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

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, 178, 222, 278, 347, 434, 543, 678, 848, 1060, 1325, 1656, 2070, 2588, 3235, 4043, 5054, 6318, 7897, 9871, 12339, 15424, 19280, 24100, 30125, 37656, 47070, 58838, 73547

Offset: 1

Author

Graeme McRae, Jun 10 2006

Keywords

• nonn

Comments

From Petros Hadjicostas, Jul 21 2020: (Start)

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.

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)

From Petros Hadjicostas, Jul 23 2020: (Start)

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

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

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

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

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

Examples

			From _Petros Hadjicostas_, Jul 23 2020: (Start)
We explain why 6 and 8 belong to the sequence related to the Josephus problem (for the case k = 5) while 7 does not.
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.
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.
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)
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• K. Burde, Das Problem der Abzählreime und Zahlentwicklungen mit gebrochenen Basen [The problem of counting rhymes and number expansions with fractional bases], 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.]
• Nicolas Thériault, Generalizations of the Josephus problem, Utilitas Mathematica, 58 (2000), 161-173 (MR1801309).
• Nicolas Thériault, Generalizations of the Josephus problem, Utilitas Mathematica, 58 (2000), 161-173 (MR1801309).
• Index entries for sequences related to the Josephus Problem

Crossrefs

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

Programs

Magma

function f(n, a, b)
  t:=0;
    for k in [1..n-1] do
      t+:= a+Ceiling((b+t)/4);
    end for;
  return t;
end function;
g:= func< n, a, b | f(n+1, a, b)-f(n, a, b) >;
A120160:= func< n | n le 4 select 1 else g(n-4, 1, 0) >;
[A120160(n): n in [1..60]]; // G. C. Greubel, Sep 01 2023

Mathematica

f[s_]:= Append[s, Ceiling[Plus @@ s/4]]; Nest[f,1,53] (* Robert G. Wilson v *)
(* Second program *)
f[n_]:= f[n]= 1 + Quotient[Sum[f[k], {k,n-1}], 4];
A120160[n_]:= If[n==1, 1, f[n-1]];
Table[A120160[n], {n, 60}] (* G. C. Greubel, Sep 01 2023 *)

PARI

/* 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. */
lista(nn, k) = {my(j=vector(nn)); my(f=vector(nn)); my(N=vector(nn));
j[1]=1; f[1]=0; N[1] = 1;
for(n=1, nn-1, f[n+1] = ((j[n]-N[n]-1) % (k-1)) + 1 - j[n];
j[n+1] = j[n] + f[n+1]; N[n+1] = (k*N[n] + f[n+1])/(k-1); );
for(n=1, nn, if(N[n] > k-1, print1(N[n], ", "))); } \\ Petros Hadjicostas, Jul 23 2020

SageMath

@CachedFunction
def A120160(n): return 1 + ceil( sum(A120160(k) for k in range(1,n))//4 )
[A120160(n) for n in range(1,61)] # G. C. Greubel, Sep 01 2023

Extensions

Edited and extended by Robert G. Wilson v, Jul 07 2006

Appended the first missing term. - Tom Edgar, Jul 18 2014