|
|
A002491
|
|
Smallest number of stones in Tchoukaillon (or Mancala, or Kalahari) solitaire that make use of n-th hole.
(Formerly M1009 N0377)
|
|
29
|
|
|
1, 2, 4, 6, 10, 12, 18, 22, 30, 34, 42, 48, 58, 60, 78, 82, 102, 108, 118, 132, 150, 154, 174, 192, 210, 214, 240, 258, 274, 282, 322, 330, 360, 372, 402, 418, 442, 454, 498, 510, 540, 570, 612, 622, 648, 672, 718, 732, 780, 802, 840, 870, 918
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
To get n-th term, start with n and successively round up to next multiple of n-1, n-2, ..., 1.
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.
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.
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).
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)
|
|
REFERENCES
|
Y. David, On a sequence generated by a sieving process, Riveon Lematematika, 11 (1957), 26-31.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.4.7.
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. 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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Pi.
|
|
FORMULA
|
a(n+1) = 1 + [..[[[[n*3/2]5/4]7/6]9/8]...(2k+1)/2k]...]. - Birkas Gyorgy, Mar 07 2011
Limit_{n -> oo} n^2/a(n) = Pi (see Brown). - Peter Bala, Mar 12 2014
|
|
EXAMPLE
|
To get 10th term: 10->18->24->28->30->30->32->33->34->34.
|
|
MAPLE
|
# program due to B. Gourevitch
a := proc(n)
local x, f, i, y;
x := n; f := n;
for i from x by -1 to 2 do
y := i-1;
while y < f do
y := y+i-1
od;
f := y
od
end:
seq(a(n), n = 2 .. 53);
|
|
MATHEMATICA
|
f[n_] := Fold[ #2*Ceiling[ #1/#2 + 0] &, n, Reverse@Range[n - 1]]; Array[f, 56] (* Robert G. Wilson v, Nov 05 2005 *)
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 *)
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 *)
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 *)
|
|
PROG
|
(Haskell)
a002491 n = a002491_list !! (n-1)
a002491_list = sieve 1 [1..] where
sieve k (x:xs) = x : sieve (k+1) (mancala xs) where
mancala xs = us ++ mancala vs where (us, v:vs) = splitAt k xs
|
|
CROSSREFS
|
Cf. A000012, A000960, A028920, A028931, A028932, A028933, A112557, A112558, A113742, A113743, A113744, A113745, A113746, A113747, A113748, A113749.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|