A175177 - OEIS

%I #26 Sep 25 2017 05:43:11

%S 2,3,4,9,2,31,6,4,2,2,2,11,24,41,2,2,2,57,2,2,58,2,2,6,17,4,2,2,39,67,

%T 2,2,2,2,2,2,25,4,2,2,2,158,2,61,2,2,2,2,2,2,54,2,186,2,10,2,2,2,18,8,

%U 2,2,2,2,96,2,2,18,2,6,15,2,2,2,2,2,2,44,34,6,2,16,2,105,2,2,60,5,4,2,2,2,4

%N Conjectured number of numbers for which the iteration x -> phi(x) + 1 terminates at prime(n). Cardinality of rooted tree T_p (where p is n-th prime) in Karpenko's book.

%D Richard K. Guy, Unsolved Problems in Number Theory, Third Edition, Springer, New York 2004. Chapter B41, Iterations of phi and sigma, page 148.

%D A. S. Karpenko, Lukasiewicz's Logics and Prime Numbers, (English translation), 2006. See Table 2 on p.125 ff.

%D A. S. Karpenko, Lukasiewicz's Logics and Prime Numbers, (Russian), 2000.

%H Hugo Pfoertner, <a href="/A175177/b175177.txt">Table of n, a(n) for n = 1..1000</a>

%e a(3) = 4 because x = { 5, 8, 10, 12 } are the 4 numbers from which the iteration x -> phi(x) + 1 terminates at prime(3) = 5.

%e a(4) = 8 because x = { 7, 9, 14, 15, 16, 18, 20, 24, 30 } are the 9 numbers from which the iteration x -> phi(x) + 1 terminates at prime(4) = 7.

%o (PARI)

%o iterat(x) = {my(k,s); if ( isprime(x),return(x)); s=x;

%o for (k=1,1000000000,s=eulerphi(s)+1;if(isprime(s),return(s)));

%o return(s); }

%o check(y,endrange) = {my(count,start); count=0;

%o for(start=1,endrange,if(iterat(start)==y,count++;));

%o return(count); }

%o for (n=1,93,x=prime(n);print1(check(x,1000000),", "))

%o \\ _Hugo Pfoertner_, Sep 23 2017

%Y Cf. A039649, A039650, A039651, A039652, A096827, A175178.

%K nonn

%O 1,1

%A _Artur Jasinski_, Mar 01 2010

%E Name clarified by _Hugo Pfoertner_, Sep 23 2017