To Catch a Prime

[Ali Sada]

Hi everyone,

Hope all is well.

Start with the list of positive integers
1, 2, 3, 4, 5, 6, ...
At each step, scan the list from left to right and choose the first entry k such that removing k and reinserting it exactly k positions to the right places it immediately before a prime number. Perform the move and let a(n) be the value moved at the n-th step.

Initially, 1 moves one position to the right and lands immediately before 3, so a(1) = 1.
The list is now
2, 1, 3, 4, 5, 6, 7, ...
Neither 2 nor 1 qualifies, but 3 moves three positions to the right and lands immediately before 7, so a(2) = 3.

The sequence begins
1, 3, 2, 1, 4, 1, 6, 6, 6, 8, ...

We can use the same algorithm with other prescribed targets, for example triangular numbers.

Again, at each step choose the leftmost entry k that can be moved exactly k positions to the right so that it lands immediately before a triangular number.
The sequence begins
1, 7, 4, 8, 11, 18, 7, 19, 10, 6, ...
 

Question: Does every positive integer eventually appear in either sequence?

If any of these sequences is suitable for the OEIS I would really appreciate the usual help with the definition, terms, program, etc.

Best,

Ali

[Allan Wechsler]

Note that if we always move the leading number, unconditionally, the resulting sequence is the 1-based ruler sequence oeis.org/A001511 , in which every positive integer does eventually appear (though you often have to wait a long time).

My intuition is that the sequences Ali is proposing have the same property. Well, wait. I suppose it is possible that the process might enter a loop ...

--  Allan

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNrY2jVsi1aawja8%2B6p43Y3bc9QvH1FtRjZGO19CEi5E1A%40mail.gmail.com.

[Daniel Mondot]

Ali, could you clarify what you mean by "Neither 2 nor 1 qualifies". It might affect what Allan is thinking, about making loops.

Or to be more specific, how do you pick the next number to move, if some numbers don't "qualify"?

Daniel.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CADy-sGHXH7jPkfggQzC%2BLvv%2Bs9zvV6Pv0gav3POMHHA4PApCmg%40mail.gmail.com.

[Allan Wechsler]

Daniel, I think Ali means that if you were to move the 2 two steps to the right, it would end up in front of a composite number (4); the same with moving 1 one step to the right. A number n "qualifies" if the number n+1 to its right is prime. Ali, please correct me if I have misunderstood your procedure.

-- Allan

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD5iKaiKtR52%3Dgehk6BUJcV7a49f22dqJYtPR%2BZpb9p8G2cUkg%40mail.gmail.com.

[Ali Sada]

Thank you Allan and Daniel for your responses. I really appreciate it. Allan's explanation is correct. The moving number must land before a prime in the first sequence. 

Best,

Ali

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CADy-sGFVdxYsaLQx2s9w5QRh6ptVm%2Bzxvk%2BojCjuO16ogaeGYQ%40mail.gmail.com.