This site is supported by donations to The OEIS Foundation. Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing. Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A064097 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. 19
 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, 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, 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Note that this is the logarithm of a completely multiplicative function. - Michael Somos Number of steps of iterations of {r - (largest divisor d < r)} needed to reach 1 starting at r = n. Example (a(19) = 6): 19 - 1 = 18; 18 - 9 = 9; 9 - 3 = 6; 6 - 3 = 3; 3 - 1 = 2; 2 - 1 = 1; iterations has 6 steps. a(n) = a(n - A032472(n)) + 1 for n >= 2. - Jaroslav Krizek, Jan 28 2010 LINKS Reinhard Zumkeller, Table of n, a(n) for n = 1..10000 Hugo Pfoertner, Addition chains FORMULA 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 Conjecture: for n>1, floor(log_2(n)) <= a(n) < (5/2)*log(n). - Robert G. Wilson v, Aug 10 2013 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 From Antti Karttunen, Aug 23 2017: (Start) a(1) = 0; for n > 1, a(n) = 1 + a(A060681(n)). [From Jaroslav Krizek's Jan 28 2010 formula in comments.] a(n) = A073933(n) - 1. (End) MAPLE a:= proc(n) option remember;       add((1+a(i-1))*i, i=ifactors(n))     end: seq(a(n), n=1..120);  # Alois P. Heinz, Apr 26 2019 MATHEMATICA quasiLog := (Length@NestWhileList[# - Divisors[#][[-2]] &, #, # > 1 &] - 1) &; quasiLog /@ Range (* Terentyev Oleg, Jul 17 2011 *) fi[n_] := Flatten[ Table[#[], {#[]}] & /@ FactorInteger@ n]; a = 0; a[n_] := If[ PrimeQ@ n, a[n - 1] + 1, Plus @@ (a@# & /@ fi@ n)]; Array[a, 105] (* Robert G. Wilson v, Jul 17 2013 *) PROG (PARI) NN=200; an=vector(NN); a(n)=an[n]; for(n=2, NN, an[n]=if(isprime(n), 1+a(n-1), sumdiv(n, p, if(isprime(p), a(p)*valuation(n, p))))); for(n=1, 100, print1(a(n)", ")) (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 (Haskell) import Data.List (genericIndex) a064097 n = genericIndex a064097_list (n-1) a064097_list = 0 : f 2 where    f x | x == spf  = 1 + a064097 (spf - 1) : f (x + 1)        | otherwise = a064097 spf + a064097 (x `div` spf) : f (x + 1)        where spf = a020639 x -- Reinhard Zumkeller, Mar 08 2013 (Scheme) (define (A064097 n) (if (= 1 n) 0 (+ 1 (A064097 (A060681 n))))) ;; After Jaroslav Krizek's Jan 28 2010 formula. (define (A060681 n) (- n (A032742 n))) ;; See also code under A032742. ;; Antti Karttunen, Aug 23 2017 CROSSREFS Similar to A061373 which uses the same recurrence relation but a(1) = 1. Cf. A000079, A003313, A005245, A020639, A032742, A060681, A076142, A076091, A175125. For records see A105017. One less than A073933. Sequence in context: A277608 A117497 A117498 * A014701 A207034 A226164 Adjacent sequences:  A064094 A064095 A064096 * A064098 A064099 A064100 KEYWORD nonn AUTHOR Thomas Schulze (jazariel(AT)tiscalenet.it), Sep 16 2001 EXTENSIONS More terms from Michael Somos, Sep 25 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 11 12:33 EST 2019. Contains 329916 sequences. (Running on oeis4.)