cp's OEIS Frontend

A350877 The Sisyphus sequence: start the sequence S with a(1) = 1 and extend S with a(n)/2 when a(n) is even, otherwise with a(n) + the smallest prime not yet added.

%I A350877 #110 Apr 13 2023 23:33:28
%S A350877 1,3,6,3,8,4,2,1,8,4,2,1,12,6,3,16,8,4,2,1,18,9,28,14,7,30,15,44,22,
%T A350877 11,42,21,58,29,70,35,78,39,86,43,96,48,24,12,6,3,62,31,92,46,23,90,
%U A350877 45,116,58,29,102,51,130,65,148,74,37,126,63,160,80,40,20,10,5,106,53,156,78,39,146,73,182,91
%N A350877 The Sisyphus sequence: start the sequence S with a(1) = 1 and extend S with a(n)/2 when a(n) is even, otherwise with a(n) + the smallest prime not yet added.
%C A350877 Will every positive integer appear in S?
%C A350877 Comment from _Allan C. Wechsler_, Jan 22 2022: (Start)
%C A350877 Conjecture: On naive probabilistic grounds, all integers should eventually appear. An up-step is always immediately followed by a down-step, and then, on average, by one more down-step. So we expect that every third step will be an up-step, by the next prime number, which will be around p(n/3).
%C A350877 So the sequence will spend a lot of its time between p(n/3)/3 and 4p(n/3)/3. It will make brief forays out of that zone but that will be its "home ground". The scatterplot should be instructive.
%C A350877 Now p(n/3) grows really slowly. It will take longer than 2^k steps to get from 2^k to 2^(k+1), and so there will be long downward excursions very roughly once in each such "era". Each of these long downward excursions has a nonzero chance of hitting any particular number N, and that chance won't decrease as the eras pass. So while we may not be able to calculate the sequence far enough to reach N, I think we can have fairly high confidence that all integers will appear. It would be interesting to study a histogram of how frequently the small integers appear. (End)
%C A350877 After 10^9 terms the missing numbers are 36, 72, 97, 115, 127, 144, 167, 194, 211, ... - _Hans Havermann_, Jan 22 2022
%C A350877 After 10^12 terms, the missing numbers are 97, 115, 127, 167, 194, 211, 230, 232, 254, ...; a(77534485875) = 144, a(77534485876) = 72, and a(77534485877) = 36. - _Russ Cox_, Jan 23 2022
%C A350877 a(17282073747556) = 194, a(17282073747557) = 97. - _Martin Ehrenstein_, Jan 26 2022 [Where does this descending chain start? - _N. J. A. Sloane_, Jan 27 2022]
%C A350877 From _Martin Ehrenstein_, Jan 29 2022: (Start)
%C A350877 36 is part of a descending chain that ends with a(77534485879) = 9 and starts with a(77534485842) = 1236950581248 after adding the prime 677121348413.
%C A350877 a(17282073747557) = 97 ends a descending chain that starts with a(17282073747516) = 213305255788544 after adding the prime 183236837077571.
%C A350877 a(45274461582754) = 115 ends a descending chain that starts with a(45274461582712) = 505775348776960 after adding the prime 495047540307647.
%C A350877 After 5*10^13 terms, the missing numbers are 127, 167, 211, 232, 254, ... (End)
%H A350877 Rémy Sigrist, <a href="/A350877/b350877.txt">Table of n, a(n) for n = 1..20000</a>
%H A350877 Michael De Vlieger, <a href="/A350877/a350877.png">Scatterplot of a(n)</a> n = 1..2^16.
%H A350877 Michael De Vlieger, <a href="/A350877/a350877_2.png">Annotated log-log scatterplot of a(n)</a>, n = 1..2^14, labeling the first 64 terms, highlighting records in red, 1's in blue, and primes in gold.
%H A350877 Rémy Sigrist, <a href="/A350877/a350877_3.png">Colored scatterplot of the first 100000 terms</a> (red pixels correspond to terms following an odd term)
%H A350877 N. J. A. Sloane, <a href="/A350877/a350877.txt">Table of n, a(n) for n = 1..100000</a>
%e A350877 S = 1, ...
%e A350877 1 is odd, we add the prime 2:
%e A350877 S = 1, 3, ...
%e A350877 3 is odd, we add the next prime, 3:
%e A350877 S = 1, 3, 6, ...
%e A350877 6 is even, we divide by 2:
%e A350877 S = 1, 3, 6, 3, ...
%e A350877 3 is odd, we add the next prime, 5:
%e A350877 S = 1, 3, 6, 3, 8, ...
%e A350877 8 is even we divide by 2 (etc.):
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, ...
%e A350877 1 is odd, we add the next prime, 7:
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, 8, ...
%e A350877 8 is even, we divide by 2 (etc.):
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, ...
%e A350877 1 is odd, we add the next prime, 11:
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, ...
%e A350877 12 is even, we divide by 2 (etc.):
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, ...
%e A350877 3 is odd, we add the next prime, 13:
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, ...
%e A350877 16 is even, we divide by 2 (etc.):
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1, ...
%e A350877 1 is odd, we add the next prime, 17:
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1, 18, ...
%e A350877 18 is even, we divide by 2:
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1, 18, 9, ...
%e A350877 9 is odd, we add the next prime, 19:
%e A350877 S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1, 18, 9, 28, ...
%e A350877 Etc.
%p A350877 # To produce M terms in b-file format:
%p A350877 M:=100000;
%p A350877 p:=1; L:=1;
%p A350877 for n from 1 to M do
%p A350877 if n=1 then lprint(n,L);
%p A350877 else if (L mod 2) = 0 then L := L/2;
%p A350877      else p:=nextprime(p); L:=L+p;
%p A350877      fi;
%p A350877 lprint(n,L);
%p A350877 fi;
%p A350877 od: # _N. J. A. Sloane_, Jan 28 2022
%t A350877 j = 1; q = 2; {j}~Join~Reap[Do[If[EvenQ[j], k = j/2, k = j + q; Set[q, NextPrime[q]]]; Sow[k]; j = k, {i, 79}]][[-1, -1]] (* _Michael De Vlieger_, Jan 22 2022 *)
%t A350877 nxt[{sp_,n_,a_}]:=Module[{p=2,c},c=If[EvenQ[a],a/2,a+sp];{If[EvenQ[ a],sp,NextPrime[sp]],n+1,c}]; NestList[nxt,{2,1,1},80][[All,3]] (* _Harvey P. Dale_, Jan 23 2022 *)
%o A350877 (PARI) { print1 (v=1); forprime (p=2, 109, print1 (", "v+=p); while (v%2==0, print1 (", "v/=2))) } \\ _Rémy Sigrist_, Jan 23 2022
%o A350877 (PARI) A350877_first(N,p=0)=vector(N,i,N=if(!p,p=1,N%2,N+p=nextprime(p+1),N/2)) \\ _M. F. Hasler_, Jan 23 2022
%o A350877 (Python)
%o A350877 from sympy import nextprime
%o A350877 a, p = [1], 1
%o A350877 [a.append(a[-1]//2 if a[-1]%2 == 0 else a[-1]+(p:=nextprime(p))) for n in range(79)]
%o A350877 print(a) # _Michael S. Branicky_, Jan 23 2022
%Y A350877 A350615 gives indices of 1's, A350616 gives indices of odd terms. See also A350617, A350618, A350619, A350833, A362107, A362108.
%Y A350877 Cf. A174221, A350742.
%Y A350877 See A350620 for when n first appears, A350621 for when the primes first appear, and A362105 and A362106 for the numbers that are the slowest to appear.
%K A350877 nonn,nice
%O A350877 1,2
%A A350877 _Eric Angelini_ and _Carole Dubois_, Jan 22 2022
%E A350877 Added name Sisyphus sequence. - _N. J. A. Sloane_, Jan 23 2022