login
A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n > 1.
48

%I #124 Nov 17 2023 11:51:35

%S 0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,7,5,6,6,6,6,7,6,7,5,7,6,

%T 7,6,7,7,7,6,7,7,8,7,7,8,9,6,8,7,7,7,8,7,8,7,8,8,9,7,8,8,8,6,8,8,9,7,

%U 9,8,9,7,8,8,8,8,9,8,9,7,8,8,9,8,8,9,9,8,9,8,9,9,9,10,9,7,8,9,9,8,9,8,9,8

%N A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n > 1.

%C Note that this is the logarithm of a completely multiplicative function. - _Michael Somos_

%C Number of iterations of r -> r - (largest divisor d < r) needed to reach 1 starting at r = n. a(n) = a(n - A032742(n)) + 1 for n >= 2. - _Jaroslav Krizek_, Jan 28 2010

%C From _Antti Karttunen_, Apr 04 2020: (Start)

%C Krizek's comment above stems from the fact that n - n/p = (p-1)*(n/p), where p is the least prime dividing n [= A020639(n), thus n/p = A032742(n)] and because this is fully additive sequence we can write a(n) = a(p) + a(n/p) = (1+a(p-1)) + a(n/p) = 1 + a((p-1)*(n/p)) = 1 + a(n - n/p), for any composite n.

%C Note that in above formula p can be any prime factor of n, not only the smallest, which proves _Robert G. Wilson v_'s comment in A333123 that all such iteration paths from n to 1 are of the same length, regardless of the route taken.

%C (End)

%C From _Antti Karttunen_, May 11 2020: (Start)

%C Moreover, those paths form the chains of a graded poset, which is also a lattice. See the Mathematics Stack Exchange link.

%C Keeping the formula otherwise same, but changing it for primes either as a(p) = 1 + a(A064989(p)), a(p) = 1 + a(floor(p/2)) or a(p) = 1 + a(A048673(p)) gives sequences A056239, A064415 and A334200 respectively.

%C (End)

%C a(n) is the number of iterations r->A060681(r) to reach 1 starting at r=n. - _R. J. Mathar_, Nov 06 2023

%H Reinhard Zumkeller, <a href="/A064097/b064097.txt">Table of n, a(n) for n = 1..10000</a>

%H Passawan Noppakaew and Prapanpong Pongsriiam, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Pongsriiam/pong43.html">Product of Some Polynomials and Arithmetic Functions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.9.1.

%H Hugo Pfoertner, <a href="/A003313/a003313.txt">Addition chains</a>

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/a/3640072/121988">Does a graded poset on the positive integers generated from subtracting factors define a lattice?</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Addition_chain">Addition chain</a>

%F Conjectures: for n>1, log(n) < a(n) < (5/2)*log(n); lim n ->infinity sum(k=1, n, a(k))/(n*log(n)-n) = C = 1.8(4)... - _Benoit Cloitre_, Oct 30 2002

%F Conjecture: for n>1, floor(log_2(n)) <= a(n) < (5/2)*log(n). - _Robert G. Wilson v_, Aug 10 2013

%F a(n) = Sum_{k=1..n} a(p_k)*e_k if n is composite with factorization p_1^e_1 * ... * p_k^e_k. - _Orson R. L. Peters_, May 10 2016

%F From _Antti Karttunen_, Aug 23 2017: (Start)

%F a(1) = 0; for n > 1, a(n) = 1 + a(A060681(n)). [From _Jaroslav Krizek_'s Jan 28 2010 formula in comments.]

%F a(n) = A073933(n) - 1. (End)

%F a(n) = A064415(n) + A329697(n) [= A054725(n) + A329697(n), for n > 1]. - _Antti Karttunen_, Apr 16 2020

%F a(n) = A323077(n) + A334202(n) = a(A052126(n)) + a(A006530(n)). - _Antti Karttunen_, May 12 2020

%e a(19) = 6: 19 - 1 = 18; 18 - 9 = 9; 9 - 3 = 6; 6 - 3 = 3; 3 - 1 = 2; 2 - 1 = 1. That is a total of 6 iterations. - _Jaroslav Krizek_, Jan 28 2010

%e From _Antti Karttunen_, Apr 04 2020: (Start)

%e We can follow also alternative routes, where we do not always select the largest proper divisor to subtract, for example, from 19 to 1, we could go as:

%e 19-1 = 18; 18-(18/3) = 12; 12-(12/2) = 6; 6-(6/3) = 4; 4-(4/2) = 2; 2-(2/2) = 1, or as

%e 19-1 = 18; 18-(18/3) = 12; 12-(12/3) = 8; 8-(8/2) = 4; 4-(4/2) = 2; 2-(2/2) = 1,

%e both of which also have exactly 6 iterations.

%e (End)

%p a:= proc(n) option remember;

%p add((1+a(i[1]-1))*i[2], i=ifactors(n)[2])

%p end:

%p seq(a(n), n=1..120); # _Alois P. Heinz_, Apr 26 2019

%p # alternative which can be even used outside this entry

%p A064097 := proc(n)

%p option remember ;

%p add((1+procname(i[1]-1))*i[2], i=ifactors(n)[2]) ;

%p end proc:

%p seq(A064097(n),n=1..100) ; # _R. J. Mathar_, Aug 07 2022

%t quasiLog := (Length@NestWhileList[# - Divisors[#][[-2]] &, #, # > 1 &] - 1) &;

%t quasiLog /@ Range[1024]

%t (* _Terentyev Oleg_, Jul 17 2011 *)

%t fi[n_] := Flatten[ Table[#[[1]], {#[[2]]}] & /@ FactorInteger@ n]; a[1] = 0; a[n_] := If[ PrimeQ@ n, a[n - 1] + 1, Plus @@ (a@# & /@ fi@ n)]; Array[a, 105] (* _Robert G. Wilson v_, Jul 17 2013 *)

%t a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[1, 1]] &, n, # != 1 &] - 1; Array[a, 100] (* or *)

%t a[n_] := a[n - n/FactorInteger[n][[1, 1]]] +1; a[1] = 0; Array[a, 100] (* _Robert G. Wilson v_, Mar 03 2020 *)

%o (PARI) NN=200; an=vector(NN);

%o a(n)=an[n];

%o for(n=2,NN,an[n]=if(isprime(n),1+a(n-1), sumdiv(n,p, if(isprime(p),a(p)*valuation(n,p)))));

%o for(n=1,100,print1(a(n)", "))

%o (PARI) a(n)=if(isprime(n), return(a(n-1)+1)); if(n==1, return(0)); my(f=factor(n)); apply(a,f[,1])~ * f[,2] \\ _Charles R Greathouse IV_, May 10 2016

%o (Haskell)

%o import Data.List (genericIndex)

%o a064097 n = genericIndex a064097_list (n-1)

%o a064097_list = 0 : f 2 where

%o f x | x == spf = 1 + a064097 (spf - 1) : f (x + 1)

%o | otherwise = a064097 spf + a064097 (x `div` spf) : f (x + 1)

%o where spf = a020639 x

%o -- _Reinhard Zumkeller_, Mar 08 2013

%o (Scheme)

%o (define (A064097 n) (if (= 1 n) 0 (+ 1 (A064097 (A060681 n))))) ;; After _Jaroslav Krizek_'s Jan 28 2010 formula.

%o (define (A060681 n) (- n (A032742 n))) ;; See also code under A032742.

%o ;; _Antti Karttunen_, Aug 23 2017

%Y Similar to A061373 which uses the same recurrence relation but a(1) = 1.

%Y Cf. A003313, A005245, A020639, A032742, A052126, A054725, A060681, A064415, A073933, A076142, A076091, A175125, A256653, A307742, A323076, A323077, A329697, A333123, A334200, A334202, A334203, and array A334111.

%Y Cf. A000079 (position of last occurrence), A105017 (position of records), A334197 (positions of record jumps upward).

%Y Partial sums of A334090.

%Y Cf. also A056239.

%K nonn

%O 1,3

%A Thomas Schulze (jazariel(AT)tiscalenet.it), Sep 16 2001

%E More terms from _Michael Somos_, Sep 25 2001