A225381 Elimination order of the first person in a Josephus problem.

1, 2, 2, 4, 3, 5, 4, 8, 5, 8, 6, 11, 7, 11, 8, 16, 9, 14, 10, 18, 11, 17, 12, 23, 13, 20, 14, 25, 15, 23, 16, 32, 17, 26, 18, 32, 19, 29, 20, 38, 21, 32, 22, 39, 23, 35, 24, 47, 25, 38, 26, 46, 27, 41, 28, 53, 29, 44, 30, 53, 31, 47, 32, 64, 33, 50, 34, 60, 35

Offset: 1

Author

Marcus Hedbring, May 17 2013

Keywords

• nonn

Comments

In a Josephus problem such as A006257, a(n) is the order in which the person originally first in line is eliminated.

The number of remaining survivors after the person originally first in line has been eliminated, i.e., n-a(n), gives the fractal sequence A025480.

For the linear version, see A225489.

Examples

			If there are 7 persons to begin with, they are eliminated in the following order: 2,4,6,1,5,3,7. So the first person (the person originally first in line) is eliminated as number 4. Therefore a(7) = 4.
		

Links

• Stefano Spezia, Table of n, a(n) for n = 1..10000
• Cristina Ballantine and Mircea Merca, Plane Partitions and Divisors, Symmetry (2024), Vol. 16, Iss. 5. See page 9.
• Mircea Merca, Plane Partitions and a Problem of Josephus, Mathematics (2023), Vol. 11, Iss. 4996. See page 2.
• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A006257, A006519, A025480, A225489.

Programs

Mathematica

t = {1}; Do[AppendTo[t, If[OddQ[n], (n + 1)/2, t[[n/2]] + n/2]], {n, 2, 100}]; t (* T. D. Noe, May 17 2013 *)

Formula

a(n) = (n+1)/2 (odd n); a(n) = a(n/2) + n/2 (even n).

a(n) = n - A025480(n).

G.f.: Sum{n>=1} x^n/(1-x^A006519(n)). - Nicolas Nagel, Mar 19 2018