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.

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

Author

Ya-Ping Lu, Oct 05 2020

Keywords

• nonn

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.

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• Ya-Ping Lu and Shu-Fang Deng, An upper bound for the prime gap, arXiv:2007.15282 [math.GM], 2020.

Crossrefs

Cf. A000720, A025003, A062298, A095117, A337978.

Programs

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 *)

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

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

Formula

f^a(n) (n) = 1, where f = A062298(A095117) and m-fold iteration of f is denoted by f^m.