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

 

Logo


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

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) oo=200; an=vector(oo);

a(n)=an[n];

for(n=2, oo, 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

CROSSREFS

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

Cf. A003313, A076142, A076091, A005245, A020639, A000079, A175125.

For records see A105017.

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 25 22:15 EDT 2017. Contains 288730 sequences.