cp's OEIS Frontend

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

%I A364334 #25 Sep 17 2023 01:22:50
%S A364334 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 A364334 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 A364334 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 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}.
%C A364334 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 A364334 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 A364334 a(2) = 0,
%F A364334 a(n) = a(n-1) + 1 if n is an odd prime,
%F A364334 a(n) = max{a(k) : k|n, 1<k<n} otherwise.
%e A364334 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 A364334 And a(239)=3, since 239 is a prime number, and a(238)=2.
%t A364334 Nest[Function[list,
%t A364334   Module[{n = Length[list] + 1},
%t A364334    Append[list,
%t A364334     If[PrimeQ[n], Last[list] + 1,
%t A364334      Max[(list[[First[#]]]) & /@ FactorInteger[n]]]]]], {0, 0}, 110]//Rest
%Y A364334 For values at primes, see A364332.
%K A364334 nonn
%O A364334 2,6
%A A364334 _Steven Lu_, Jul 18 2023