cp's OEIS Frontend

A061373 "Natural" logarithm, defined inductively by a(1)=1, a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if n, m>1.

%I A061373 #32 Dec 21 2021 23:37:20
%S A061373 1,2,3,4,5,5,6,6,6,7,8,7,8,8,8,8,9,8,9,9,9,10,11,9,10,10,9,10,11,10,
%T A061373 11,10,11,11,11,10,11,11,11,11,12,11,12,12,11,13,14,11,12,12,12,12,13,
%U A061373 11,13,12,12,13,14,12,13,13,12,12,13,13,14,13,14,13,14,12,13,13,13,13,14
%N A061373 "Natural" logarithm, defined inductively by a(1)=1, a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if n, m>1.
%C A061373 Related to A005245, the complexity of n, which is <= this sequence. They are equal up to term a(46) and for 771 values out of the first 1000 terms. A061373 is easier to compute.
%C A061373 a(A182061(n)) = n and a(m) < n for m < A182061(n). [_Reinhard Zumkeller_, Apr 09 2012]
%H A061373 T. D. Noe, <a href="/A061373/b061373.txt">Table of n, a(n) for n = 1..10000</a>
%H A061373 J. Arias de Reyna, <a href="http://gaceta.rsme.es/vernumero.php?id=28">Complejidad de los numeros naturales</a>, Gaceta de la Real Sociedad Matematica Espanola, 3, (2000), 230-250. (In Spanish.)
%H A061373 J. Arias de Reyna, <a href="/A061373/a061373.pdf">Complejidad de los numeros naturales</a>, Gaceta de la Real Sociedad Matematica Espanola, 3, (2000), 230-250. (In Spanish.) [Cached copy, with permission]
%H A061373 J. Arias de Reyna, <a href="https://arxiv.org/abs/2111.03345">Complexity of natural numbers</a>, arXiv:2111.03345 [math.NT], 2021.
%t A061373 a[1]=1; a[p_?PrimeQ] := 1+a[p-1]; a[n_] := a[n] = With[{d=Divisors[n][[2]] }, a[d] + a[n/d]]; Array[a, 100] (* _Jean-François Alcover_, Feb 26 2016 *)
%o A061373 (Haskell)
%o A061373 import Data.List (genericIndex)
%o A061373 a061373 1 = 1
%o A061373 a061373 n = genericIndex a061373_list (n-1)
%o A061373 a061373_list = 1 : f 2 where
%o A061373    f x | x == spf  = 1 + a061373 (spf - 1) : f (x + 1)
%o A061373        | otherwise = a061373 spf + a061373 (x `div` spf) : f (x + 1)
%o A061373        where spf = a020639 x
%o A061373 -- _Reinhard Zumkeller_, Apr 09 2012
%Y A061373 Cf. A005245.
%Y A061373 Cf. A020639.
%K A061373 easy,nice,nonn
%O A061373 1,2
%A A061373 _Juan Arias-de-Reyna_, Jun 08 2001