A291317 - OEIS

%I #30 Jun 23 2020 10:27:24

%S 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,

%T 16,26,25,6,32,19,15,21,28,3,12,21,24,13,21,36,17,45,41,45,8,40,11,6,

%U 25,41,23,4,43,52,51,57,28,21,11,47,26,29,57,51,48,56,12

%N 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.

%C 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.

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

%C See also A128982 for another variation of the Josephus problem.

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

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

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

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

%C - for k = 1 to n-1:

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

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

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

%C In particular:

%C - j_A000012 = A006257,

%C - j_A007395 = A054995,

%C - and j_A000027 = a (this sequence),

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

%C We have the following properties:

%C - j_f(1) = 1,

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

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

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

%C - likely j_f = j_g iff f = g.

%H Rémy Sigrist, <a href="/A291317/b291317.txt">Table of n, a(n) for n = 1..5000</a>

%H Rémy Sigrist, <a href="/A291317/a291317.png">Scatterplot of the first 5000 terms of j_A000002 (A000002 = Kolakoski sequence)</a>.

%H Rémy Sigrist, <a href="/A291317/a291317_1.png">Scatterplot of the first 5000 terms of j_A020639 (A020639(n) = least prime dividing n)</a>.

%H Rémy Sigrist, <a href="/A291317/a291317_2.png">Scatterplot of the first 5000 terms of j_A006519 (A006519(n) = highest power of 2 dividing n)</a>.

%H Rémy Sigrist, <a href="/A291317/a291317_3.png">Scatterplot of the first 5000 terms of j_A000120 (A000120(n) = Hamming weight of n)</a>.

%H Rémy Sigrist, <a href="/A291317/a291317_4.png">Scatterplot of the first 5000 terms of j_A054868 (A054868(n) = sum of bits of sum of bits of n)</a>.

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%e The different stages for n=6 are (where ^ indicates the counting reference position):

%e - stage 1:  1^ 2  3  4  5  6

%e - stage 2:  1     3^ 4  5  6

%e - stage 3:  1     3  4     6^

%e - stage 4:  1     3        6^

%e - stage 5:        3^       6

%e - stage 6:        3^

%e Hence, a(6) = 3.

%o (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])

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

%K nonn

%O 1,4

%A _Rémy Sigrist_, Aug 22 2017