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.
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:
- 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_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).
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
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Aug 22 2017
STATUS
approved