A330154 Each term is visited according to the rule: move left (resp. right) a(n) places if a(n) is prime (resp. not prime), starting at n = 1: lexicographically earliest such sequence of distinct positive integers.

1, 4, 6, 8, 2, 9, 3, 10, 12, 5, 14, 15, 16, 7, 18, 20, 21, 22, 11, 24, 25, 26, 13, 27, 28, 30, 32, 17, 33, 34, 35, 19, 36, 38, 39, 40, 23, 42, 44, 45, 46, 48, 49, 50, 29, 51, 52, 31, 54, 55, 56, 57, 58, 60, 62, 37, 63, 64, 65, 66, 41, 68, 69, 70, 43, 72, 74, 75, 76, 47, 77

Offset: 1

Author

M. F. Hasler, Dec 03 2019

Keywords

• nonn

Comments

Inspired by A329423, which is constructed "following the journey" and not lexicographically earliest.

Conjectured to be a permutation of the positive integers: see Example for computational results.

"Each term is visited" means here more precisely that each term has a successor and each term a(n) > 1 has a "predecessor" a(m) such that m + a(m)*(-1)^isprime(a(m)) = n (see examples), and there are no loops. The trajectory from a(1) to, e.g., a(3) is not yet known.

However, for given N we can construct a sequence which equals this sequence for the first N terms, and then deviates from minimality in order to make an effort to "connect" the trajectories which are so far not yet connected. This can be achieved using the method outlined in A329423: following the trajectory of 1, once beyond index N, one always chooses the largest possible prime in order to drive the journey back to small numbers; if no prime is possible one uses the smallest possible composite. We have verified for several N that we get indeed a path from a(1) = 1 through a(7) = 3 -> a(4) = 8 and a(5) = 2 -> a(3) = 6 etc., see examples for more. The current sequence can be seen as the limit of all these manifestly "connected" sequences, as N -> oo.

Examples

			a(1) = 1 is the smallest available choice at that point and does not lead to a contradiction. It means that after this term, the term at index 1 + 1 = 2 must be visited.
a(2) cannot be a prime since these are >= 2 and would "point" to a nonpositive index. The smallest available choice is a(2) = 4, which means that after this term, the term at index 2 + 4 = 6 must be visited.
a(3) also cannot be prime, because 2 would lead back to 3 - 2 = 1 and give a loop, and other primes are too large to specify a valid step to the left. Thus a(3) = 6 is the smallest possible choice, leading to index 3 + 6 = 9 after this term is visited.
Similarly a(4) = 8, leading to index 4 + 8 = 12 after this term.
Then a(5) can be equal to the smallest available number, 2, leading to index 5 - 2 = 3 after this term is visited.
Therefore a(6) cannot be 3, which would lead to 6 - 3 = 3, but a(3) already has a(5) as predecessor. Larger primes aren't possible either, so the smallest possible choice is a(6) = 9, leading to 6 + 9 = 15.
And so on.
After 1000 terms, the smallest unused number is the prime 787, and the earliest term which does not yet have a predecessor is a(226) = 238.
After 2000 terms, the smallest unused number is the prime 1583, and the earliest term which does not yet have a predecessor is a(420).
After 10^4 terms, the smallest unused number is the prime 8219, and the earliest term which does not yet have a predecessor is a(1784).
It appears that these limits increase roughly linearly, which justifies the conjecture that all numbers will eventually appear and have a predecessor.
The trajectories involving the first few terms are:
a(1)=1 -> a(2)=4 -> a(6)=9 -> a(15)=18 -> a(33)=36 -> a(69)=76 -> a(145)=103 -> a(42)=48 -> a(90)=96 -> a(186)=200 -> a(386)=404 -> a(790)=820 -> a(1610)=1666 -> a(3276)=3369 -> a(6645)=6807 -> ...
... -> a(6461)=5261 -> a(1200)=937 -> a(263)=193 -> a(70)=47 -> a(23)=13 ->
  a(10)=5 -> a(5)=2 -> a(3)=6 -> a(9)=12 -> a(21)=25 -> a(46)=51 -> a(97)=67 ->
  a(30)=34 -> a(64)=70 -> a(134)=144 -> a(278)=294 -> a(572)=596 ->
  a(1168)=1210 -> a(2378)=2451 -> a(4829)=3907 -> a(922)=957 -> a(1879)=1939 ->
  a(3818)=3922 -> a(7740)=7917 -> ...
... -> a(4286)=3461 -> a(825)=858 -> a(1683)=1737 -> a(3420)=2741 -> a(679)=708 ->
  a(1387)=1087 -> a(300)=223 -> a(77)=53 -> a(24)=27 -> a(51)=56 ->
  a(107)=116 -> a(223)=163 -> a(60)=66 -> a(126)=89 -> a(37)=23 -> a(14)=7 ->
  a(7)=3 -> a(4)=8 -> a(12)=15 -> a(27)=32 -> a(59)=65 -> a(124)=133 ->
  a(257)=273 -> a(530)=552 -> a(1082)=1124 -> a(2206)=2271 -> a(4477)=4593 ->
  a(9070)=9275 -> ...
We can modify the sequence from a certain index on, in order connect the trajectories through a(3) = 6 and a(4) = 8 earlier. For example, one variant which has the same terms up to a(10) but connects all these quite early yields (breaking lines before "local minima"):
a(1)=1 -> a(2)=4 -> a(6)=9 -> a(15)=7 -> a(8)=10 -> a(18)=11 ->
  a(7)=3 -> a(4)=8 -> a(12)=14 -> a(26)=13 -> a(13)=15 -> a(28)=17 ->
  a(11)=16 -> a(27)=18 -> a(45)=31 ->
  a(14)=20 -> a(34)=21 -> a(55)=23 -> a(32)=22 -> a(54)=37 -> a(17)=24 ->
  a(41)=19 -> a(22)=25 -> a(47)=26 -> a(73)=53 ->
  a(20)=28 -> a(48)=29 -> a(19)=27 -> a(46)=30 -> a(76)=47 ->
  a(29)=32 -> a(61)=33 -> a(94)=71 -> a(23)=34 -> a(57)=41 ->
  a(16)=35 -> a(51)=36 -> a(87)=43 -> a(44)=38 -> a(82)=39 -> a(121)=97 ->
  a(24)=40 -> a(64)=42 -> a(106)=73 -> a(33)=44 -> a(77)=67 -> a(10)=5 ->
  a(5)=2 -> a(3)=6 -> a(9)=12 -> a(21)=45 -> ...
		

Crossrefs

Cf. A329423.

Programs

PARI

A330154_upto(N,U=[0],V=[1])={vector(N, n, my(t); for(k=U[1]+1,oo, setsearch(U,k) || setsearch(V,t=n+(-1)^isprime(k)*k) || t <= V[1] || break); if(V[1]+11 && V[2]==V[1]+1,V=V[^1])); if(U[1]+11 && U[2]==U[1]+1,U=U[^1])); t)}