A334200 -id:A334200 - cp's OEIS frontend

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.

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

Offset: 1

Thomas Schulze (jazariel(AT)tiscalenet.it), Sep 16 2001

nonn

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 Mathematics Stack Exchange 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)
a(n) is the number of iterations r->A060681(r) to reach 1 starting at r=n. - R. J. Mathar, Nov 06 2023

			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)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Passawan Noppakaew and Prapanpong Pongsriiam, Product of Some Polynomials and Arithmetic Functions, J. Int. Seq. (2023) Vol. 26, Art. 23.9.1.
Hugo Pfoertner, Addition chains
Mathematics Stack Exchange, Does a graded poset on the positive integers generated from subtracting factors define a lattice?
Wikipedia, Addition chain

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.

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

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
# alternative which can be even used outside this entry
A064097 := proc(n)
        option remember ;
        add((1+procname(i[1]-1))*i[2], i=ifactors(n)[2]) ;
end proc:
seq(A064097(n),n=1..100) ; # R. J. Mathar, Aug 07 2022

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 *)
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[1] = 0; Array[a, 100]  (* Robert G. Wilson v, Mar 03 2020 *)

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)", "))

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

(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

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

More terms from Michael Somos, Sep 25 2001

A352957 Triangle read by rows: Row n is the lexicographically earliest strictly monotonic completely additive sequence of length n.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 0, 2, 3, 4, 0, 2, 3, 4, 5, 0, 3, 5, 6, 7, 8, 0, 3, 5, 6, 7, 8, 9, 0, 4, 6, 8, 9, 10, 11, 12, 0, 5, 8, 10, 11, 13, 14, 15, 16, 0, 5, 8, 10, 12, 13, 14, 15, 16, 17, 0, 5, 8, 10, 12, 13, 14, 15, 16, 17, 18, 0, 7, 11, 14, 16, 18, 19, 21, 22, 23, 24, 25

Offset: 1

Peter Munn, Apr 11 2022

Each sequence consists of nonnegative integers indexed from 1.
Note in particular in the formula section, the lower bound, floor(n/k), for first differences between terms in a row. This follows (using the additive property) from the strict monotonicity of floor(n/k)+1 consecutive terms near the end of the row.
For any k, with increasing length n >= k, the first k terms of the sequences approach similarity with a real-valued logarithmic function defined on the integers. For example, the asymptote of T(n,3)/T(n,2) is log(3)/log(2), A020857.

			(For row 4.) A completely additive sequence requires T(4,1) = 0. Strict monotonicity requires T(4,4) > T(4,3) > T(4,2). So T(4,4) >= T(4,2) + 2. Using the additivity this becomes T(4,2) + T(4,2) >= T(4,2) + T(4,1) + 2. Subtracting T(4,2) and substituting 0 for T(4,1) we get T(4,2) >= 2. So from T(4,4) > T(4,3) > T(4,2), we see T(4,3) >= 3, T(4,4) >= 4. So row 4 = (0, 2, 3, 4) as it is strictly monotonic and completely additive and from the preceding arguments is seen to be the lexicographically earliest such.
Triangle starts:
0;
0, 1;
0, 1,  2;
0, 2,  3,  4;
0, 2,  3,  4,  5;
0, 3,  5,  6,  7,  8;
0, 3,  5,  6,  7,  8,  9;
0, 4,  6,  8,  9, 10, 11, 12;
0, 5,  8, 10, 11, 13, 14, 15, 16;
0, 5,  8, 10, 12, 13, 14, 15, 16, 17;
0, 5,  8, 10, 12, 13, 14, 15, 16, 17, 18;
0, 7, 11, 14, 16, 18, 19, 21, 22, 23, 24, 25;
0, 7, 11, 14, 16, 18, 19, 21, 22, 23, 24, 25, 26;
0, 7, 11, 14, 16, 18, 20, 21, 22, 23, 24, 25, 26, 27;
0, 8, 13, 16, 19, 21, 23, 24, 26, 27, 28, 29, 30, 31, 32;
0, 9, 14, 18, 21, 23, 25, 27, 28, 30, 31, 32, 33, 34, 35, 36;

Peter Munn, Rows n = 1..141, flattened
Encyclopedia of Mathematics, Additive arithmetic function.
Peter Munn, PARI program

Cf. A020857.
Completely additive sequences, s, with primes p mapped to a function of s(p-1) and maybe s(p+1): A064097, A344443, A344444; and for functions of earlier terms, see A334200.
For completely additive sequences with primes p mapped to a function of p, see A001414.
For completely additive sequences with prime(k) mapped to a function of k, see A104244.
For completely additive sequences where some primes are mapped to 1, the rest to 0 (notably, some ruler functions) see the cross-references in A249344.

The definition specifies: T(n,j*k) = T(n,j) + T(n,k); for k > 1, T(n,k) > T(n,k-1).
T(n,1) = 0, otherwise T(n,k) >= T(n,k-1) + floor(n/k).
For prime p, T(p,p) = T(p-1,p-1) + 1, otherwise T(p,k) = T(p-1,k).
T(n,2) >= 2*floor(n/4) + floor(n/9).
T(n,3) >= ceiling( (3*T(n,2) + floor(n/9)) / 2).
T(11,k) = A344443(k).
For k <> 13, T(23,k) = A344444(k).

cp's OEIS Frontend

A334199 a(n) is the first occurrence of n in A334200.

Views

Author

Keywords

Comments

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Scheme

Formula

Extensions

A352957 Triangle read by rows: Row n is the lexicographically earliest strictly monotonic completely additive sequence of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A334206 Fully additive with a(p) = 1 + a(A014682(p)) when p is prime and a(n*m) = a(n) + a(m) when m,n > 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI