This site is supported by donations to The OEIS Foundation.

 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]-1))*i[2], i=ifactors(n)[2])     end: seq(a(n), n=1..120);  # Alois P. Heinz, Apr 26 2019 MATHEMATICA quasiLog := (Length@NestWhileList[# - Divisors[#][[-2]] &, #, # > 1 &] - 1) &; quasiLog /@ Range[1024] (* Terentyev Oleg, Jul 17 2011 *) 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 *) 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 October 18 04:46 EDT 2019. Contains 328145 sequences. (Running on oeis4.)