A120194 -id:A120194 - cp's OEIS frontend

A005428 a(n) = ceiling((1 + sum of preceding terms) / 2) starting with a(0) = 1.

1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 799, 1199, 1798, 2697, 4046, 6069, 9103, 13655, 20482, 30723, 46085, 69127, 103691, 155536, 233304, 349956, 524934, 787401, 1181102, 1771653, 2657479, 3986219, 5979328, 8968992, 13453488, 20180232, 30270348, 45405522, 68108283, 102162425, 153243637, 229865456, 344798184

Offset: 0

N. J. A. Sloane and Simon Plouffe

Original definition: a(0) = 1, state(0) = 2; for n >= 1, if a(n-1) is even then a(n) = 3*a(n-1)/2 and state(n) = state(n-1); if a(n-1) is odd and state(n-1) = 1 then a(n) = ceiling( 3*a(n-1)/2) and state(n) = 3 - state(n-1) and if a(n-1) is odd and state(n-1) = 2 then a(n) = floor( 3*a(n-1)/2) and state(n) = 3 - state(n-1). [See formula by M. Alekseyev for a simpler equivalent. - Ed.]
Arises from a version of the Josephus problem: sequence gives set of n where, if you start with n people and every 3rd person drops out, either it is person #1 or #2 who is left at the end. A081614 and A081615 give the subsequences where it is person #1 (respectively #2) who is left.
The state changes just when a(n) is odd: it therefore indicates whether the sum of a(0) to a(n) is odd (1 means no, 2 means yes).
The sum a(0) to a(n) is never divisible by 3 (for n >= 0); it is 1 mod 3 precisely when the sum a(0) to a(n-1) is odd and thus indicates the state at the previous step. - Franklin T. Adams-Watters, May 14 2008
The number of nodes at level n of a planted binary tree with alternating branching and non-branching nodes. - Joseph P. Shoulak, Aug 26 2012
Take Sum_{k=1..n} a(k) objects, and partition them into 3 parts. It is always possible to generate those parts using addends once each from the initial n terms, and this is the fastest growing sequence with this property. For example, taking 1+1+2+3+4+6+9 = 26 objects, if we partition them [10,9,7], we can generate these sizes as 10 = 9+1, 9 = 6+3, 7 = 4+2+1. The corresponding sequence partitioning into 2 parts is the powers of 2, A000079. In general, to handle partitioning into k parts, replace the division by 2 in the definition with division by k-1. - Franklin T. Adams-Watters, Nov 07 2015
a(n) is the number of even integers that have n+1 digits when written in base 3/2. For example, there are 2 even integers that use three digits in base 3/2: 6 and 8: they are written as 210 and 212, respectively. - Tanya Khovanova and PRIMES STEP Senior group, Jun 03 2018

			n........0...1...2...3...4...5...6...7...8...9..10..11..12..13..14.
state=1......1...........4...6...9..........31.....70..105.........
state=2..1.......2...3..............14..21......47.........158..237

F. Schuh, The Master Book of Mathematical Recreations. Dover, NY, 1968, page, 374, Table 18, union of columns 1 and 2 (which are A081614 and A081615).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..500
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.
B. Chen, R. Chen, J. Guo, S. Lee et al., On Base 3/2 and its sequences, arXiv:1808.04304 [math.NT], 2018.
L. Halbeisen and N. Hungerbuehler, The Josephus Problem, J. Théor. Nombres Bordeaux 9(2) (1997), 303-318.
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33 (1991), 235-240.
Eric Weisstein's World of Mathematics, Josephus Problem.
Wikipedia, Josephus problem.
Index entries for sequences related to the Josephus Problem

Cf. A005427, A073941, A082416. Union of A081614 and A081615.
First differences of D_3(n) (A061419) in the terminology of Odlyzko and Wilf. - Ralf Stephan, Apr 23 2002
Same as log_2(A082125(n+3)). - Ralf Stephan, Apr 16 2002
Apart from initial terms, same as A073941, which has further information.
a(n) is the number of positive even k for which A024629(k) has n+1 digits. - Glen Whitney, Jul 09 2017
Partial sums are in A061419, A061418, A006999.
Cf. A000079, A072493, A120160, A120170, A120178, A120186, A120194, A120202.

a005428 n = a005428_list !! n
a005428_list = (iterate j (1, 1)) where
   j (a, s) = (a', (s + a') `mod` 2) where
     a' = (3 * a + (1 - s) * a `mod` 2) `div` 2
-- Reinhard Zumkeller, May 10 2015 (fixed), Oct 26 2011

f[s_] := Append[s, Ceiling[(1 + Plus @@ s)/2]]; Nest[f, {1}, 40] (* Robert G. Wilson v, Jul 07 2006 *)
nxt[{t_,a_}]:=Module[{c=Ceiling[(1+t)/2]},{t+c,c}]; NestList[nxt,{1,1},50][[All,2]] (* Harvey P. Dale, Nov 05 2017 *)

{ a=1; s=2; for(k=1,50, print1(a,", "); a=(3*a+s-1)\2; s=(s+a)%3; ) } \\ Max Alekseyev, Mar 28 2009

s=0;vector(50,n,-s+s+=s\2+1)  \\ M. F. Hasler, Oct 14 2012

from itertools import islice
def A005428_gen(): # generator of terms
    a, c = 1, 0
    yield 1
    while True:
        yield (a:=1+((c:=c+a)>>1))
A005428_list = list(islice(A005428_gen(),30)) # Chai Wah Wu, Sep 21 2022

a(0) = 1; a(n) = ceiling((1 + Sum_{k=0..n-1} a(k)) / 2). - Don Reble, Apr 23 2003
a(1) = 1, s(1) = 2, and for n > 1, a(n) = floor((3*a(n-1) + s(n-1) - 1) / 2), s(n) = (s(n-1) + a(n)) mod 3. - Max Alekseyev, Mar 28 2009
a(n) = floor(1 + (sum of preceding terms)/2). - M. F. Hasler, Oct 14 2012

More terms from Hans Havermann, Apr 23 2003

Definition replaced with a simpler formula due to Don Reble, by M. F. Hasler, Oct 14 2012

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

Original entry on oeis.org

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

Graeme McRae, Jun 10 2006

nonn

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)

			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)

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

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

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

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

@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

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

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

A120170 a(n) = ceiling( Sum_{i=1..n-1} a(i)/5 ), a(1)=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 6, 7, 8, 10, 12, 14, 17, 21, 25, 30, 36, 43, 52, 62, 74, 89, 107, 128, 154, 185, 222, 266, 319, 383, 460, 552, 662, 795, 954, 1144, 1373, 1648, 1977, 2373, 2847, 3417, 4100, 4920, 5904, 7085, 8502, 10202, 12243, 14691, 17630

Offset: 1

Graeme McRae, Jun 10 2006

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A011782, A073941, A072493, A112088, A120160, A120178, A120186, A120194, A120202.

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

f[s_] := Append[s, Ceiling[Plus @@ s/5]]; Nest[f, {1}, 57] (* Robert G. Wilson v, Jul 07 2006 *)

@CachedFunction
def a(n):
    if (n==1): return 1
    else: return ceil(sum(a(k)/5 for k in (1..n-1)))
[a(n) for n in (1..60)] # G. C. Greubel, Aug 19 2019

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

A120186 a(n) = ceiling( Sum_{i=1..n-1} a(i)/7 ), a(1) = 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 23, 27, 30, 35, 40, 45, 52, 59, 68, 77, 88, 101, 115, 132, 151, 172, 197, 225, 257, 294, 336, 384, 439, 501, 573, 655, 748, 855, 977, 1117, 1277, 1459, 1667, 1906, 2178, 2489, 2845

Offset: 1

Graeme McRae, Jun 10 2006

nonn

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

f[s_] := Append[s, Ceiling[Plus @@ s/7]]; Nest[f, {1}, 64] (* Robert G. Wilson v, Jul 07 2006 *)

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

A120202 a(n) = ceiling( Sum_{i=1..n-1} a(i)/9), a(1)=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 18, 20, 22, 25, 28, 31, 34, 38, 42, 47, 52, 58, 64, 71, 79, 88, 98, 109, 121, 134, 149, 166, 184, 205, 227, 253, 281, 312, 347, 385, 428, 476, 528, 587, 652, 725, 805, 895

Offset: 1

Graeme McRae, Jun 10 2006

nonn

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A112088, A011782, A073941, A072493, A120160, A120170, A120178, A120186, A120194.

N:= 100: # to get a(1) to a(N)
S:= 0: A[1]:= 1:
for n from 2 to N do
  S:= S + A[n-1];
  A[n]:= ceil(S/9);
od:
seq(A[n],n=1..N); # Robert Israel, Jul 14 2014

a[s_] := Append[s, Ceiling[Plus @@ s/9]]; Nest[a, {1}, 70] (* Robert G. Wilson v, Jul 07 2006 *)

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

Typo in name corrected by Tom Edgar, Jul 14 2014

A120178 a(n)=ceiling( sum_{i=1..n-1} a(i)/6), a(1)=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 20, 23, 27, 32, 37, 43, 50, 59, 69, 80, 93, 109, 127, 148, 173, 202, 235, 275, 320, 374, 436, 509, 594, 693, 808, 943, 1100, 1283, 1497, 1747, 2038, 2377, 2774, 3236, 3775, 4404, 5138, 5995, 6994

Offset: 1

Graeme McRae, Jun 10 2006

nonn

Cf. A112088, A072493, A011782, A073941, A072493, A120160, A120170, A120186, A120194, A120202.

f[s_] := Append[s, Ceiling[Plus @@ s/5]]; Nest[f, {1}, 61] (* Robert G. Wilson v *)

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

A005427 Josephus problem: numbers m such that, when m people are arranged on a circle and numbered 1 through m, the final survivor when we remove every 4th person is one of the first three people.

Original entry on oeis.org

5, 7, 9, 12, 16, 22, 29, 39, 52, 69, 92, 123, 164, 218, 291, 388, 517, 690, 920, 1226, 1635, 2180, 2907, 3876, 5168, 6890, 9187, 12249, 16332, 21776, 29035, 38713, 51618, 68824, 91765, 122353, 163138, 217517, 290023, 386697, 515596, 687461, 916615, 1222153, 1629538, 2172717, 2896956, 3862608, 5150144, 6866859, 9155812, 12207749, 16276999, 21702665, 28936887, 38582516, 51443354

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

Is this the same as A072493 with its first 8 terms removed? See also the similar conjecture concerning A005428 and A073941.
From Petros Hadjicostas, Jul 20 2020: (Start)
We describe the counting-off game of Burde (1987) using language from Schuh (1968). Suppose m people are labeled with the numbers 1 through m (say clockwise). (Burde uses the numbers 0 through m-1 probably because he relates this problem to the representation of m in the fractional base k/(k-1) = 4/3. He actually modifies the (4/3)-representation of m to include negative coefficients. See the coefficients f(n;k) below.)
Suppose we start the counting at the person labeled 1, and we remove every 4th person. This sequence gives those numbers m for which the last survivor is one of the first three people.
When m = 5, 9, 12, 16, 218, 517, ... the last survivor is the first person.
When m = 7, 29, 69, 92, 291, 388, ... the last survivor is the second person.
When m = 22, 39, 52, 123, 164, 690, ... the last survivor is the third person.
If we know m = a(n) and the number, say i(n), of the last survivor (when there are a(n) people on the circle), we may find a(n+1) and the number i(n+1) of the new last survivor (when there are a(n+1) people on the circle) in the following way:
(a) If 0 = a(n) mod 3, then a(n+1) = (4/3)*a(n), and i(n+1) = i(n).
(b) If 1 = a(n) mod 3 and i(n) = 1, then a(n+1) = ceiling((4/3)*a(n)) and i(n+1) = 3.
(c) If 1 = a(n) mod 3 and i(n) = 2, then a(n+1) = floor((4/3)*a(n)) and i(n+1) = 1.
(d) If 1 = a(n) mod 3 and i(n) = 3, then a(n+1) = floor((4/3)*a(n)) and i(n+1) = 2.
(e) If 2 = a(n) mod 3 and i(n) = 1, then a(n+1) = ceiling((4/3)*a(n)) and i(n+1) = 2.
(f) If 2 = a(n) mod 3 and i(n) = 2, then a(n+1) = ceiling((4/3)*a(n)) and i(n+1) = 3.
(g) If 2 = a(n) mod 3 and i(n) = 3, then a(n+1) = floor((4/3)*a(n)) and i(n+1) = 1. (End)
From Petros Hadjicostas, Jul 22 2020: (Start)
In general, for k >= 2, it seems that when m people are placed on a circle, labeled 1 through m, and every k-th person is removed (starting the counting at person 1), we may determine those m for which the last survivor is in {1, 2, ..., k-1} in the following way.
Define the sequence (T(n;k): n >= 1) by T(n;k) = ceiling(Sum_{s=1..n-1} T(s;k)/(k-1)) for n >= 2 starting with T(1; k) = 1. Then the list of those m's for which the last survivor is in {1, 2, ..., k-1} consists of all the numbers T(n;k) >= k (thus, we exclude the cases m = 1, ..., k-1 that may be repeated more than once in the sequence (T(n;k): n >= 1)).
I do not have a general proof of this conjecture though I strongly believe that Schuh's (1968) way of solving the case k = 3 (see pp. 373-375 and 377-379, where he provides two methods of solution) may provide clues for proving the conjecture.
We have T(n; k=2) = A011782(n+1), T(n; k=3) = A073941(n), T(n; k=4) = A072493(n), T(n; k=5) = A120160(n), T(n; k=6) = A120170(n), T(n; k=7) = A120178(n), T(n; k=8) = A120186(n), T(n; k=9) = A120194(n), and T(n; k=10) = A120202(n).
We also have T(n+1;k) = floor((k/(k-1))*T(n;k)) or ceiling((k/(k-1)*T(n;k)).
To identify the last survivor that results when we place T(n; k) people on the circle (with T(n;k) >= k) in the above Josephus problem, we use a modification of Burde's algorithm due to Thériault (2000).
We use the following recursions but we start at T(k;k) (rather than at the smallest n for which T(n;k) >= k). Define the sequence (S(n;k): n >= 1) by S(n;k) = T(n+k-1; k) for n >= 1. (It is easy to prove that S(1;k) = T(k;k) = 1.)
Define also the sequences (j(n;k): n >= 1) and (f(n;k): n >= 1) by j(1;k) = 1, f(1;k) = 0, f(n+1;k) = ((j(n;k) - S(n;k) - 1) mod (k-1)) + 1 - j(n;k) and j(n+1;k) = j(n;k) + f(n+1;k) for n >= 2.
Then for all n s.t. S(n;k) >= k, j(n;k) is the number of the last survivor of the Josephus problem where every k-th person is removed (provided we start the counting at number 1). It will always be the case that j(n;k) is in {1,2,...,k-1}.
We actually have S(n+1; k) = (k*S(n;k) + f(n+1;k))/(k-1) for n >= 1.
Notice that the Burde-Thériault algorithm is a generalization of Schuh's method. (End)

			From _Petros Hadjicostas_, Jul 22 2020: (Start)
We explain why 5 and 7 are in the sequence but 6 is not.
If we put m = 5 people on the circle, label them 1 through 5, start the counting at person 1, and remove every 4th person, then the list of people who are removed is 4 -> 3 -> 5 -> 2. Thus, the last survivor is 1, so m = 5 is included in this sequence.
If we put m = 6 people on a circle, label them 1 through 6, start the counting at person 1, and remove every 4th person, then the list of people who are removed is 4 -> 2 -> 1 -> 3 -> 6. Thus, the last survivor is 5 (not 1, 2, or 3), so m = 6 is not included in this sequence.
If we put m = 7 people on a circle, label them 1 through 7, start the counting at person 1, and remove every 4th person, then the list of people who are removed is 4 -> 1 -> 6 -> 5 -> 7 -> 3. Thus, the last survivor is 2, so m = 7 is included in this sequence.
Strictly speaking, m = 2 and m = 3 should have been included as well (since clearly the last survivor would be 1 or 2 or 3). In addition, m = 4 should have been included as well because the list of people removed is 4 -> 1 -> 3. The case of number 1 does create a problem since there is no survivor. Note that the numbers 1, 2, 3, 4 are all included in A072493. (End)

Fred Schuh, The Master Book of Mathematical Recreations, Dover, New York, 1968. [This book is cited in Burde (1987). Table 18, p. 374, is related to a very similar sequence (A073941). Thus, definitely, the counting-off games described in the book are related to a similar counting-off game in Burde (1987).]
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, 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.
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

Cf. A005428, A072493.

Similar sequences: A011782 (k = 2), A073941 (k = 3), A072493 (k = 4), A120160 (k = 5), A120170 (k = 6), A120178 (k = 7), A120186 (k = 8), A120194 (k = 9), A120202 (k = 10).

f[s_] := Append[s, Ceiling[5 + Plus@@(s/3)]]; Nest[f, {5}, 100] (* Vladimir Joseph Stephan Orlovsky, Jan 08 2011 *)

/* Gives an n X 2 matrix w s.t. w[,1] are the terms of this sequence and w[,2] are the corresponding numbers of the last survivors (1, 2 or 3). */
lista(nn) = {my(w = matrix(nn,2)); w[1,1] = 5; w[1,2] = 1; for(n=1, nn-1,
if(0 == w[n,1] % 3, w[n+1,1] = w[n,1]*4/3; w[n+1,2] = w[n,2]);
if(1 == w[n,1] % 3 && w[n,2] == 1, w[n+1,1] = ceil(w[n,1]*4/3);  w[n+1,2] = w[n,2] + 2);
if(1 == w[n,1] % 3 && w[n,2] == 2, w[n+1,1] = floor(w[n,1]*4/3); w[n+1,2] = w[n,2] - 1);
if(1 == w[n,1] % 3 && w[n,2] == 3, w[n+1,1] = floor(w[n,1]*4/3); w[n+1,2] = w[n,2] - 1);
if(2 == w[n,1] % 3 && w[n,2] == 1, w[n+1,1] = ceil(w[n,1]*4/3);  w[n+1,2] = w[n,2] + 1);
if(2 == w[n,1] % 3 && w[n,2] == 2, w[n+1,1] = ceil(w[n,1]*4/3);  w[n+1,2] = w[n,2] + 1);
if(2 == w[n,1] % 3 && w[n,2] == 3, w[n+1,1] = floor(w[n,1]*4/3); w[n+1,2] = w[n,2] - 2);
); Vec(w[,1]);} \\ Petros Hadjicostas, Jul 21 2020

/* Second PARI program for the general case of Josephus problem. We use the Burde-Thériault algorithm, not the formula T(n;k) = ceiling(Sum_{s=1..n-1} T(s;k)/(k-1)). We start with T(k;k) = 1 (and omit all previous 1's). Burde starts with the smallest T(n;k) >= k whose corresponding last survivor is 1. This, however, can be very large. 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

a(n) = 5 + ceiling(Sum_{k=1..n-1} a(k)/3). - Petros Hadjicostas, Jul 21 2020

More terms (from the Burde paper, p. 208) from R. J. Mathar, Sep 26 2006

Name edited by Petros Hadjicostas, Jul 20 2020

A348533 Generalized Josephus problem: Let T(m,k), k>=2, m=1,2,3,.., be the number of people on a circle such that the survivor is one of the first k-1 people after every k-th person has been removed.

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 8, 3, 2, 1, 16, 4, 3, 2, 1, 32, 6, 4, 3, 2, 1, 64, 9, 5, 4, 3, 2, 1, 128, 14, 7, 5, 4, 3, 2, 1, 256, 21, 9, 6, 5, 4, 3, 2, 1, 512, 31, 12, 8, 6, 5, 4, 3, 2, 1, 1024, 47, 16, 10, 7, 6, 5, 4, 3, 2, 1, 2048, 70, 22, 12, 8, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Gerhard Kirchner, Oct 21 2021

The table, see example, is read by ascending antidiagonals.

Trivial cases: T(m,k)=m for m

The recurrence in the formula section does not only yield T(m,k), but also the survivor's number S(m,k) so that the Josephus problem can be solved for any number N of people, especially for large N because T(m,k) grows exponentially, see link "Derivation of the recurrence", section II.

T(m,k) compared with other sequences ("->" means that the sequences can be made equal by removing repeated terms, see link "Derivation of the recurrence", section IV).

T(m,2) = A000079(m)=2^(m-1)

T(m,3) -> A073941

T(m,4) -> A072493

T(m+4,4)= A005427(m)

T(m,5) -> A120160

T(m,6) -> A120170

T(m,7) -> A120178

T(m,8) -> A120186

T(m,9) -> A120194

T(m,10)-> A120202

			k=4: 7 people, survivors number 2 <4.
k=4: 6 people, survivors number 5>=4, counterexample.
Table T(m,k) begins:
  m\k____2____3____4____5
   1:    1    1    1    1
   2:    2    2    2    2
   3:    4    3    3    3
   4:    8    4    4    4
   5:   16    6    5    5
   6:   32    9    7    6
   7:   64   14    9    8
   8:  128   21   12   10
   9:  256   31   16   12
  10:  512   47   22   15

Gerhard Kirchner, Derivation of the recurrence
Gerhard Kirchner, Table for 2<=k<=10 and 1<=m<=30
Index entries for sequences related to the Josephus Problem

Cf. A005428, A032434, A054995, A007495.

block(k:10, mmax:30, t:1, s:1, T:[1],
/*Terms T(m,k), m=1 thru mmax */
for m from 1 thru mmax-1 do(
    p:  mod(t, k-1),
    if s>p then e:-p else e:k-1-p,
    t: (k*t+e)/(k-1), s: 1+mod(s+e-1, t),
    T:append(T,[t])),
return (T));

Recurrence for T(m,k) and S(m,k), the survivor's number.
Start: T(1,k)=S(1,k)=1.
T(m+1,k)=(k*T(m,k)+e)/(k-1),
S(m+1,k)=1 + (S(m,k)+e-1) mod T(m+1,k),
with e=-p if S(m,k)>p and e=k-1-p otherwise, p = T(m,k) mod (k-1).

A245400 Number of nonnegative integers with property that their base 9/8 expansion (see A024656) has n digits.

Original entry on oeis.org

9, 9, 9, 9, 9, 9, 9, 9, 9, 18, 18, 18, 18, 27, 27, 27, 36, 36, 45, 45, 54, 63, 72, 81, 90, 99, 108, 126, 144, 162, 180, 198, 225, 252, 288, 324, 360, 405, 459, 513, 576, 648, 729, 819, 927, 1044, 1170, 1314, 1485, 1665, 1872, 2106, 2376, 2673, 3006, 3384, 3807

Offset: 1

Tom Edgar, Jul 21 2014

			a(2) = 9 since 80, 81, 82, 83, 84, 85, 86, 87, 88 are the base 9/8 representations of 9-17 respectively and these are the only integers with 2 digits.

Cf. A245356, A120194, A024656, A081848.

A=[1]
for i in [1..100]:
    A.append(ceil(((9-8)/8)*sum(A)))
[9*x for x in A]

a(n) = 9*A120194(n).

Showing 1-9 of 9 results.

cp's OEIS Frontend

A005428 a(n) = ceiling((1 + sum of preceding terms) / 2) starting with a(0) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Extensions

A120170 a(n) = ceiling( Sum_{i=1..n-1} a(i)/5 ), a(1)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Extensions

A120186 a(n) = ceiling( Sum_{i=1..n-1} a(i)/7 ), a(1) = 1.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Extensions

A120202 a(n) = ceiling( Sum_{i=1..n-1} a(i)/9), a(1)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A120178 a(n)=ceiling( sum_{i=1..n-1} a(i)/6), a(1)=1.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Extensions

A005427 Josephus problem: numbers m such that, when m people are arranged on a circle and numbered 1 through m, the final survivor when we remove every 4th person is one of the first three people.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica