A332993 -id:A332993 - cp's OEIS frontend

A333783 a(n) = sigma(n) - A332993(n).

0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 6, 0, 2, 3, 0, 0, 8, 0, 6, 3, 2, 0, 14, 0, 2, 0, 6, 0, 21, 0, 0, 3, 2, 5, 24, 0, 2, 3, 14, 0, 25, 0, 6, 12, 2, 0, 30, 0, 12, 3, 6, 0, 26, 5, 14, 3, 2, 0, 57, 0, 2, 12, 0, 5, 33, 0, 6, 3, 31, 0, 56, 0, 2, 18, 6, 7, 37, 0, 30, 0, 2, 0, 69, 5, 2, 3, 14, 0, 78, 7, 6, 3, 2, 5, 62, 0, 16, 12

Offset: 1

Antti Karttunen, Apr 05 2020

Sum of all other divisors of n, except those divisors that can be obtained by repeatedly taking the largest proper divisor (of previous such divisor, starting from n), up to and including the terminal 1.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences related to sigma(n)

Cf. A000203, A000961 (positions of zeros), A001065, A006022, A032742, A332993, A333784, A333791.

A332993(n) = if(1==n,n,n + A332993(n/vecmin(factor(n)[,1])));
A333783(n) = (sigma(n) - A332993(n));

a(n) = A000203(n) - A332993(n).
a(n) = A001065(n) - A006022(n).
a(n) = A333784(n) - A333791(n).

A333791 Difference of sums of two subsets of divisors of n, those obtained by repeatedly dividing with the smallest remaining prime factor (A332993) and those obtained by repeatedly dividing with the largest remaining prime factor (A332994).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0, 3, 0, 5, 2, 0, 0, 4, 0, 9, 4, 9, 0, 7, 0, 11, 0, 15, 0, 12, 0, 0, 8, 15, 2, 12, 0, 17, 10, 21, 0, 20, 0, 27, 8, 21, 0, 15, 0, 18, 14, 33, 0, 13, 6, 35, 16, 27, 0, 32, 0, 29, 16, 0, 8, 36, 0, 45, 20, 30, 0, 28, 0, 35, 12, 51, 4, 44, 0, 45, 0, 39, 0, 52, 12, 41, 26, 63, 0, 39, 6, 63, 28, 45, 14, 31

Offset: 1

Antti Karttunen, Apr 05 2020

nonn

			For n = 12 = 2*2*3, we obtain the A332993(12) = 22 as 12 + 12/2 + 6/2 + 3/3 = 12+6+3+1, and A332994(12) = 19 as 12 + 12/3 + 4/2 + 2/2 = 12+4+2+1, thus a(12) = 22 - 19 = 3.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A000961 (positions of zeros), A006022, A032742, A052126, A322382, A332993, A332994, A333783, A333784.

A332993(n) = if(1==n,n,n + A332993(n/vecmin(factor(n)[,1])));
A332994(n) = if(1==n,n,n + A332994(n/vecmax(factor(n)[,1])));
A333791(n) = (A332993(n)-A332994(n));

a(n) = A332993(n) - A332994(n).
a(n) = A333784(n) - A333783(n).
a(n) = A006022(n) - A322382(n).
a(p^k) = 0, for all primes p and exponents k >= 0.

A348978 Numerator of ratio A332993(n) / sigma(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 5, 1, 1, 1, 8, 1, 11, 1, 11, 7, 1, 1, 31, 1, 6, 29, 17, 1, 23, 1, 20, 1, 25, 1, 17, 1, 1, 15, 26, 43, 67, 1, 29, 53, 38, 1, 71, 1, 13, 11, 35, 1, 47, 1, 27, 23, 46, 1, 47, 67, 53, 77, 44, 1, 37, 1, 47, 23, 1, 79, 37, 1, 20, 31, 113, 1, 139, 1, 56, 53, 67, 89, 131, 1, 26, 1, 62, 1, 155, 103, 65, 39, 83

Offset: 1

Antti Karttunen, Nov 06 2021

Ratio A332993(n) / sigma(n) tells how large proportion of the divisor sum we obtain if we sum just those divisors of n that can be obtained by repeatedly taking the largest proper divisor (of previous such divisor, starting from n, which is included in the sum), up to and including the terminal 1. Pair a(n) / A348979(n) shows the ratio in the lowest terms: 1/1, 1/1, 1/1, 1/1, 1/1, 5/6, 1/1, 1/1, 1/1, 8/9, 1/1, 11/14, 1/1, 11/12, 7/8, 1/1, 1/1, 31/39, 1/1, 6/7, 29/32, 17/18, 1/1, 23/30, etc. The ratio is 1 for all powers of primes (A000961).

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to sigma(n)

Cf. A000203, A000961, A332993, A333783, A348977, A348979 (denominators).

Cf. also A348988, A348989.

f[n_] := n/FactorInteger[n][[1, 1]]; g[1] = 1; g[n_] := g[n] = n + g[f[n]]; a[n_] := Numerator[g[n]/DivisorSigma[1, n]]; Array[a, 100] (* Amiram Eldar, Nov 06 2021 *)

A332993(n) = if(1==n,n,n + A332993(n/vecmin(factor(n)[,1])));
A348978(n) = { my(u=A332993(n)); (u/gcd(sigma(n), u)); };

a(n) = A332993(n) / A348977(n) = A332993(n) / gcd(A000203(n), A332993(n)).

A348977 a(n) = gcd(sigma(n), A332993(n)).

Original entry on oeis.org

1, 3, 4, 7, 6, 2, 8, 15, 13, 2, 12, 2, 14, 2, 3, 31, 18, 1, 20, 6, 1, 2, 24, 2, 31, 2, 40, 2, 30, 3, 32, 63, 3, 2, 1, 1, 38, 2, 1, 2, 42, 1, 44, 6, 6, 2, 48, 2, 57, 3, 3, 2, 54, 2, 1, 2, 1, 2, 60, 3, 62, 2, 4, 127, 1, 3, 68, 6, 3, 1, 72, 1, 74, 2, 2, 2, 1, 1, 80, 6, 121, 2, 84, 1, 1, 2, 3, 2, 90, 78, 7, 6, 1, 2, 5

Offset: 1

Antti Karttunen, Nov 06 2021

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to sigma(n)

Cf. A000203, A332993, A333783, A348978, A348979.

Cf. also A348987.

f[n_] := n/FactorInteger[n][[1, 1]]; g[1] = 1; g[n_] := g[n] = n + g[f[n]]; a[n_] := GCD[g[n], DivisorSigma[1, n]]; Array[a, 100] (* Amiram Eldar, Nov 06 2021 *)

A332993(n) = if(1==n,n,n + A332993(n/vecmin(factor(n)[,1])));
A348977(n) = gcd(sigma(n), A332993(n));

a(n) = gcd(A000203(n), A332993(n)).
a(n) = gcd(A000203(n), A333783(n)) = gcd(A332993(n), A333783(n)).
a(n) = A332993(n) / A348978(n) = A000203(n) / A348979(n).

A348979 Denominator of ratio A332993(n) / sigma(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 6, 1, 1, 1, 9, 1, 14, 1, 12, 8, 1, 1, 39, 1, 7, 32, 18, 1, 30, 1, 21, 1, 28, 1, 24, 1, 1, 16, 27, 48, 91, 1, 30, 56, 45, 1, 96, 1, 14, 13, 36, 1, 62, 1, 31, 24, 49, 1, 60, 72, 60, 80, 45, 1, 56, 1, 48, 26, 1, 84, 48, 1, 21, 32, 144, 1, 195, 1, 57, 62, 70, 96, 168, 1, 31, 1, 63, 1, 224, 108, 66, 40, 90

Offset: 1

Antti Karttunen, Nov 06 2021

See comments in A348978.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to sigma(n)

Cf. A000203, A332993, A333783, A348977, A348978 (numerators).

Cf. also A348988, A348989.

f[n_] := n/FactorInteger[n][[1, 1]]; g[1] = 1; g[n_] := g[n] = n + g[f[n]]; a[n_] := Denominator[g[n]/DivisorSigma[1, n]]; Array[a, 100] (* Amiram Eldar, Nov 06 2021 *)

A332993(n) = if(1==n,n,n + A332993(n/vecmin(factor(n)[,1])));
A348979(n) = { my(s=sigma(n)); (s/gcd(s, A332993(n))); };

a(n) = A000203(n) / A348977(n) = A000203(n) / gcd(A000203(n), A332993(n)).

A378523 Dirichlet inverse of A332993, where A332993 is defined as a(1) = 1, and for n > 1, a(n) = n + a(A032742(n)), and A032742 is the largest proper divisor.

Original entry on oeis.org

1, -3, -4, 2, -6, 14, -8, 0, 3, 20, -12, -14, -14, 26, 27, 0, -18, -17, -20, -18, 35, 38, -24, 4, 5, 44, 0, -22, -30, -109, -32, 0, 51, 56, 53, 34, -38, 62, 59, 4, -42, -137, -44, -30, -30, 74, -48, 0, 7, -27, 75, -34, -54, 6, 77, 4, 83, 92, -60, 146, -62, 98, -36, 0, 89, -193, -68, -42, 99, -199, -72, -28, -74, 116

Offset: 1

Antti Karttunen, Nov 30 2024

sign

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

Cf. A032742, A332993.

Cf. also A378524.

A332993(n) = if(1==n,n,n + A332993(n/vecmin(factor(n)[,1])));
memoA378523 = Map();
A378523(n) = if(1==n,1,my(v); if(mapisdefined(memoA378523,n,&v), v, v = -sumdiv(n,d,if(dA332993(n/d)*A378523(d),0)); mapput(memoA378523,n,v); (v)));

a(1) = 1, and for n > 1, a(n) = -Sum_{d|n, dA332993(n/d) * a(d).

A006022 Sprague-Grundy (or Nim) values for the game of Maundy cake on an n X 1 sheet.

Original entry on oeis.org

0, 1, 1, 3, 1, 4, 1, 7, 4, 6, 1, 10, 1, 8, 6, 15, 1, 13, 1, 16, 8, 12, 1, 22, 6, 14, 13, 22, 1, 21, 1, 31, 12, 18, 8, 31, 1, 20, 14, 36, 1, 29, 1, 34, 21, 24, 1, 46, 8, 31, 18, 40, 1, 40, 12, 50, 20, 30, 1, 51, 1, 32, 29, 63, 14, 45, 1, 52, 24, 43, 1, 67, 1, 38, 31, 58, 12, 53, 1

Offset: 1

N. J. A. Sloane

nonn

There are three equivalent formulas for a(n). Suppose n >= 2, and let p1 <= p2 <= ... <= pk be the prime factors of n, with repetition.
Theorem 1: a(1) = 0. For n >= 2, a(n) = n*s(n), where
s(n) = 1/p1 + 1/(p1*p2) + 1/(p1*p2*p3) + ... + 1/(p1*p2*...*pk).
This is implicit in Berlekamp, Conway and Guy, Winning Ways, 2 vols., 1982, pp. 28, 53.
Note that s(n) = A322034(n) / A322035(n).
David James Sycamore observed on Nov 24 2018 that Theorem 1 implies a(n) < n for all n (see comments in A322034), and also leads to a simple recurrence for a(n):
Theorem 2: a(1) = 0. For n >= 2, a(n) = p*a(n/p) + 1, where p is the largest prime factor of n.
Proof. (Th. 1 implies Th. 2) If n is a prime, Theorem 1 gives a(n) = 1 = n*a(1)+1. For a nonprime n, let n = m*p where p is the largest prime factor of n and m >= 2. From Theorem 1, a(m) = m*s(m), a(n) = q*m*(s(m) + 1/n) = q*a(m) + 1.
(Th. 2 implies Th. 1) The reverse implication is equally easy.
Theorem 2 is equivalent to the following more complicated recurrence:
Theorem 3: a(1) = 0. For n >= 2, a(n) = max_{p|n, p prime} (p*a(n/p)+1).

			For n=24, s(24) = 1/2 + 1/4 + 1/8 + 1/24 = 11/12, so a(24) = 24*11/12 = 22.

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 28, 53.
E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Second Edition, Vol. 1, A K Peters, 2001, pp. 27, 51.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jonathan Blanchette and Robert Laganière, A Curious Link Between Prime Numbers, the Maundy Cake Problem and Parallel Sorting, arXiv:1910.11749 [cs.DS], 2019.

Cf. A020639, A032742, A001348, A002182, A008864.
Cf. also A027746, A306264, A306363, A322034, A322035, A322036, A322382, A328898, A333783, A332993, A333791.
Row sums of A328969.

a006022 1 = 0
a006022 n = (+ 1) $ sum $ takeWhile (> 1) $
          iterate (\x -> x `div` a020639 x) (a032742 n)
-- Reinhard Zumkeller, Jun 03 2012

P:=proc(n) local FM: FM:=ifactors(n)[2]: seq(seq(FM[j][1], k=1..FM[j][2]), j=1..nops(FM)) end: # A027746
s:=proc(n) local i,t,b; global P;t:=0; b:=1; for i in [P(n)] do b:=b*i; t:=t+1/b; od; t; end; # A322034/A322035
A006022 := n -> if n = 1 then 0 else n*s(n); fi;
# N. J. A. Sloane, Nov 28 2018

Nest[Function[{a, n}, Append[a, Max@ Map[# a[[n/#]] + 1 &, Rest@ Divisors@ n]]] @@ {#, Length@ # + 1} &, {0, 1}, 77] (* Michael De Vlieger, Nov 23 2018 *)

lista(nn) = {my(v = vector(nn)); for (n=1, nn, if (n>1, my(m = 0); fordiv (n, d, if (d>1, m = max(m, d*v[n/d]+1))); v[n] = m;); print1(v[n], ", "););} \\ Michel Marcus, Nov 25 2018

a(n) = n * Sum_{k=1..N} (1/(p1^m1*p2^m2*...*pk^mk)) * (pk^mk-1)/(pk-1) for n>=2, where pk is the k-th distinct prime factor of n, N is the number of distinct prime factors of n, and mk is the multiplicity of pk occurring in n. To prove this, expand the factors in Theorem 1 and use the geometrical series identity. - Jonathan Blanchette, Nov 01 2019
From Antti Karttunen, Apr 12 2020: (Start)
a(n) = A322382(n) + A333791(n).
a(n) = A332993(n) - n = A001065(n) - A333783(n). (End)
a(n) = Sum_{k=1..bigomega(n)} F^k(n), where F^k(n) is the k-th iterate of F(n) = A032742(n). - Ridouane Oudra, Jan 26 2024

Edited and extended by Christian G. Bower, Oct 18 2002

Entry revised by N. J. A. Sloane, Nov 28 2018

A332994 a(1) = 1, for n > 1, a(n) = n + a(A052126(n)).

Original entry on oeis.org

1, 3, 4, 7, 6, 9, 8, 15, 13, 13, 12, 19, 14, 17, 19, 31, 18, 27, 20, 27, 25, 25, 24, 39, 31, 29, 40, 35, 30, 39, 32, 63, 37, 37, 41, 55, 38, 41, 43, 55, 42, 51, 44, 51, 58, 49, 48, 79, 57, 63, 55, 59, 54, 81, 61, 71, 61, 61, 60, 79, 62, 65, 76, 127, 71, 75, 68, 75, 73, 83, 72, 111, 74, 77, 94, 83, 85, 87, 80, 111, 121

Offset: 1

Antti Karttunen, Apr 04 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A000203, A052126, A322382, A332904, A332993, A333784, A333791, A333794.

A332994(n) = if(1==n,n,n + A332994(n/vecmax(factor(n)[,1])));

a(1) = 1; and for n > 1, a(n) = n + a(A052126(n)).
a(n) = n + A322382(n).
a(n) = A332993(n) - A333791(n).
a(n) = A000203(n) - A333784(n).

A333794 a(1) = 1, for n > 1, a(n) = n + a(n-A052126(n)).

Original entry on oeis.org

1, 3, 6, 7, 12, 13, 20, 15, 22, 25, 36, 27, 40, 41, 42, 31, 48, 45, 64, 51, 66, 73, 96, 55, 76, 81, 72, 83, 112, 85, 116, 63, 118, 97, 120, 91, 128, 129, 130, 103, 144, 133, 176, 147, 136, 193, 240, 111, 182, 153, 162, 163, 216, 145, 208, 167, 202, 225, 284, 171, 232, 233, 208, 127, 236, 237, 304, 195, 306, 241, 312, 183, 256, 257

Offset: 1

Antti Karttunen, Apr 05 2020

nonn

Conjecturally, also the largest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

			For n=119, the graph obtained is this:
              119
             _/\_
            /    \
          102    112
         _/|\_    | \_
       _/  |  \_  |   \_
      /    |    \ |     \
    51     68    96     56
    /|   _/ |   _/|   _/ |
   / | _/   | _/  | _/   |
  /  |/     |/    |/     |
(48) 34    64     48    28
     |\_    |    _/|   _/|
     |  \_  |  _/  | _/  |
     |    \_|_/    |/    |
    17     32     24    14
      \_    |    _/|   _/|
        \_  |  _/  | _/  |
          \_|_/    |/    |
           16      12    7
            |    _/|    _/
            |  _/  |  _/
            |_/    |_/
            8     _6
            |  __/ |
            |_/    |
            4      3
             \     /
              \_ _/
                2
                |
                1.
If we always subtract A052126(n) (i.e., n divided by its largest prime divisor), i.e., iterate with A171462 (starting from 119), we obtain 119-(119/17) = 112 -> 112-(112/7) -> 96-(96/3) -> 64-(64/2) -> 32-(32/2) -> 16-(16/2) -> 8-(8/2) -> 4-(4/2) -> 2-(2/2) -> 1, with sum 119+112+96+64+32+16+8+4+2+1 = 554, thus a(119) = 554. This happens also to be maximal sum of any path in above diagram.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Michael De Vlieger, Graph montage of k -> k - k/p, with prime p|k for 2 <= k <= 211, red line showing path of greatest sum, blue the path of least sum (cf. A333790), and purple where the two paths coincide, with other paths in gray.

Cf. A052126, A073934, A171462, A332994, A333790, A333793.

Array[Total@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # > 1 &] &, 74] (* Michael De Vlieger, Apr 14 2020 *)

A333794(n) = if(1==n,n,n + A333794(n-(n/vecmax(factor(n)[, 1]))));

a(1) = 1; and for n > 1, a(n) = n + a(A171462(n)) = n + a(n-A052126(n)).
a(n) = A073934(n) + A333793(n).
a(n) = n + Max a(n - n/p), for p prime and dividing n. [Conjectured, holds at least up to n=2^24]
For all n >= 1, A333790(n) <= a(n) <= A332904(n).
For all n >= 1, a(n) >= A332993(n). [Apparently, have to check!]

A332904 Sum of distinct integers encountered on all possible paths from n to 1 when iterating with nondeterministic map k -> k - k/p, where p is any of the prime factors of k.

Original entry on oeis.org

1, 3, 6, 7, 12, 16, 23, 15, 25, 30, 41, 36, 49, 57, 66, 31, 48, 63, 82, 66, 105, 99, 122, 76, 91, 115, 90, 125, 154, 156, 187, 63, 222, 114, 240, 139, 176, 196, 217, 138, 179, 251, 294, 215, 264, 284, 331, 156, 300, 213, 258, 247, 300, 220, 345, 261, 334, 348, 407, 336, 397, 429, 395, 127, 492, 512, 579, 246, 650, 546, 617, 291, 364

Offset: 1

Antti Karttunen, Apr 04 2020

nonn

			a(12): we have three alternative paths: {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6, 8, 12] present, therefore a(12) = 1+2+3+4+6+8+12 = 36.
For n=15 we have five alternative paths from 15 to 1: {15, 10, 5, 4, 2, 1}, {15, 10, 8, 4, 2, 1}, {15, 12, 8, 4, 2, 1},  {15, 12, 6, 4, 2, 1},  {15, 12, 6, 3, 2, 1}. These form a lattice illustrated below:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1,
therefore a(15) = 1+2+3+4+5+6+8+10+12+15 = 66.

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

Cf. A064097, A073934, A332809, A332993, A332994, A333000, A333123.

Cf. A333790 (sum of the route with minimal sum), A333794.

Total /@ Nest[Function[{a, n}, Append[a, Union@ Flatten@ Table[Append[a[[n - n/p]], n], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{1}}, 72] (* Michael De Vlieger, Apr 15 2020 *)

up_to = 20000;
A332904list(up_to) = { my(v=vector(up_to)); v[1] = Set([1]); for(n=2,up_to, my(f=factor(n)[, 1]~, s=Set([n])); for(i=1,#f,s = setunion(s,v[n-(n/f[i])])); v[n] = s); apply(vecsum,v); }
v332904 = A332904list(up_to);
A332904(n) = v332904[n];

For all primes p, a(p) = a(p-1) + p.

For all n >= 1, A333000(n) >= a(n) >= A333794(n) >= A333790(n).

cp's OEIS Frontend

A333783 a(n) = sigma(n) - A332993(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A333791 Difference of sums of two subsets of divisors of n, those obtained by repeatedly dividing with the smallest remaining prime factor (A332993) and those obtained by repeatedly dividing with the largest remaining prime factor (A332994).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A348978 Numerator of ratio A332993(n) / sigma(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A348977 a(n) = gcd(sigma(n), A332993(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A348979 Denominator of ratio A332993(n) / sigma(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A378523 Dirichlet inverse of A332993, where A332993 is defined as a(1) = 1, and for n > 1, a(n) = n + a(A032742(n)), and A032742 is the largest proper divisor.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A006022 Sprague-Grundy (or Nim) values for the game of Maundy cake on an n X 1 sheet.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A332994 a(1) = 1, for n > 1, a(n) = n + a(A052126(n)).

Views