A364332 -id:A364332

Search: a364332 -id:a364332

Displaying 1-2 of 2 results found.

page 1

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.

+10
6

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

(list; graph; refs; listen; history; text; internal format)

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: (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

REFERENCES

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

LINKS

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

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.

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

STATUS

approved

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

+10
1

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,6

COMMENTS

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.

LINKS

Table of n, a(n) for n=2..112.

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

FORMULA

a(2) = 0,

a(n) = a(n-1) + 1 if n is an odd prime,

a(n) = max{a(k) : k|n, 1<k<n} otherwise.

EXAMPLE

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.

MATHEMATICA

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

CROSSREFS

For values at primes, see A364332.

KEYWORD

nonn

AUTHOR

Steven Lu, Jul 18 2023

STATUS

approved

page 1

Search completed in 0.006 seconds