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

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

Offset: 1

Author

Klaus Brockhaus, May 01 2003

Keywords

• nonn

Comments

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

Examples

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

Links

• Ruud H.G. van Tol, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A006530, A023503, A082449.

Programs

Mathematica

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

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,","))}