login
For primes p: Number of steps to reach 2 when iterating f(p) = greatest prime divisor of p-1.
4

%I #17 Sep 02 2024 19:34:05

%S 0,1,1,2,2,2,1,2,3,3,2,2,2,3,4,3,4,2,3,3,2,3,3,3,2,2,2,4,2,3,3,3,2,4,

%T 3,2,3,2,4,4,4,2,3,2,3,3,3,3,4,3,4,2,2,2,1,4,4,2,4,3,5,3,2,3,3,4,3,3,

%U 5,4,3,5,3,3,3,4,3,3,2,2,3,3,4,2,3,2,3,3,4,3,5,3,2,3,4,3,4,3,4,2,3,5,4,4,3

%N For primes p: Number of steps to reach 2 when iterating f(p) = greatest prime divisor of p-1.

%C For smallest prime that requires n steps to reach 2 cf. A082449.

%H Ruud H.G. van Tol, <a href="/A083647/b083647.txt">Table of n, a(n) for n = 1..10000</a>

%e 59 is the 17th prime and takes four steps to reach 2 (59 -> 29 -> 7 -> 3 -> 2), so a(17) = 4.

%t Table[Length[NestWhileList[FactorInteger[#-1][[-1,1]]&,Prime[n], #!=2&]]-1,{n,110}] (* _Harvey P. Dale_, Feb 27 2012 *)

%o (PARI) {forprime(p=2,571,q=p; c=0; while(q>2,fac=factor(q-1); q=fac[matsize(fac)[1],1]; c++); print1(c,","))}

%Y Cf. A006530, A023503, A082449.

%K nonn

%O 1,4

%A _Klaus Brockhaus_, May 01 2003