A104738 -id:A104738 - cp's OEIS frontend

A002491 Smallest number of stones in Tchoukaillon (or Mancala, or Kalahari) solitaire that make use of n-th hole.

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

Offset: 1

N. J. A. Sloane

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.
Comment from Don Knuth, Jun 08 2021, added by N. J. A. Sloane, Jun 09 2021: (Start)
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)

			To get 10th term: 10->18->24->28->30->30->32->33->34->34.

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).

Kerry Mitchell, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
D. Betten, Kalahari and the Sequence "Sloane No. 377", Annals Discrete Math., 37, 51-58, 1988.
D. M. Broline and Daniel E. Loeb, The combinatorics of Mancala-Type games: Ayo, Tchoukaillon and 1/Pi, J. Undergrad. Math. Applic., vol. 16 (1995), pp. 21-36; arXiv:math/9502225 [math.CO], 1995.
K. S. Brown, Rounding Up To PI
Y. David, On a sequence generated by a sieving process, Riveon Lematematika, 11 (1957), 26-31. [Annotated scan of pages 31 and 27 only]
Mark Dukes, Sequences of integer pairs related to the game of Tchoukaillon solitaire, University College Dublin (Ireland, 2020).
Mark Dukes, Fagan's Construction, Strange Roots, and Tchoukaillon Solitaire, Journal of Integer Sequences, Vol. 24 (2021), Article 21.7.1.
Mark Dukes, Fagan's Construction, Strange Roots, and Tchoukaillon Solitaire, arXiv:2202.02381 [math.NT], 2022.
P. Erdős and E. Jabotinsky, On a sequence of integers generated by a sieving process (Part I), Indagationes Math., 20, 115-128, 1958.
P. Erdős and E. Jabotinsky, On a sequence of integers generated by a sieving process (Part II), Indagationes Math., 20, 115-128, 1958.
B. Gourevitch, The World of Pi
Nick Hobson, Python program for this sequence
Brant Jones, Laura Taalman and Anthony Tongen, Solitaire Mancala Games and the Chinese Remainder Theorem, Amer. Math. Mnthly, 120 (2013), 706-724.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
Eric Weisstein's World of Mathematics, Pi.
Eric Weisstein's World of Mathematics, Pi Formulas.
Index entries for sequences generated by sieves

Cf. A000012, A000960, A028920, A028931, A028932, A028933, A112557, A112558, A113742, A113743, A113744, A113745, A113746, A113747, A113748, A113749.
Cf. also A104738.
A row of the array in A344009.

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
-- Reinhard Zumkeller, Oct 31 2012

# A002491
# 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);

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

a(n)=forstep(k=n-1,2,-1, n=((n-1)\k+1)*k); n \\ Charles R Greathouse IV, Mar 29 2016

Equals A007952(n) + 1 or equally A108696(n) - 1.
A130747(a(n)) = 1. - Reinhard Zumkeller, Jun 23 2009
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
It appears that a(n)/2 = A104738(n-1). - Don Knuth, May 27 2021

A204539 a(n) is the number of integers N=4k whose "basin" sequence (cf. comment) ends in n^2.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 2, 4, 2, 4, 3, 5, 1, 9, 2, 10, 3, 5, 7, 9, 2, 10, 9, 9, 2, 13, 9, 8, 4, 20, 4, 15, 6, 15, 8, 12, 6, 22, 6, 15, 15, 21, 5, 13, 12, 23, 7, 24, 11, 19, 15, 24, 6, 30, 6, 26, 7, 27, 26, 13, 6, 33, 27, 30, 5, 13, 30, 30, 5, 37, 15, 26, 28, 32, 7, 17, 25, 54, 9, 30, 21, 41, 25

Offset: 2

Colm Fagan, Jan 16 2012

nonn

The "basin" (analogous to river basins, for reasons set out below) is the number of positive integers N=4k which end in the "sea" at n^2. The "sea" of N is found as follows:
Starting out with N, in step i=1,2,3,..., stop if you have reached N=(i+1)^2 (the "sea" of N), otherwise set N to the next higher, odd or even (according to the parity of i), multiple of i+2, and go to step i+1.
Partial sums of this sequence appear to be A104738 (with a shift in offset). This has been confirmed for at least the first 4000 terms, but it is not at all clear why this is the case. - Ray Chandler, Jan 20 2012
After the first term, this sequence agrees with A028914 except for offset. Therefore this sequence is related to A028913, A007952, A002491 and A108696 dealing with the sieve of Tchoukaillon (or Mancala, or Kalahari). - Ray Chandler, Jan 20 2012

			For integers N=4,8,12,16,... we have the following sequences:
  {4}
  {8, 9}   (8 -> the next higher odd multiple of 3, which is 9 -> STOP)
  {12, 15, 16}  (12 -> 3*5=15 -> 4*4=16 -> STOP)
  {16, 21, 24, 25}
  {20, 21, 24, 25}
  {24, 27, 32, 35, 36}
  {28, 33, 40, 45, 48, 49}
  {32, 33, 40, 45, 48, 49}
  {36, 39, 40, 45, 48, 49}
  ...
Thus there is 1 integer N=4k ending in the sea at 2^2, whence basin a(2)=1, and idem for 3 and 4.
The two integers 16 and 20 end at 5^2, so the basin of 5 is a(5)=2.
There is again a(6)=1 integer ending in 6^2, while the basin of 7 are the 3 integers 28, 32, and 36, which all merge into the "river" that enters the "sea" in 7^2=49.
Thus the first 6 terms in the sequence are 1, 1, 1, 2, 1, 3.
Take N=100 as an example: the next integer on the same line is the next higher odd multiple of 3, i.e., smallest 3*(2m+1) > 100, which is 105. The next number is the least even multiple of 4, 4*(2m) = 112, etc., leading to 115 = 5*(2m+1), followed by 120 = 6*(2m), 133 = 7*(2m+1), 144 = 8*2m (where we have a square, but not the square of 8), 153 =9*(2m+1), 160 = 10*2m, 165 = 11*(2m+1), 168 = 12*(2m) and finally 169 = 13*13.

Ray Chandler, Table of n, a(n) for n = 2..10001
Mark Dukes, Fagan's Construction, Strange Roots, and Tchoukaillon Solitaire, Journal of Integer Sequences, Vol. 24 (2021), Article 21.7.1.
Mark Dukes, Fagan's Construction, Strange Roots, and Tchoukaillon Solitaire, arXiv:2202.02381 [math.NT], 2022.

Cf. A002491, A007952, A028913, A104738, A108696, A204540.

Essentially the same as A028914.

cumul[n_Integer] := Module[{den1 = n, num = n^2, den2}, While[num > 4 && den1 != 2, num = num - 1; den1 = den1 - 1; den2 = Floor[num/den1]; If[Not[EvenQ[den1 + den2]], den2 = den2 - 1]; num = den1 den2]; Return[num/4]]; basin[2] := 1; basin[n_Integer] := cumul[n] - cumul[n - 1]; Table[basin[n], {n, 2, 75}] (* Alonso del Arte, Jan 19 2012 *)

bs(n,s,m=2)={while(n>m^2,n=(n\m+++2-bittest(n\m-m,0))*m; s & print1(n","));n}
n=4; for(c=2,50, for(k=1,9e9, bs(n+=4)==c^2 || print1(k",")||break)) \\ M. F. Hasler, Jan 20 2012

cp's OEIS Frontend

A002491 Smallest number of stones in Tchoukaillon (or Mancala, or Kalahari) solitaire that make use of n-th hole.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A204539 a(n) is the number of integers N=4k whose "basin" sequence (cf. comment) ends in n^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A104737 Positions of records in A104705.

Views

Author

Keywords

Crossrefs

Extensions

A104739 Positions of records in A104717.

Views

Author

Keywords

Crossrefs

Extensions