cp's OEIS Frontend

A175177 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.

%I A175177 #26 Sep 25 2017 05:43:11
%S A175177 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 A175177 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 A175177 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 A175177 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 A175177 Richard K. Guy, Unsolved Problems in Number Theory, Third Edition, Springer, New York 2004. Chapter B41, Iterations of phi and sigma, page 148.
%D A175177 A. S. Karpenko, Lukasiewicz's Logics and Prime Numbers, (English translation), 2006. See Table 2 on p.125 ff.
%D A175177 A. S. Karpenko, Lukasiewicz's Logics and Prime Numbers, (Russian), 2000.
%H A175177 Hugo Pfoertner, <a href="/A175177/b175177.txt">Table of n, a(n) for n = 1..1000</a>
%e A175177 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 A175177 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 A175177 (PARI)
%o A175177 iterat(x) = {my(k,s); if ( isprime(x),return(x)); s=x;
%o A175177 for (k=1,1000000000,s=eulerphi(s)+1;if(isprime(s),return(s)));
%o A175177 return(s); }
%o A175177 check(y,endrange) = {my(count,start); count=0;
%o A175177 for(start=1,endrange,if(iterat(start)==y,count++;));
%o A175177 return(count); }
%o A175177 for (n=1,93,x=prime(n);print1(check(x,1000000),", "))
%o A175177 \\ _Hugo Pfoertner_, Sep 23 2017
%Y A175177 Cf. A039649, A039650, A039651, A039652, A096827, A175178.
%K A175177 nonn
%O A175177 1,1
%A A175177 _Artur Jasinski_, Mar 01 2010
%E A175177 Name clarified by _Hugo Pfoertner_, Sep 23 2017