A120160 - OEIS

%I #39 Aug 06 2024 06:40:08

%S 1,1,1,1,1,2,2,3,3,4,5,6,8,10,12,15,19,24,30,37,47,58,73,91,114,142,

%T 178,222,278,347,434,543,678,848,1060,1325,1656,2070,2588,3235,4043,

%U 5054,6318,7897,9871,12339,15424,19280,24100,30125,37656,47070,58838,73547

%N a(n) = ceiling(Sum_{i=1..n-1} a(i)/4) for n >= 2 starting with a(1) = 1.

%C From _Petros Hadjicostas_, Jul 21 2020: (Start)

%C Conjecture 1: a(n) equals the number of multiples of 4 whose representation in base 5/4 (see A024634) has n-1 digits. For example, a(8) = 3 because there are three multiples of 4 with n-1 = 7 digits in their representation in base 5/4: 36 = 4321031, 40 = 4321420, and 44 = 4321424.

%C Conjecture 2: a(n) equals 1/5 times the number of nonnegative integers with the property that their 5/4-expansion has n digits (assuming that the 5/4-expansion of 0 has 1 digit). For example, a(7)*5 = 10 because the following 10 numbers have 5/4 expansions with n = 7 digits: 35 = 4321030, 36 = 4321031, 37 = 4321032, 38 = 4321033, 39 = 4321034, 40 = 4321420, 41 = 4321421, 42 = 4321422, 43 = 4321423, and 44 = 4321424. (End)

%C From _Petros Hadjicostas_, Jul 23 2020: (Start)

%C Starting at a(11) = 5, we conjecture that this sequence gives all those numbers m for which when we place m persons on a circle, label them 1 through m, start counting at person number 1, and remove every 5th person, the last survivors have numbers in {1, 2, 3, 4}.

%C When m = 6, 12, 15, 37, 58, 142, 222, 347, ... the last survivor is person 1.

%C When m = 5, 19, 91, 434, 1656, 2070, 5054, ... the last survivor is person 2.

%C When m = 8, 10, 24, 30, 73, 114, 178, 278, ... the last survivor is person 3.

%C When m = 47, 543, 2588, 3235, 6318, 58838, ... the last survivor is person 4. (End)

%H G. C. Greubel, <a href="/A120160/b120160.txt">Table of n, a(n) for n = 1..1000</a>

%H K. Burde, <a href="http://dx.doi.org/10.1016/0022-314X(87)90078-3">Das Problem der Abzählreime und Zahlentwicklungen mit gebrochenen Basen [The problem of counting rhymes and number expansions with fractional bases]</a>, J. Number Theory 26(2) (1987), 192-209. [The author deals with the representation of n in fractional bases k/(k-1) and its relation to counting-off games (variations of Josephus problem). Here k = 5. See the review in MathSciNet (MR0889384) by R. G. Stoneham.]

%H Nicolas Thériault, <a href="https://pdfs.semanticscholar.org/341d/f5787ba71d62a9e4fb4f7b506351521cbf06.pdf">Generalizations of the Josephus problem</a>, Utilitas Mathematica, 58 (2000), 161-173 (MR1801309).

%H Nicolas Thériault, <a href="https://citeseerx.ist.psu.edu/pdf/341df5787ba71d62a9e4fb4f7b506351521cbf06">Generalizations of the Josephus problem</a>, Utilitas Mathematica, 58 (2000), 161-173 (MR1801309).

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%e From _Petros Hadjicostas_, Jul 23 2020: (Start)

%e We explain why 6 and 8 belong to the sequence related to the Josephus problem (for the case k = 5) while 7 does not.

%e When we place m = 6 people on a circle, label them 1 through 6, start counting at person 1, and remove every 5th person, the list of people we remove is 5 -> 4 -> 6 -> 2 -> 3. Thus the last survivor is person 1, so 6 belongs to this sequence.

%e When we place m = 7 people on a circle, label them 1 through 7, start counting at person 1, and remove every 5th person, the list of people we remove is 5 -> 3 -> 2 -> 4 -> 7 -> 1. Thus the last survivor is person 6 (not in {1, 2, 3, 4}), so 7 does not belong to this sequence.

%e When we place m = 8 people on a circle, label them 1 through 8, start the counting at person 1, and remove every 5th person, the list of people we remove is 5 -> 2 -> 8 -> 7 -> 1 -> 4 -> 6. Thus the last survivor is 3, so 8 belongs to this sequence. (End)

%t f[s_]:= Append[s, Ceiling[Plus @@ s/4]]; Nest[f,1,53] (* _Robert G. Wilson v_ *)

%t (* Second program *)

%t f[n_]:= f[n]= 1 + Quotient[Sum[f[k], {k,n-1}], 4];

%t A120160[n_]:= If[n==1, 1, f[n-1]];

%t Table[A120160[n], {n, 60}] (* _G. C. Greubel_, Sep 01 2023 *)

%o (PARI)

%o /* PARI program for the general case of Josephus problem. We use the Burde-Thériault algorithm. Here k = 5. To get the corresponding last survivors, modify the program to get the vector j. */

%o lista(nn, k) = {my(j=vector(nn)); my(f=vector(nn)); my(N=vector(nn));

%o j[1]=1; f[1]=0; N[1] = 1;

%o for(n=1, nn-1, f[n+1] = ((j[n]-N[n]-1) % (k-1)) + 1 - j[n];

%o j[n+1] = j[n] + f[n+1]; N[n+1] = (k*N[n] + f[n+1])/(k-1); );

%o for(n=1, nn, if(N[n] > k-1, print1(N[n], ", "))); } \\ _Petros Hadjicostas_, Jul 23 2020

%o (Magma)

%o function f(n, a, b)

%o   t:=0;

%o     for k in [1..n-1] do

%o       t+:= a+Ceiling((b+t)/4);

%o     end for;

%o   return t;

%o end function;

%o g:= func< n, a, b | f(n+1, a, b)-f(n, a, b) >;

%o A120160:= func< n | n le 4 select 1 else g(n-4, 1, 0) >;

%o [A120160(n): n in [1..60]]; // _G. C. Greubel_, Sep 01 2023

%o (SageMath)

%o @CachedFunction

%o def A120160(n): return 1 + ceil( sum(A120160(k) for k in range(1,n))//4 )

%o [A120160(n) for n in range(1,61)] # _G. C. Greubel_, Sep 01 2023

%Y Cf. A011782, A024634, A072493, A073941, A112088, A120170, A120178, A120186, A120194, A120202.

%K nonn

%O 1,6

%A _Graeme McRae_, Jun 10 2006

%E Edited and extended by _Robert G. Wilson v_, Jul 07 2006

%E Appended the first missing term. - _Tom Edgar_, Jul 18 2014