A128982 -id:A128982 - 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.

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

Rémy Sigrist, Aug 22 2017

nonn

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.

			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.

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

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

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])

A128529 Survivor of the Josephus problem, counting direction reversed after each step.

Original entry on oeis.org

1, 1, 1, 1, 3, 4, 1, 3, 5, 1, 9, 8, 3, 3, 11, 1, 15, 7, 7, 18, 19, 16, 3, 7, 15, 24, 25, 18, 9, 28, 19, 24, 7, 13, 21, 5, 31, 20, 11, 15, 21, 32, 3, 11, 31, 7, 39, 23, 25, 15, 35, 1, 47, 32, 15, 54, 55, 48, 9, 19, 39, 60, 59, 58, 63, 7, 49, 50, 11, 40, 27, 70, 63, 48, 23, 27, 47, 74, 67

Offset: 1

R. J. Mathar, May 07 2007

nonn

As in A007495, counting for elimination starts clockwise for the first elimination, then continues counterclockwise from the eliminated place for the second, then toggles again to clockwise for the third elimination and changes direction in that manner after each elimination. Sequence shows original place of the survivor.

			n=5 start with 1,2,3,4,5, count upwards to eliminate 5: 1,2,3,4. Count backwards from 4 over 3 over 2 over 1 to eliminate 4: 1,2,3. Then count forwards from 1 (wrapping around and upwards of 4) over 2 etc. to eliminate 2: 1,3. Count backwards starting at 1 (left of eliminated 2) to eliminate 1 and to leave a(5)=3.

Index entries for sequences related to the Josephus Problem

Cf. A007495, A128982.

a := proc(n) local l,dir,pos,i,c ; dir := 1 ; pos := 0 ; l := [seq(i,i=1..n)] ; for i from 1 to n-1 do pos := pos+n*dir ; pos := 1+((pos-1) mod nops(l)) ; l := subsop(pos=NULL,l) ; dir := -dir ; if dir > 0 then pos := pos-1 ; fi ; od ; RETURN(op(1,l)) ; end: for n from 1 to 85 do printf("%d, ",a(n)) ; od;

A341216 Triangle read by columns T(n,k) k > n >= 1: Last survivor positions in a modified Josephus problem for n numbers, where after each deletion the counting starts over at the lowest existing number n, rather than continuing from the current position.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 1, 2, 3, 4, 1, 1, 1, 1, 2, 1, 2, 3, 4, 5, 6, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 3, 3, 4, 5, 6, 1, 1, 2, 3, 3, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2

Offset: 1

Gary Yane, Feb 06 2021

Arrange 1,2,3,...,n clockwise in a circle. Start the count at the lowest surviving value and delete the k-th value counting clockwise around the circle. Repeat this procedure until one number remains, which is T(n,k).
Note: In the complete n X k array with n >= 1 and k >= 1, T(n,k) = T(k-1,k) for all n >= k > 1 and T(n,1)=n.
That makes the bottom triangle of the array unchanging, so it is omitted.

			n\k    2    3    4    5    6    7    8    9   10   11   12   13
_______________________________________________________________
1      1    1    1    1    1    1    1    1    1    1    1    1
2           2    1    2    1    2    1    2    1    2    1    2
3                2    3    1    3    1    2    2    3    1    3
5                     4    1    4    1    3    3    4    1    4
6                          2    5    1    3    3    5    1    5
7                               6    1    4    3    6    1    6
8                                    2    5    4    7    1    7
9                                         6    5    8    1    8
10                                             6    9    1    9
11                                                 10    1   10
12                                                       2   11
13                                                           12

Index entries for sequences related to the Josephus Problem

The last entry in each column is A128982.

T(1,k) = 1, for k > 1;
T(n,k) = T(n-1,k) if k mod n > T(n-1,k) or k mod n = 0;
T(n,k) = T(n-1,k) + 1 otherwise.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A128529 Survivor of the Josephus problem, counting direction reversed after each step.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A341216 Triangle read by columns T(n,k) k > n >= 1: Last survivor positions in a modified Josephus problem for n numbers, where after each deletion the counting starts over at the lowest existing number n, rather than continuing from the current position.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula