Skip to main content
1 of 3
Bugs Bunny
  • 12.3k
  • 1
  • 30
  • 65

Greedy permutation of the set {1,2,…,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?

Bugs Bunny
  • 12.3k
  • 1
  • 30
  • 65