# Greedy permutation of the set $\{1,2,\dots,n\}$ and prime numbers

Answering this question, another question came to my mind. For which $n$ will the greedy algorithm work?

We define a sequence of natural numbers $x_n$ recursively: $$x_1 =1,$$ $$x_n \mbox{ is the smallest natural number such that } x_n+x_{n-1} \mbox{ is prime and } x_n\neq x_k \mbox{ for all } k<n.$$ We call $n$ wabbity if $$\{x_1,x_2,\ldots x_n\} = \{1,2,\ldots n\}.$$

Is there an infinitely many wabbity numbers? Is there an effective characterisation of wabbity numbers?

• Be vewy vewy quiet... I'm huntin' wabbits... wehehehehe Jun 8 '16 at 19:13
• Are there any? [yes – $n=2,3,4$ all work] Have you found a few, and then consulted the Online Encyclopedia of Integer Sequences? Jun 8 '16 at 23:16
• oeis is not responding for me right now. Here's what I get for the sequence of wabbity numbers. pastebin.com/wFWTs5eV 1, 2, 3, 4, 7, 8, 9, 10, 17, 18, 19, 22, 23, 24, 43, 55, 56, 57, 73, 99, 136, 137, 142, 143, 202, 217, 218, 233, 234, 264, 281, 282, 287, 288, 289, 302, 303, 304, 387, 409, 414, 415, 491, 509, 520, 521, 528, 529, 532, 533, 553, 554, 555, 588, 652, 653, 654, 665, 666, 788, 789, 790, 806, 807, 812, 813, 814, 901, 940, 941
– usul
Jun 9 '16 at 0:13
• OK, the wabbity numbers are here: oeis.org/A070942 "Values of n such that the first n terms of oeis.org/A055265 constitute a permutation" but little information about them otherwise.
– usul
Jun 9 '16 at 0:25
• I bet you say that to all the wabbits. Yet it looks like a nice question to prove that all naturals appear in A055265. Jun 9 '16 at 9:27