A073933 -id:A073933 - cp's OEIS frontend

A334184 Irregular table read by rows: T(n,k) gives the number of values that can be reached after exactly k iterations of maps of the form (n - n/p) where p is a prime divisor of n. 0 <= k < A073933(n).

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2

Offset: 1

Peter Kagey, Apr 17 2020

Row lengths are given by A073933(n). Row sums are given by A332809(n). The maximum value in each row is given by A334144(n).
The n-th row consists of all 1's if and only if n is a power of two (A000079) or a Fermat prime (A019434).
Conjecture: rows are unimodal (increasing and then decreasing).
Not all rows are unimodal. Indices of rows that have terms that increase and decrease more than once are A334238. - Michael De Vlieger, Apr 18 2020

			For n = 15, the fifteenth row of this table is [1,2,3,2,1,1] because there is one value (15 itself) that can be reached with zero iterations of (n - n/p) maps, two values (10 and 12) that can be reached after one iteration, three values (5, 8, and 6) that can be reached after two iterations, and so on.
      15
     _/ \_
    /     \
  10       12
  | \_   _/ |
  |   \ /   |
  5    8    6
   \_  |  _/|
     \_|_/  |
       4    3
       |  _/
       |_/
       2
       |
       |
       1
Table begins:
1
1, 1
1, 1, 1
1, 1, 1
1, 1, 1, 1
1, 2, 1, 1
1, 1, 2, 1, 1
1, 1, 1, 1
1, 1, 2, 1, 1
1, 2, 1, 1, 1
1, 1, 2, 1, 1, 1
1, 2, 2, 1, 1
1, 1, 2, 2, 1, 1
1, 2, 2, 2, 1, 1
1, 2, 3, 2, 1, 1
1, 1, 1, 1, 1

Michael De Vlieger, Table of n, a(n) for n = 1..12386 (rows 1 <= n <= 1000, flattened)
Michael De Vlieger, Hasse diagrams showing rows n = {55, 63, 171, ...} that increase and decrease more than once.
Michael De Vlieger, Table of n, b(n) for n = 1..10000, encoding the running total of row n of this sequence as a binary number expressed decimally.

Cf. A001221, A073933, A332809, A333123, A334111, A334144, A334238.

Cf. A000079, A019434.

Table[Length@ Union@ # & /@ Transpose@ # &@ If[n == 1, {{1}}, NestWhile[If[Length[#] == 0, Map[{n, #} &, # - # /FactorInteger[#][[All, 1]] ], Union[Join @@ Map[Function[{w, n}, Map[Append[w, If[n == 0, 0, n - n/#]] &, FactorInteger[n][[All, 1]] ]] @@ {#, Last@ #} &, #]]] &, n, If[ListQ[#], AllTrue[#, Last[#] > 1 &], # > 1] &]], {n, 22}] // Flatten (* Michael De Vlieger, Apr 18 2020 *)

T(n,0) = T(n, A073933(n) - 2) = T(n, A073933(n) - 1) = 1.

T(n,1) = A001221(n) for n > 1.

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.

Original entry on oeis.org

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

A073934 Sum of terms in n-th row of triangle in A073932.

Original entry on oeis.org

1, 3, 6, 7, 12, 12, 19, 15, 21, 22, 33, 24, 37, 33, 37, 31, 48, 39, 58, 42, 54, 55, 78, 48, 67, 63, 66, 61, 90, 67, 98, 63, 88, 82, 96, 75, 112, 96, 102, 82, 123, 96, 139, 99, 112, 124, 171, 96, 145, 117, 133, 115, 168, 120, 154, 117, 153, 148, 207, 127, 188, 160

Offset: 1

Amarnath Murthy, Aug 19 2002

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A032742, A060681, A073932, A073933, A073935.

a[1] := 1:for i from 2 to 500 do n := i:s := n:while(n>1) do if isprime(n) then r := n-1: else r := n-n/ifactors(n)[2][1][1]; fi; n := r:s := s+n:od:a[i] := s:od:seq(a[k],k=1..500);

Array[If[# == 1, 1, Total@ NestWhileList[If[PrimeQ@ #, # - 1, # - #/FactorInteger[#][[1, 1]] ] &, #, # > 1 &]] &, 62]

(define (A073934 n) (if (= 1 n) n (+ n (A073934 (A060681 n)))))
(define (A060681 n) (- n (A032742 n))) ;; See also code under A032742
;; Antti Karttunen, Aug 23 2017

a(1) = 1; for n > 1, a(n) = n + a(A060681(n)). - Antti Karttunen, Aug 23 2017

More terms from Sascha Kurz, Aug 23 2002

Offset corrected from 0 to 1 by Antti Karttunen, Aug 23 2017

A073935 Numbers n such that the n-th row of triangle in A073932 contains exactly the divisors of n.

Original entry on oeis.org

1, 2, 4, 6, 8, 16, 18, 20, 32, 42, 54, 64, 100, 128, 162, 256, 272, 294, 342, 486, 500, 512, 1024, 1458, 1806, 2048, 2058, 2500, 4096, 4374, 4624, 6498, 8192, 10100, 12500, 13122, 14406, 16384, 26406, 32768, 39366, 62500, 65536, 65792, 77658

Offset: 1

Amarnath Murthy, Aug 19 2002

nonn

John Machacek, Egyptian Fractions and Prime Power Divisors, arXiv:1706.01008 [math.NT], 2017.

Cf. A073932, A073933, A073934, A283423.

More terms from Sascha Kurz, Aug 23 2002

Name clarified by Sean A. Irvine, Dec 28 2024

A073932 Define f(n) = n - largest nontrivial divisor of n or f(n) = n-1 if n is a prime [that is, f(n) = A060681(n)]. Form a triangle in which the n-th row contains terms n, f(n), f(f(n)), ... until a 1 is reached; sequence gives triangle read by rows.

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 4, 2, 1, 5, 4, 2, 1, 6, 3, 2, 1, 7, 6, 3, 2, 1, 8, 4, 2, 1, 9, 6, 3, 2, 1, 10, 5, 4, 2, 1, 11, 10, 5, 4, 2, 1, 12, 6, 3, 2, 1, 13, 12, 6, 3, 2, 1, 14, 7, 6, 3, 2, 1, 15, 10, 5, 4, 2, 1, 16, 8, 4, 2, 1, 17, 16, 8, 4, 2, 1, 18, 9, 6, 3, 2, 1, 19, 18, 9, 6, 3, 2, 1, 20, 10, 5, 4, 2, 1

Offset: 1

Amarnath Murthy, Aug 19 2002

			Triangle begins:
   1;
   2, 1;
   3, 2, 1;
   4, 2, 1;
   5, 4, 2, 1;
   6, 3, 2, 1;
   7, 6, 3, 2, 1;
   8, 4, 2, 1;
   9, 6, 3, 2, 1;
  10, 5, 4, 2, 1;

Michael De Vlieger, Table of n, a(n) for n = 1..12386 (rows 1 <= n <= 1000, flattened)
John Machacek, Egyptian Fractions and Prime Power Divisors, Journal of Integer Sequences, Vol. 21 (2018), Article 18.3.7.

Cf. A032742, A060681, A073933, A073934, A073935.

j := 1:a[1] := 1:for i from 2 to 50 do n := i:j := j+1:a[j] := n:while(n>1) do if isprime(n) then r := n-1: else r := n-n/ifactors(n)[2][1][1]; fi; n := r:j := j+1:a[j] := n: od:od:seq(a[k],k=1..j);

Array[If[# == 1, {1}, NestWhileList[If[PrimeQ@ #, # - 1, # - #/FactorInteger[#][[1, 1]] ] &, #, # > 1 &]] &, 20] // Flatten  (* Michael De Vlieger, Apr 15 2020 *)

More terms from Sascha Kurz, Aug 23 2002

Offset corrected from 0 to 1 by Antti Karttunen, Aug 23 2017

A307723 Naturally ordered prime factorization of n as a quasi-logarithmic word over the binary alphabet {1,0}.

Original entry on oeis.org

10, 1100, 1010, 110100, 101100, 11011000, 101010, 11001100, 10110100, 1101101000, 10110010, 1101100100, 1011011000, 1100110100, 10101010, 1101010100, 1011001100, 110110011000, 1010110100, 110011011000

Offset: 2

I. V. Serov, Apr 24 2019

Let m(n) be the number of digits (letters) in a(n).
m(n) = 2*A064097(n) = 2*(A073933(n)-1).
Split the word a(n) into two parts of equal length. The number of 1's in the left part equals the number of 0's in the right part and vice versa.

			The sequence begins:
   n a(n)
  -- -----------
   1
   2 10
   3 1100
   4 1010
   5 110100
   6 101100
   7 11011000
   8 101010
   9 11001100
  10 10110100
  11 1101101000
  12 10110010
  ...

I. V. Serov, Table of n, a(n) for n = 2..10000

Cf. A010051, A088387, A307641, A307746, A064097, A073933.

a(1) is empty.
a(n) = concatenation(1, a(n-1), 0) if n is prime.
a(n) = concatenation_{k=1..A001222(n)} a(A307746(n,k)) if n is composite.
a(n) = concatenation(a(n/A088387(n)), a(A088387(n))) if n is composite.

A074093 Number of values of k such that n = k - largest divisor of k (

Original entry on oeis.org

1, 2, 1, 2, 1, 3, 1, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 4, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 4, 1, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 4, 1, 1, 1

Offset: 1

Amarnath Murthy, Aug 19 2002

nonn

			a(6) = 3 and the three values of k are 7,9 and 12.

Antti Karttunen, Table of n, a(n) for n = 1..100000

Cf. A073932, A073933, A073934, A073935, A060681.

f1[n_] := Count[Range[n, 2 n], ?(Differences[Take[Divisors[#], -2]] == {n} &)]; Join[{1}, Table[f1[n], {n, 2, 105}]] (* _Jayanta Basu, Jul 30 2013 *)

a(n)=sum(k=2,2*n,if(k- component(divisors(k),numdiv(k)-1)-n,0,1))

a(2n+1)=1; sum(k=1, n, a(k)) seems to be asymptotic to C*n with C=1.6... - Benoit Cloitre, Aug 21 2002

More terms from Benoit Cloitre and Vladeta Jovovic, Aug 21 2002

cp's OEIS Frontend

A334184 Irregular table read by rows: T(n,k) gives the number of values that can be reached after exactly k iterations of maps of the form (n - n/p) where p is a prime divisor of n. 0 <= k < A073933(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A073934 Sum of terms in n-th row of triangle in A073932.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Scheme

Formula

Extensions

A073935 Numbers n such that the n-th row of triangle in A073932 contains exactly the divisors of n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A073932 Define f(n) = n - largest nontrivial divisor of n or f(n) = n-1 if n is a prime [that is, f(n) = A060681(n)]. Form a triangle in which the n-th row contains terms n, f(n), f(f(n)), ... until a 1 is reached; sequence gives triangle read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A307723 Naturally ordered prime factorization of n as a quasi-logarithmic word over the binary alphabet {1,0}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A074093 Number of values of k such that n = k - largest divisor of k (

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions