|
|
A006022
|
|
Sprague-Grundy (or Nim) values for the game of Maundy cake on an n X 1 sheet.
(Formerly M2219)
|
|
12
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
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.
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).
|
|
REFERENCES
|
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).
|
|
LINKS
|
|
|
FORMULA
|
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
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
|
|
EXAMPLE
|
For n=24, s(24) = 1/2 + 1/4 + 1/8 + 1/24 = 11/12, so a(24) = 24*11/12 = 22.
|
|
MAPLE
|
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;
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(Haskell)
a006022 1 = 0
a006022 n = (+ 1) $ sum $ takeWhile (> 1) $
iterate (\x -> x `div` a020639 x) (a032742 n)
(PARI) 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
|
|
CROSSREFS
|
Cf. also A027746, A306264, A306363, A322034, A322035, A322036, A322382, A328898, A333783, A332993, A333791.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|