login
A337979
Define a map f(n):= n-> n + pi(n) - pi(n + pi(n)), where pi(n) is the prime count of n (n>=1). a(n) is the number of steps for n to reach 1 under repeated iteration of f.
3
0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14, 14, 15, 15, 16, 16, 17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 28, 29, 29
OFFSET
1,3
COMMENTS
For any integer n > 1, pi(n + pi(n)) > pi(n) according to Lu and Deng (see Links). Thus, n + pi(n) - pi(n + pi(n)) < n, which means n is reduced by at least 1 every time map f is applied, eventually reaching 1 under repeated iteration of f.
It seems that the sequence contains all nonnegative integers.
LINKS
Ya-Ping Lu and Shu-Fang Deng, An upper bound for the prime gap, arXiv:2007.15282 [math.GM], 2020.
FORMULA
f^a(n) (n) = 1, where f = A062298(A095117) and m-fold iteration of f is denoted by f^m.
EXAMPLE
a(1) = 0 because f^0(1) = 1;
a(2) = 1 because f(2) = 2 + pi(2) - pi(2 + pi(2)) = 1;
a(4) = 3 because f^3(4) = f^2(f(4)) = f^2(3) = f(f(3)) = f(2) = 1.
MAPLE
a:= proc(n) option remember; `if`(n=1, 0, 1+a((
pi-> n+pi(n)-pi(n+pi(n)))(numtheory[pi])))
end:
seq(a(n), n=1..80); # Alois P. Heinz, Oct 24 2020
MATHEMATICA
f[n_] := Module[{x = n + PrimePi[n]}, x - PrimePi[x]];
a[n_] := Module[{nb = 0, m = n}, While[m != 1, m = f[m]; nb++]; nb];
Array[a, 100] (* Jean-François Alcover, Oct 24 2020, after PARI code *)
PROG
(Python)
from sympy import primepi
print(0)
n = 2
for n in range (2, 10000001):
ct = 0
n_l = n
pi_l = primepi(n)
while ct >= 0:
n_r = n_l + pi_l
pi_r = primepi(n_r)
n_l = n_r - pi_r
pi_l = primepi(n_l)
ct += 1
if n_l == 1:
print(ct)
break
(PARI) f(n) = {my(x = n + primepi(n)); x - primepi(x); } \\ A337978
a(n) = {my(nb=0); while (n != 1, n = f(n); nb++); nb; } \\ Michel Marcus, Oct 06 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Ya-Ping Lu, Oct 05 2020
STATUS
approved