cp's OEIS Frontend

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.

%I A291317 #33 Jul 15 2025 16:03:35
%S A291317 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 A291317 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 A291317 25,41,23,4,43,52,51,57,28,21,11,47,26,29,57,51,48,56,12
%N 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.
%C A291317 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 A291317 No term belongs to A000096 (for the same reason that there are no even positive terms in A006257).
%C A291317 See also A128982 for another variation of the Josephus problem.
%C A291317 a(n) = 1 for n = 1, 2, 3, 18, 22, 171, 195, 234, 1262, 2136, ...
%C A291317 a(n) = n for n = 1, 7, 10, 12, 21, 25, 28, 235, 822, ...
%C A291317 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 A291317 - let L = (1, 2, ..., n) be the list of the first n natural numbers,
%C A291317 - for k = 1 to n-1:
%C A291317    - for i = 1 to f(k): move the first element of L to the end,
%C A291317    - after these moves, discard the first element of L,
%C A291317 - j_f(n) = the remaining element in L.
%C A291317 In particular:
%C A291317 - j_A000012 = A006257,
%C A291317 - j_A007395 = A054995,
%C A291317 - and j_A000027 = a (this sequence),
%C A291317 - see also Links section for the scatterplots of j_f for certain classical or basic functions f.
%C A291317 We have the following properties:
%C A291317 - j_f(1) = 1,
%C A291317 - if f(1) = 1 mod 2 then j_f(2) = 1 else j_f(2) = 2,
%C A291317 - j_f(n) never equals k + Sum_{i=1..k} f(i),
%C A291317 - iterating j_f(n), j_f(j_f(n)), ... eventually leads to a fixed point,
%C A291317 - likely j_f = j_g iff f = g.
%H A291317 Rémy Sigrist, <a href="/A291317/b291317.txt">Table of n, a(n) for n = 1..5000</a>
%H A291317 Rémy Sigrist, <a href="/A291317/a291317.png">Scatterplot of the first 5000 terms of j_A000002 (A000002 = Kolakoski sequence)</a>.
%H A291317 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 A291317 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 A291317 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 A291317 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 A291317 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%e A291317 The different stages for n=6 are (where ^ indicates the counting reference position):
%e A291317 - stage 1:  1^ 2  3  4  5  6
%e A291317 - stage 2:  1     3^ 4  5  6
%e A291317 - stage 3:  1     3  4     6^
%e A291317 - stage 4:  1     3        6^
%e A291317 - stage 5:        3^       6
%e A291317 - stage 6:        3^
%e A291317 Hence, a(6) = 3.
%o A291317 (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])
%Y A291317 Cf. A000002, A000012, A000027, A000096, A000120, A006519, A007395, A006257, A020639, A054868, A054995, A128982.
%K A291317 nonn
%O A291317 1,4
%A A291317 _Rémy Sigrist_, Aug 22 2017