A082449 Let f(p) = greatest prime divisor of p-1. Sequence gives smallest prime which takes at least n steps to reach 2 when f is iterated.

2, 3, 7, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 1266767, 14619833, 36449279, 377982107, 1432349099, 22111003847, 54560052479, 619108107719, 7242080052479, 64750853277599

Offset

0,1

Comments

There is a remarkable and unexplained agreement: if 3 and 7 are replaced by 11 and 14619833 is replaced by 14920303, the result is sequence A056637 (least prime of class n-, according to the Erdős-Selfridge classification of primes).

From David A. Corneth, Oct 18 2016, corrected and updated, Apr 18 2026: (Start):

a(18), a(19), ..., a(27) <= 619108107719, 7242080052479, 85301359593119, 866284735109723, 11407852252734739, 115504631269039577, 693027787614237463, 11989855155001502477, 167857972170021034679, 3506325202899107096567 respectively. (End)

Conjecture: a(n) is the smallest prime p such that b(p) = n, where f(2) = 0 and for an odd prime p, f(p) = 1 + max{q|(p-1), q prime} f(q). In other words, a(n) is the smallest prime p such that A364332(primepi(p)) = n. Verified for n <= 13. - Jianing Song, Apr 28 2024

This sequence and A056637 both involve the prime factors of p-1, when p is prime. This sequence depends on the largest factor of p-1 whereas A056637 depends on the largest class number of its factors. If the largest prime factor of p-1 is also the one with the largest class number, the terms should coincide. - Jud McCranie, Apr 30 2026

References

Steven G. Johnson, Postings to Number Theory List, Apr 23 and Apr 25, 2003.

Links

Table of n, a(n) for n=0..20.

Example

a(2) = 7 since 7 -> 3 -> 2 takes two steps, and smaller primes require less than 2 steps.
For p = 2879, 8 steps are needed (2879 -> 1439 -> 719 -> 359 -> 179 -> 89 -> 11 -> 5 -> 2), so a(8) = 2879, since smaller primes require less than 8 steps.

Mathematica

(* Assuming a(n) > 2 a(n-1) if n>1 *) Clear[a, f]; f[p_] := FactorInteger[p - 1][[-1, 1]]; f[2] = 2; a[n_] := a[n] = For[p = NextPrime[2 a[n-1]], True, p = NextPrime[p], k = 0; If[Length[FixedPointList[f, p]] == n+2, Return[p]]]; a[0]=2; a[1]=3; Table[Print[a[n]]; a[n], {n, 0, 16}] (* Jean-François Alcover, Oct 18 2016 *)

Crossrefs

Cf. A006530, A023503, A083647, A056637, A364332.

Sequence in context: A366929 A376187 A346161 * A129741 A006720 A084710

Adjacent sequences: A082446 A082447 A082448 * A082450 A082451 A082452

Keyword

nonn,more

Author

N. J. A. Sloane, Apr 25 2003

Extensions

Edited by Klaus Brockhaus, May 01 2003

a(16) from Donovan Johnson, Nov 17 2008

a(17)-a(18) by Jud McCranie, Apr 17 2026

a(19) by Jud McCranie, Apr 21 2026

a(20) by Jud McCranie, Apr 30 2026

Status

approved