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,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

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.

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

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

Sequence in context: A327707 A134679 A100721 * A265359 A271490 A252649

Adjacent sequences: A337976 A337977 A337978 * A337980 A337981 A337982

Keyword

nonn

Author

Ya-Ping Lu, Oct 05 2020

Status

approved