login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006022 Sprague-Grundy (or Nim) values for the game of Maundy cake on an n X 1 sheet.
(Formerly M2219)
7

%I M2219

%S 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,

%T 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,

%U 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

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

%C There are three equivalent formulas for a(n). Suppose n >= 2, and let p1 <= p2 <= ... <= pk be the prime factors of n, with repetition.

%C Theorem 1: a(1) = 0. For n >= 2, a(n) = n*s(n), where

%C s(n) = 1/p1 + 1/(p1*p2) + 1/(p1*p2*p3) + ... + 1/(p1*p2*...*pk).

%C This is implicit in Berlekamp, Conway and Guy, Winning Ways, 2 vols., 1982, pp. 28, 53.

%C Note that s(n) = A322034(n) / A322035(n).

%C _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):

%C Theorem 2: a(1) = 0. For n >= 2, a(n) = p*a(n/p) + 1, where p is the largest prime factor of n.

%C 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.

%C (Th. 2 implies Th. 1) The reverse implication is equally easy.

%C Theorem 2 is equivalent to the following more complicated recurrence:

%C Theorem 3: a(1) = 1. For n >= 2, a(n) = max_{p|n, p prime} (p*a(n/p)+1).

%D E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 28, 53.

%D E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Second Edition, Vol. 1, A K Peters, 2001, pp. 27, 51.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Reinhard Zumkeller, <a href="/A006022/b006022.txt">Table of n, a(n) for n = 1..10000</a>

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

%p # from _N. J. A. Sloane_, Nov 28 2018

%p 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

%p 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/A0322035

%p A006022 := n -> if n = 1 then 0 else n*s(n); fi;

%t 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 *)

%o (Haskell)

%o a006022 1 = 0

%o a006022 n = (+ 1) $ sum $ takeWhile (> 1) $

%o iterate (\x -> x `div` a020639 x) (a032742 n)

%o -- _Reinhard Zumkeller_, Jun 03 2012

%o (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

%Y Cf. A020639, A032742, A001348, A002182, A008864.

%Y Cf. also A027746, A322034, A322035, A322036.

%K nonn

%O 1,4

%A _N. J. A. Sloane_

%E Edited and extended by _Christian G. Bower_, Oct 18 2002

%E Entry revised by _N. J. A. Sloane_, Nov 28 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 26 04:32 EDT 2019. Contains 321481 sequences. (Running on oeis4.)