login
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.
20
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, 11, 42, 21, 58, 29, 70, 35, 78, 39, 86, 43, 96, 48, 24, 12, 6, 3, 62, 31, 92, 46, 23, 90, 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
OFFSET
1,2
COMMENTS
Will every positive integer appear in S?
Comment from Allan C. Wechsler, Jan 22 2022: (Start)
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).
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.
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)
After 10^9 terms the missing numbers are 36, 72, 97, 115, 127, 144, 167, 194, 211, ... - Hans Havermann, Jan 22 2022
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
a(17282073747556) = 194, a(17282073747557) = 97. - Martin Ehrenstein, Jan 26 2022 [Where does this descending chain start? - N. J. A. Sloane, Jan 27 2022]
From Martin Ehrenstein, Jan 29 2022: (Start)
36 is part of a descending chain that ends with a(77534485879) = 9 and starts with a(77534485842) = 1236950581248 after adding the prime 677121348413.
a(17282073747557) = 97 ends a descending chain that starts with a(17282073747516) = 213305255788544 after adding the prime 183236837077571.
a(45274461582754) = 115 ends a descending chain that starts with a(45274461582712) = 505775348776960 after adding the prime 495047540307647.
After 5*10^13 terms, the missing numbers are 127, 167, 211, 232, 254, ... (End)
LINKS
Michael De Vlieger, Scatterplot of a(n) n = 1..2^16.
Michael De Vlieger, Annotated log-log scatterplot of a(n), n = 1..2^14, labeling the first 64 terms, highlighting records in red, 1's in blue, and primes in gold.
Rémy Sigrist, Colored scatterplot of the first 100000 terms (red pixels correspond to terms following an odd term)
EXAMPLE
S = 1, ...
1 is odd, we add the prime 2:
S = 1, 3, ...
3 is odd, we add the next prime, 3:
S = 1, 3, 6, ...
6 is even, we divide by 2:
S = 1, 3, 6, 3, ...
3 is odd, we add the next prime, 5:
S = 1, 3, 6, 3, 8, ...
8 is even we divide by 2 (etc.):
S = 1, 3, 6, 3, 8, 4, 2, 1, ...
1 is odd, we add the next prime, 7:
S = 1, 3, 6, 3, 8, 4, 2, 1, 8, ...
8 is even, we divide by 2 (etc.):
S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, ...
1 is odd, we add the next prime, 11:
S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, ...
12 is even, we divide by 2 (etc.):
S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, ...
3 is odd, we add the next prime, 13:
S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, ...
16 is even, we divide by 2 (etc.):
S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1, ...
1 is odd, we add the next prime, 17:
S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1, 18, ...
18 is even, we divide by 2:
S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1, 18, 9, ...
9 is odd, we add the next prime, 19:
S = 1, 3, 6, 3, 8, 4, 2, 1, 8, 4, 2, 1, 12, 6, 3, 16, 8, 4, 2, 1, 18, 9, 28, ...
Etc.
MAPLE
# To produce M terms in b-file format:
M:=100000;
p:=1; L:=1;
for n from 1 to M do
if n=1 then lprint(n, L);
else if (L mod 2) = 0 then L := L/2;
else p:=nextprime(p); L:=L+p;
fi;
lprint(n, L);
fi;
od: # N. J. A. Sloane, Jan 28 2022
MATHEMATICA
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 *)
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 *)
PROG
(PARI) { print1 (v=1); forprime (p=2, 109, print1 (", "v+=p); while (v%2==0, print1 (", "v/=2))) } \\ Rémy Sigrist, Jan 23 2022
(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
(Python)
from sympy import nextprime
a, p = [1], 1
[a.append(a[-1]//2 if a[-1]%2 == 0 else a[-1]+(p:=nextprime(p))) for n in range(79)]
print(a) # Michael S. Branicky, Jan 23 2022
CROSSREFS
A350615 gives indices of 1's, A350616 gives indices of odd terms. See also A350617, A350618, A350619, A350833, A362107, A362108.
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.
Sequence in context: A201143 A326935 A135003 * A090895 A337903 A358787
KEYWORD
nonn,nice
AUTHOR
Eric Angelini and Carole Dubois, Jan 22 2022
EXTENSIONS
Added name Sisyphus sequence. - N. J. A. Sloane, Jan 23 2022
STATUS
approved