|
%I M1009 N0377 #104 Sep 07 2023 11:09:43
%S 1,2,4,6,10,12,18,22,30,34,42,48,58,60,78,82,102,108,118,132,150,154,
%T 174,192,210,214,240,258,274,282,322,330,360,372,402,418,442,454,498,
%U 510,540,570,612,622,648,672,718,732,780,802,840,870,918
%N Smallest number of stones in Tchoukaillon (or Mancala, or Kalahari) solitaire that make use of n-th hole.
%C To get n-th term, start with n and successively round up to next multiple of n-1, n-2, ..., 1.
%C Generated by a sieve: start with [ 1..n ]; keep first number, drop every 2nd, keep first, drop every 3rd, keep first, drop every 4th, etc.
%C Comment from _Don Knuth_, Jun 08 2021, added by _N. J. A. Sloane_, Jun 09 2021: (Start)
%C I have put together a preliminary exposition of the results of Broline and Loeb (1995), in what's currently called Exercise 11 (on page 7) and its answer (on pages 9 and 10) of the Bipartite Matching document.
%C Unfortunately, I believe this paper erred when it claimed to have proved the conjecture of Erdős and Jabotinsky about the sharpness of approximation to n^2/pi. When they computed the sum of I_M in the proof of Theorem 9, they expressed it as f(M-1)^2/4M + O(f(M-1)). That's correct; but the error gets quite large, and when summed gives O(n^(3/2)), not O(n).
%C By summing over only part of the range, and using another estimate in the rest, I believe one can get an overall error bound O(n^(4/3)), thus matching the result of Erdős and Jabotinsky but not improving on it. (End)
%D Y. David, On a sequence generated by a sieving process, Riveon Lematematika, 11 (1957), 26-31.
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.4.7.
%D V. Gautheron, Chapter 3.II.5: La Tchouka, in Wari et Solo: le Jeu de calculs africain (Les Distracts), Edited by A. Deledicq and A. Popova, CEDIC, Paris, 1977, 180-187.
%D D. E. Knuth, Bipartite Matching, The Art of Computer Programming, Vol. 4, Pre-fascicle 14A, June 8, 2021, http://cs.stanford.edu/~knuth/fasc14a.ps.gz. See Sect. 7.5.1, Exercise 11.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Kerry Mitchell, <a href="/A002491/b002491.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H D. Betten, <a href="http://dx.doi.org/10.1016/S0167-5060(08)70224-3">Kalahari and the Sequence "Sloane No. 377"</a>, Annals Discrete Math., 37, 51-58, 1988.
%H D. M. Broline and Daniel E. Loeb, <a href="https://arxiv.org/abs/math/9502225">The combinatorics of Mancala-Type games: Ayo, Tchoukaillon and 1/Pi</a>, J. Undergrad. Math. Applic., vol. 16 (1995), pp. 21-36; arXiv:math/9502225 [math.CO], 1995.
%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath001/kmath001.htm">Rounding Up To PI</a>
%H Y. David, <a href="/A002491/a002491.pdf">On a sequence generated by a sieving process</a>, Riveon Lematematika, 11 (1957), 26-31. [Annotated scan of pages 31 and 27 only]
%H Mark Dukes, <a href="https://maths.ucd.ie/~dukes/strange_roots.pdf">Sequences of integer pairs related to the game of Tchoukaillon solitaire</a>, University College Dublin (Ireland, 2020).
%H Mark Dukes, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Dukes/dukes3.html">Fagan's Construction, Strange Roots, and Tchoukaillon Solitaire</a>, Journal of Integer Sequences, Vol. 24 (2021), Article 21.7.1.
%H Mark Dukes, <a href="https://arxiv.org/abs/2202.02381">Fagan's Construction, Strange Roots, and Tchoukaillon Solitaire</a>, arXiv:2202.02381 [math.NT], 2022.
%H P. Erdős and E. Jabotinsky, <a href="http://dx.doi.org/10.1016/S1385-7258(58)50016-X">On a sequence of integers generated by a sieving process (Part I)</a>, Indagationes Math., 20, 115-128, 1958.
%H P. Erdős and E. Jabotinsky, <a href="http://dx.doi.org/10.1016/S1385-7258(58)50017-1">On a sequence of integers generated by a sieving process (Part II)</a>, Indagationes Math., 20, 115-128, 1958.
%H B. Gourevitch, <a href="http://www.pi314.net/eng/brown.php">The World of Pi</a>
%H Nick Hobson, <a href="/A002491/a002491.py.txt">Python program for this sequence</a>
%H Brant Jones, Laura Taalman and Anthony Tongen, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.120.08.706">Solitaire Mancala Games and the Chinese Remainder Theorem</a>, Amer. Math. Mnthly, 120 (2013), 706-724.
%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Pi.html">Pi</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PiFormulas.html">Pi Formulas</a>.
%H <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>
%F Equals A007952(n) + 1 or equally A108696(n) - 1.
%F A130747(a(n)) = 1. - _Reinhard Zumkeller_, Jun 23 2009
%F a(n+1) = 1 + [..[[[[n*3/2]5/4]7/6]9/8]...(2k+1)/2k]...]. - _Birkas Gyorgy_, Mar 07 2011
%F Limit_{n -> oo} n^2/a(n) = Pi (see Brown). - _Peter Bala_, Mar 12 2014
%F It appears that a(n)/2 = A104738(n-1). - _Don Knuth_, May 27 2021
%e To get 10th term: 10->18->24->28->30->30->32->33->34->34.
%p # A002491
%p # program due to B. Gourevitch
%p a := proc(n)
%p local x,f,i,y;
%p x := n; f := n;
%p for i from x by -1 to 2 do
%p y := i-1;
%p while y < f do
%p y := y+i-1
%p od;
%p f := y
%p od
%p end:
%p seq(a(n), n = 2 .. 53);
%t f[n_] := Fold[ #2*Ceiling[ #1/#2 + 0] &, n, Reverse@Range[n - 1]]; Array[f, 56] (* _Robert G. Wilson v_, Nov 05 2005 *)
%t del[list_, k_] := Delete[list, Table[{i}, {i, k, Length[list], k}]]; a[n_] := Last@NestWhile[{#[[1]] + 1, del[Rest@#[[2]], #[[1]] + 1], Append[#[[3]], First@#[[2]]]} &, {1,Range[n], {}}, #[[2]] =!= {} &]; a[1000] (* _Birkas Gyorgy_, Feb 26 2011 *)
%t Table[1 + First@FixedPoint[{Floor[#[[1]]*(#[[2]] + 1/2)/#[[2]]], #[[2]] + 1} &, {n, 1}, SameTest -> (#1[[1]] == #2[[1]] &)], {n, 0, 30}] (* _Birkas Gyorgy_, Mar 07 2011 *)
%t f[n_]:=Block[{x,p},For[x=p=1, p<=n, p++, x=Ceiling[(n+2-p)x/(n+1-p)]];x] (* _Don Knuth_, May 27 2021 *)
%o (Haskell)
%o a002491 n = a002491_list !! (n-1)
%o a002491_list = sieve 1 [1..] where
%o sieve k (x:xs) = x : sieve (k+1) (mancala xs) where
%o mancala xs = us ++ mancala vs where (us,v:vs) = splitAt k xs
%o -- _Reinhard Zumkeller_, Oct 31 2012
%o (PARI) a(n)=forstep(k=n-1,2,-1, n=((n-1)\k+1)*k); n \\ _Charles R Greathouse IV_, Mar 29 2016
%Y Cf. A000012, A000960, A028920, A028931, A028932, A028933, A112557, A112558, A113742, A113743, A113744, A113745, A113746, A113747, A113748, A113749.
%Y Cf. also A104738.
%Y A row of the array in A344009.
%K nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_
|
