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

%I #25 Sep 17 2023 01:22:50

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

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

%U 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

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

%C 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.

%H Zhihu, <a href="https://www.zhihu.com/question/548052659">Can the order of a number be known by bypassing the complicated calculation of "prime factor decomposing"?</a>, Aug 12 2022.

%F a(2) = 0,

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

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

%e 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.

%e And a(239)=3, since 239 is a prime number, and a(238)=2.

%t Nest[Function[list,

%t Module[{n = Length[list] + 1},

%t Append[list,

%t If[PrimeQ[n], Last[list] + 1,

%t Max[(list[[First[#]]]) & /@ FactorInteger[n]]]]]], {0, 0}, 110]//Rest

%Y For values at primes, see A364332.

%K nonn

%O 2,6

%A _Steven Lu_, Jul 18 2023