login
This site is supported by donations to The OEIS Foundation.

 

Logo

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]-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.

License Agreements, Terms of Use, Privacy Policy. .

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