cp's OEIS Frontend

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.

%I A330154 #21 Dec 06 2019 23:31:47
%S A330154 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,
%T A330154 32,17,33,34,35,19,36,38,39,40,23,42,44,45,46,48,49,50,29,51,52,31,54,
%U A330154 55,56,57,58,60,62,37,63,64,65,66,41,68,69,70,43,72,74,75,76,47,77
%N 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.
%C A330154 Inspired by A329423, which is constructed "following the journey" and not lexicographically earliest.
%C A330154 Conjectured to be a permutation of the positive integers: see Example for computational results.
%C A330154 "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.
%C A330154 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.
%e A330154 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.
%e A330154 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.
%e A330154 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.
%e A330154 Similarly a(4) = 8, leading to index 4 + 8 = 12 after this term.
%e A330154 Then a(5) can be equal to the smallest available number, 2, leading to index 5 - 2 = 3 after this term is visited.
%e A330154 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.
%e A330154 And so on.
%e A330154 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.
%e A330154 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).
%e A330154 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).
%e A330154 It appears that these limits increase roughly linearly, which justifies the conjecture that all numbers will eventually appear and have a predecessor.
%e A330154 The trajectories involving the first few terms are:
%e A330154 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 -> ...
%e A330154 ... -> a(6461)=5261 -> a(1200)=937 -> a(263)=193 -> a(70)=47 -> a(23)=13 ->
%e A330154   a(10)=5 -> a(5)=2 -> a(3)=6 -> a(9)=12 -> a(21)=25 -> a(46)=51 -> a(97)=67 ->
%e A330154   a(30)=34 -> a(64)=70 -> a(134)=144 -> a(278)=294 -> a(572)=596 ->
%e A330154   a(1168)=1210 -> a(2378)=2451 -> a(4829)=3907 -> a(922)=957 -> a(1879)=1939 ->
%e A330154   a(3818)=3922 -> a(7740)=7917 -> ...
%e A330154 ... -> a(4286)=3461 -> a(825)=858 -> a(1683)=1737 -> a(3420)=2741 -> a(679)=708 ->
%e A330154   a(1387)=1087 -> a(300)=223 -> a(77)=53 -> a(24)=27 -> a(51)=56 ->
%e A330154   a(107)=116 -> a(223)=163 -> a(60)=66 -> a(126)=89 -> a(37)=23 -> a(14)=7 ->
%e A330154   a(7)=3 -> a(4)=8 -> a(12)=15 -> a(27)=32 -> a(59)=65 -> a(124)=133 ->
%e A330154   a(257)=273 -> a(530)=552 -> a(1082)=1124 -> a(2206)=2271 -> a(4477)=4593 ->
%e A330154   a(9070)=9275 -> ...
%e A330154 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"):
%e A330154 a(1)=1 -> a(2)=4 -> a(6)=9 -> a(15)=7 -> a(8)=10 -> a(18)=11 ->
%e A330154   a(7)=3 -> a(4)=8 -> a(12)=14 -> a(26)=13 -> a(13)=15 -> a(28)=17 ->
%e A330154   a(11)=16 -> a(27)=18 -> a(45)=31 ->
%e A330154   a(14)=20 -> a(34)=21 -> a(55)=23 -> a(32)=22 -> a(54)=37 -> a(17)=24 ->
%e A330154   a(41)=19 -> a(22)=25 -> a(47)=26 -> a(73)=53 ->
%e A330154   a(20)=28 -> a(48)=29 -> a(19)=27 -> a(46)=30 -> a(76)=47 ->
%e A330154   a(29)=32 -> a(61)=33 -> a(94)=71 -> a(23)=34 -> a(57)=41 ->
%e A330154   a(16)=35 -> a(51)=36 -> a(87)=43 -> a(44)=38 -> a(82)=39 -> a(121)=97 ->
%e A330154   a(24)=40 -> a(64)=42 -> a(106)=73 -> a(33)=44 -> a(77)=67 -> a(10)=5 ->
%e A330154   a(5)=2 -> a(3)=6 -> a(9)=12 -> a(21)=45 -> ...
%o A330154 (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]+1<t, V=setunion(V,[t]), V[1]=t; while(#V>1 && V[2]==V[1]+1,V=V[^1])); if(U[1]+1<t=abs(t-n), U=setunion(U,[t]), U[1]=t; while(#U>1 && U[2]==U[1]+1,U=U[^1])); t)}
%Y A330154 Cf. A329423.
%K A330154 nonn
%O A330154 1,2
%A A330154 _M. F. Hasler_, Dec 03 2019