A291317 A variation of the Josephus problem: a(n) is the surviving integer under the following elimination process. Arrange 1,2,3,...,n in a circle, increasing clockwise. Starting with i=1, at k-th stage, move k places clockwise and delete the current number.

1, 1, 1, 3, 4, 3, 7, 7, 6, 10, 7, 12, 3, 10, 11, 7, 11, 1, 12, 6, 21, 1, 7, 12, 25, 3, 25, 28, 16, 26, 25, 6, 32, 19, 15, 21, 28, 3, 12, 21, 24, 13, 21, 36, 17, 45, 41, 45, 8, 40, 11, 6, 25, 41, 23, 4, 43, 52, 51, 57, 28, 21, 11, 47, 26, 29, 57, 51, 48, 56, 12

Offset: 1

Author

Rémy Sigrist, Aug 22 2017

Keywords

• nonn

Comments

In the classical Josephus problem (A006257), one moves one place clockwise at each stage, and in the A054995 version, one moves two places clockwise at each stage; here, on the other hand, the number of moves is progressive, and the resulting sequence seems random.

No term belongs to A000096 (for the same reason that there are no even positive terms in A006257).

See also A128982 for another variation of the Josephus problem.

a(n) = 1 for n = 1, 2, 3, 18, 22, 171, 195, 234, 1262, 2136, ...

a(n) = n for n = 1, 7, 10, 12, 21, 25, 28, 235, 822, ...

More formally, for any function f over the natural numbers, let us define the function j_f with these rules: for any n > 0:

- let L = (1, 2, ..., n) be the list of the first n natural numbers,

- for k = 1 to n-1:

- for i = 1 to f(k): move the first element of L to the end,

- after these moves, discard the first element of L,

- j_f(n) = the remaining element in L.

In particular:

- j_A000012 = A006257,

- j_A007395 = A054995,

- and j_A000027 = a (this sequence),

- see also Links section for the scatterplots of j_f for certain classical or basic functions f.

We have the following properties:

- j_f(1) = 1,

- if f(1) = 1 mod 2 then j_f(2) = 1 else j_f(2) = 2,

- j_f(n) never equals k + Sum_{i=1..k} f(i),

- iterating j_f(n), j_f(j_f(n)), ... eventually leads to a fixed point,

- likely j_f = j_g iff f = g.

Examples

			The different stages for n=6 are (where ^ indicates the counting reference position):
- stage 1:  1^ 2  3  4  5  6
- stage 2:  1     3^ 4  5  6
- stage 3:  1     3  4     6^
- stage 4:  1     3        6^
- stage 5:        3^       6
- stage 6:        3^
Hence, a(6) = 3.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..5000
• Rémy Sigrist, Scatterplot of the first 5000 terms of j_A000002 (A000002 = Kolakoski sequence).
• Rémy Sigrist, Scatterplot of the first 5000 terms of j_A020639 (A020639(n) = least prime dividing n).
• Rémy Sigrist, Scatterplot of the first 5000 terms of j_A006519 (A006519(n) = highest power of 2 dividing n).
• Rémy Sigrist, Scatterplot of the first 5000 terms of j_A000120 (A000120(n) = Hamming weight of n).
• Rémy Sigrist, Scatterplot of the first 5000 terms of j_A054868 (A054868(n) = sum of bits of sum of bits of n).
• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A000002, A000012, A000027, A000096, A000120, A006519, A007395, A006257, A020639, A054868, A054995, A128982.

Programs

PARI

a(n) = my (l = List(vector(n,i,i)), i = 0); for (k = 1, n-1, i += k; my (p = i \ #l); listpop(l, 1 + (i % #l)); i -= p); return (l[1])