A006022 - OEIS

%I M2219 #152 Aug 02 2024 06:26:28

%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) = 0. 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>

%H Jonathan Blanchette and Robert Laganière, <a href="https://arxiv.org/abs/1910.11749">A Curious Link Between Prime Numbers, the Maundy Cake Problem and Parallel Sorting</a>, arXiv:1910.11749 [cs.DS], 2019.

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

%F From _Antti Karttunen_, Apr 12 2020: (Start)

%F a(n) = A322382(n) + A333791(n).

%F a(n) = A332993(n) - n = A001065(n) - A333783(n). (End)

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

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

%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/A322035

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

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

%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, A306264, A306363, A322034, A322035, A322036, A322382, A328898, A333783, A332993, A333791.

%Y Row sums of A328969.

%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