A333783 -id:A333783 - cp's OEIS frontend

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

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

A332993 a(1) = 1, for n > 1, a(n) = n + a(A032742(n)).

Original entry on oeis.org

1, 3, 4, 7, 6, 10, 8, 15, 13, 16, 12, 22, 14, 22, 21, 31, 18, 31, 20, 36, 29, 34, 24, 46, 31, 40, 40, 50, 30, 51, 32, 63, 45, 52, 43, 67, 38, 58, 53, 76, 42, 71, 44, 78, 66, 70, 48, 94, 57, 81, 69, 92, 54, 94, 67, 106, 77, 88, 60, 111, 62, 94, 92, 127, 79, 111, 68, 120, 93, 113, 72, 139, 74, 112, 106, 134, 89, 131, 80, 156, 121

Offset: 1

Antti Karttunen, Apr 04 2020

nonn

Sum of 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.

			a(18) = 18 + 18/2 + 9/3 + 3/3 = 18 + 9 + 3 + 1 = 31.

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, A006022, A032742, A064097, A073934, A332994, A333783, A333791, A333794.

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

a(1) = 1; and for n > 1, a(n) = n + a(A032742(n)).
a(n) = n + A006022(n).
a(n) = A332994(n) + A333791(n).
a(n) = A000203(n) - A333783(n).
It seems that for all n >= 1, a(n) <= A073934(n) <= A333794(n).

A333784 a(n) = sigma(n) - A332994(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 3, 0, 0, 0, 5, 0, 9, 0, 7, 5, 0, 0, 12, 0, 15, 7, 11, 0, 21, 0, 13, 0, 21, 0, 33, 0, 0, 11, 17, 7, 36, 0, 19, 13, 35, 0, 45, 0, 33, 20, 23, 0, 45, 0, 30, 17, 39, 0, 39, 11, 49, 19, 29, 0, 89, 0, 31, 28, 0, 13, 69, 0, 51, 23, 61, 0, 84, 0, 37, 30, 57, 11, 81, 0, 75, 0, 41, 0, 121, 17, 43, 29, 77, 0, 117, 13, 69, 31

Offset: 1

Antti Karttunen, Apr 05 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
Index entries for sequences related to sigma(n)

Cf. A000203, A000961 (positions of zeros), A001065, A052126, A322382, A332994, A333783, A333791.

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

a(n) = A000203(n) - A332994(n).
a(n) = A001065(n) - A322382(n).
a(n) = A333783(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)).

cp's OEIS Frontend

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

A332993 a(1) = 1, for n > 1, a(n) = n + a(A032742(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A333784 a(n) = sigma(n) - A332994(n).

Views

Author

Keywords

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