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