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

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

Sequence in context: A061358 A025866 A259920 * A048881 A026931 A339823

Adjacent sequences: A364331 A364332 A364333 * A364335 A364336 A364337

Keyword

nonn

Author

Steven Lu, Jul 18 2023

Status

approved