cp's OEIS Frontend

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

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)