The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 40
 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 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 From Antti Karttunen, Apr 04 2020: (Start) 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. 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. (End) From Antti Karttunen, May 11 2020: (Start) Moreover, those paths form the chains of a graded poset, which is also a lattice. See the Math Stackexchange link. 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. (End) LINKS Reinhard Zumkeller, Table of n, a(n) for n = 1..10000 Hugo Pfoertner, Addition chains Wikipedia, Addition chain 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) a(n) = A064415(n) + A329697(n) [= A054725(n) + A329697(n), for n > 1]. - Antti Karttunen, Apr 16 2020 a(n) = A323077(n) + A334202(n) = a(A052126(n)) + a(A006530(n)). - Antti Karttunen, May 12 2020 EXAMPLE 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 From Antti Karttunen, Apr 04 2020: (Start) 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: 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 19-1 = 18; 18-(18/3) = 12; 12-(12/3) = 8; 8-(8/2) = 4; 4-(4/2) = 2; 2-(2/2) = 1, both of which also have exactly 6 iterations. (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 *) a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[1, 1]] &, n, # != 1 &] - 1; Array[a, 100] (* or *) a[n_] := a[n - n/FactorInteger[n][[1, 1]]] +1; a = 0; Array[a, 100]  (* Robert G. Wilson v, Mar 03 2020 *) 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. A003313, A005245, A020639, A032742, A052126, A054725, A060681, A064415, A073933, A076142, A076091, A175125, A256653, A307742, A323076, A323077, A329697, A333123, A334200, A334202, A334203, and array A334111. Cf. A000079 (position of last occurrence), A105017 (position of records), A334197 (positions of record jumps upward). Partial sums of A334090. Cf. also A056239. 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 July 25 16:03 EDT 2021. Contains 346291 sequences. (Running on oeis4.)