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

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.

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

Example

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.

Prog

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

Crossrefs

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

Sequence in context: A371858 A111970 A337493 * A141730 A127737 A358125

Adjacent sequences: A291314 A291315 A291316 * A291318 A291319 A291320

Keyword

nonn

Author

Rémy Sigrist, Aug 22 2017

Status

approved