A364332 -id:A364332 - cp's OEIS frontend

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

Offset: 0

N. J. A. Sloane, Apr 25 2003

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: (Start):
If a(n) * k + 1 is prime then a(n + 1) <= a(n) * k + 1.
a(18), a(19), ..., a(23) <= 309554053859, 619108107719, 19811459447009, 433142367554861, 866284735109723, 22523403112852799 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

			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.

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

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

(* 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 *)

Edited by Klaus Brockhaus, May 01 2003

a(16) from Donovan Johnson, Nov 17 2008

A364334 a(2) = 0; a(n) = a(n-1) + 1 if n is an odd prime; otherwise a(n) = max{a(k) : k is divisor of n, 1 < k < n}.

Original entry on oeis.org

0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 1, 0, 1, 1, 2, 1, 2, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 0, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 1, 3, 4, 1, 2, 1, 1, 2, 3, 1, 2, 2, 2, 3, 4, 1, 2, 2, 2, 0, 2, 2, 3, 1, 3, 2, 3, 1, 2, 2, 1, 2, 2, 2, 3, 1, 1, 2, 3, 2, 1, 3, 3, 2, 3, 1, 2, 3, 2, 4, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 3, 4, 1, 2, 2, 2, 2

Offset: 2

Steven Lu, Jul 18 2023

nonn

This sequence is a kind of measure of the "amount of information" in an integer. The post at Zhihu wonders whether one can calculate this sequence without using prime decomposition.

			a(238)=2, since a(2)=0, a(7)=2, a(14)=2, a(17)=1, a(34)=1, a(119)=2, and the largest among them is 2.
And a(239)=3, since 239 is a prime number, and a(238)=2.

Zhihu, Can the order of a number be known by bypassing the complicated calculation of "prime factor decomposing"?, Aug 12 2022.

For values at primes, see A364332.

Nest[Function[list,
  Module[{n = Length[list] + 1},
   Append[list,
    If[PrimeQ[n], Last[list] + 1,
     Max[(list[[First[#]]]) & /@ FactorInteger[n]]]]]], {0, 0}, 110]//Rest

a(2) = 0,
a(n) = a(n-1) + 1 if n is an odd prime,
a(n) = max{a(k) : k|n, 1

Showing 1-2 of 2 results.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Extensions