cp's OEIS Frontend

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.

%I A337979 #16 Oct 24 2020 10:53:44
%S A337979 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,
%T A337979 17,18,18,19,19,19,20,20,20,21,21,21,22,22,22,23,23,23,24,24,24,25,25,
%U A337979 25,25,26,26,26,26,26,27,27,27,27,28,28,28,28,28,29,29
%N 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.
%C A337979 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.
%C A337979 It seems that the sequence contains all nonnegative integers.
%H A337979 Alois P. Heinz, <a href="/A337979/b337979.txt">Table of n, a(n) for n = 1..10000</a>
%H A337979 Ya-Ping Lu and Shu-Fang Deng, <a href="https://arxiv.org/abs/2007.15282">An upper bound for the prime gap</a>, arXiv:2007.15282 [math.GM], 2020.
%F A337979 f^a(n) (n) = 1, where f = A062298(A095117) and m-fold iteration of f is denoted by f^m.
%e A337979 a(1) = 0 because f^0(1) = 1;
%e A337979 a(2) = 1 because f(2) = 2 + pi(2) - pi(2 + pi(2)) = 1;
%e A337979 a(4) = 3 because f^3(4) = f^2(f(4)) = f^2(3) = f(f(3)) = f(2) = 1.
%p A337979 a:= proc(n) option remember; `if`(n=1, 0, 1+a((
%p A337979       pi-> n+pi(n)-pi(n+pi(n)))(numtheory[pi])))
%p A337979     end:
%p A337979 seq(a(n), n=1..80);  # _Alois P. Heinz_, Oct 24 2020
%t A337979 f[n_] := Module[{x = n + PrimePi[n]}, x - PrimePi[x]];
%t A337979 a[n_] := Module[{nb = 0, m = n}, While[m != 1, m = f[m]; nb++]; nb];
%t A337979 Array[a, 100] (* _Jean-François Alcover_, Oct 24 2020, after PARI code *)
%o A337979 (Python)
%o A337979 from sympy import primepi
%o A337979 print(0)
%o A337979 n = 2
%o A337979 for n in range (2, 10000001):
%o A337979     ct = 0
%o A337979     n_l = n
%o A337979     pi_l = primepi(n)
%o A337979     while ct >= 0:
%o A337979         n_r = n_l + pi_l
%o A337979         pi_r = primepi(n_r)
%o A337979         n_l = n_r - pi_r
%o A337979         pi_l = primepi(n_l)
%o A337979         ct += 1
%o A337979         if n_l == 1:
%o A337979             print(ct)
%o A337979             break
%o A337979 (PARI) f(n) = {my(x = n + primepi(n)); x - primepi(x);} \\ A337978
%o A337979 a(n) = {my(nb=0); while (n != 1, n = f(n); nb++); nb;} \\ _Michel Marcus_, Oct 06 2020
%Y A337979 Cf. A000720, A025003, A062298, A095117, A337978.
%K A337979 nonn
%O A337979 1,3
%A A337979 _Ya-Ping Lu_, Oct 05 2020