A088333 -id:A088333 - cp's OEIS frontend

A181281 A version of 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, delete the integer 4 places clockwise from i. Repeat, counting 4 places from the next undeleted integer, until only one integer remains.

1, 2, 1, 2, 2, 1, 6, 3, 8, 3, 8, 1, 6, 11, 1, 6, 11, 16, 2, 7, 12, 17, 22, 3, 8, 13, 18, 23, 28, 3, 8, 13, 18, 23, 28, 33, 1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, 61, 66, 71, 3, 8, 13, 18, 23, 28, 33, 38

Offset: 1

Paul Weisenhorn, Oct 10 2010

nonn

			a(7) = 6: (^1,2,3,4,5,6,7) -> (1,2,3,4,^6,7) -> (1,2,^4,6,7) -> (1,^4,6,7) -> (1,^6,7) -> (^1,6) -> (^6).
a(14) = 11 => a(15) = (a(14)+4) mod 15 + 1 = 1.

Paul Weisenhorn, Josephus und seine Folgen, MNU Journal (Der mathematische und naturwissenschaftliche Unterricht), 59 (2006), 18-19.

Index entries for sequences related to the Josephus Problem

Cf. A006257, A054995, A088333.

a:= proc(n) option remember;
      `if` (n=1, 1, (a(n-1)+4) mod n +1)
    end:
seq (a(n), n=1..100);

a[1] = 1; a[n_] := a[n] = Mod[a[n-1]+4, n]+1; Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Oct 18 2013 *)

a(n) = (a(n-1) + 4) mod n + 1 if n>1, a(1) = 1.

Edited by Alois P. Heinz, Sep 06 2011

A198789 Array T(n,k) read by antidiagonals: Last survivor positions in Josephus problem for n numbers and a count of k, n >= 1, k >= 1.

Original entry on oeis.org

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

Offset: 1

William Rex Marshall, Nov 21 2011

Arrange 1, 2, 3, ..., n clockwise in a circle. Starting the count at 1, delete every k-th integer clockwise until only one remains, which is T(n,k).
The main diagonal (1, 1, 2, 2, 2, 4, 5, 4, ...) is A007495.
Concatenation of consecutive rows (up to the main diagonal) gives A032434.
The periods of the rows, (1, 2, 6, 12, 60, 60, 420, 840, ...), is given by A003418.

			.n\k  1  2  3  4  5  6  7  8  9 10
----------------------------------
.1 |  1  1  1  1  1  1  1  1  1  1
.2 |  2  1  2  1  2  1  2  1  2  1
.3 |  3  3  2  2  1  1  3  3  2  2
.4 |  4  1  1  2  2  3  2  3  3  4
.5 |  5  3  4  1  2  4  4  1  2  4
.6 |  6  5  1  5  1  4  5  3  5  2
.7 |  7  7  4  2  6  3  5  4  7  5
.8 |  8  1  7  6  3  1  4  4  8  7
.9 |  9  3  1  1  8  7  2  3  8  8
10 | 10  5  4  5  3  3  9  1  7  8

William Rex Marshall, First 141 antidiagonals of array, flattened
Index entries for sequences related to the Josephus Problem

Cf. A000027 (k = 1), A006257 (k = 2), A054995 (k = 3), A088333 (k = 4), A181281 (k = 5), A360268 (k = 6), A178853 (k = 7), A109630 (k = 8).

Cf. A003418, A007495 (main diagonal), A032434, A198788, A198790.

T[n_, k_] := T[n, k] = If[n == 1, 1, Mod[T[n-1, k]+k-1, n]+1];
Table[T[n-k+1, k], {n, 1, 13}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Mar 04 2023 *)

T(1,k) = 1; for n > 1: T(n,k) = ((T(n-1,k) + k - 1) mod n) + 1.

A384774 Elimination order of the first person in a variation of the Josephus problem in which first three people are skipped, then one is eliminated, repeating until all n people are eliminated.

Original entry on oeis.org

1, 2, 1, 2, 5, 3, 2, 5, 9, 8, 3, 12, 6, 10, 4, 16, 12, 16, 5, 9, 20, 10, 6, 22, 21, 23, 7, 27, 13, 21, 8, 30, 23, 20, 9, 16, 31, 17, 10, 31, 24, 35, 11, 34, 20, 27, 12, 28, 34, 49, 13, 23, 31, 24, 14, 49, 55, 34, 15, 35, 27, 59, 16, 44, 38, 60, 17, 30, 53, 31

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Jun 09 2025

nonn

a(4k-1) = k

a(n) = A384770(n,1).

			Consider n = 4 people. The first person eliminated is number 4. This leaves the remaining people in order 1, 2, 3. On the second step, we eliminate person number 1, implying that the order of elimination of the first person is 2: a(4) = 2.

Cf. First column of A384770.

Cf. A225381, A384772, A088333.

A384774 := proc(n::integer)
    local plist,eli,skip,ptr ;
    plist := [seq(i,i=1..n)] ;
    eli :=1 ;
    skip := 3;
    ptr := 0 ;
    while true do
        ptr := modp(ptr+skip,nops(plist)) ;
        if op(ptr+1,plist) = 1 then
            return eli ;
        end if;
        plist := subsop(ptr+1=NULL,plist) ;
        eli := eli+1 ;
    end do:
end proc:
seq(A384774(n),n=1..100) ; # R. J. Mathar, Jul 30 2025

def a(n):
    c, i, J = 1, 0, list(range(1, n+1))
    while len(J) > 0:
        i = (i + 3)%len(J)
        q = J.pop(i)
        if q == 1: return c
        c = c+1
print([a(n) for n in range(1, 71)])

A198788 Array T(k,n) read by descending antidiagonals: Last survivor positions in Josephus problem for n numbers and a count of k, n >= 1, k >= 1.

Original entry on oeis.org

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

Offset: 1

William Rex Marshall, Nov 21 2011

Arrange 1, 2, 3, ... n clockwise in a circle. Starting the count at 1, delete every k-th integer clockwise until only one remains, which is T(k,n).
The main diagonal of the array (1, 1, 2, 2, 2, 4, 5, 4, ...) is A007495.
Consecutive columns down to the main diagonal (1, 2, 1, 3, 3, 2, 4, 1, 1, 2, ...) is A032434.
Period lengths of columns (1, 2, 6, 12, 60, 60, 420, 840, ...) is A003418.

			.k\n  1  2  3  4  5  6  7  8  9 10
----------------------------------
.1 |  1  2  3  4  5  6  7  8  9 10  A000027
.2 |  1  1  3  1  3  5  7  1  3  5  A006257
.3 |  1  2  2  1  4  1  4  7  1  4  A054995
.4 |  1  1  2  2  1  5  2  6  1  5  A088333
.5 |  1  2  1  2  2  1  6  3  8  3  A181281
.6 |  1  1  1  3  4  4  3  1  7  3
.7 |  1  2  3  2  4  5  5  4  2  9  A178853
.8 |  1  1  3  3  1  3  4  4  3  1  A109630
.9 |  1  2  2  3  2  5  7  8  8  7
10 |  1  1  2  4  4  2  5  7  8  8

William Rex Marshall, First 141 antidiagonals of array, flattened
Index entries for sequences related to the Josephus Problem

Cf. A000027 (k = 1), A006257 (k = 2), A054995 (k = 3), A088333 (k = 4), A181281 (k = 5), A178853 (k = 7), A109630 (k = 8).

Cf. A003418, A007495 (main diagonal), A032434, A198789, A198790.

T(k,1) = 1;

for n > 1: T(k,n) = ((T(k,n-1) + k - 1) mod n) + 1.

A384770 Triangle T(n,k) read by rows, where row n is a permutation of the numbers 1 through n, such that if a deck of n cards is prepared in this order, and under-under-under-down dealing is used, then the resulting cards will be dealt in increasing order.

Original entry on oeis.org

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

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Jun 09 2025

Under-under-under-down dealing is a dealing pattern where the top three cards are placed at the bottom of the deck, and then the next card is dealt. This pattern repeats until all of the cards have been dealt.
This card dealing can equivalently be seen as a variation on the Josephus problem where every 4th person is eliminated. T(n,k) is the number of eliminations in the Josephus problem that occur before the k-th person is eliminated. Equivalently, each row of T is the inverse permutation of the corresponding row of the Josephus triangle A384772, i.e. A384772(n,T(n,k)) = k.
The total number of moves for row n is 4n.
The first column is A384774(n), the order of elimination of the first person in the Josephus problem.
The index of the largest number in row n is A088333(n), corresponding to the index of the freed person in the corresponding Josephus problem.
T(n,4j) = j, for 4j <= n.

			Consider a deck of four cards arranged in the order 2,4,3,1. If we put the top 3 cards under and deal the next card, we will deal card number 1. Now the deck is ordered 2,4,3. If we place 3 cards under and deal the next one, we will deal card number 2, and be left with cards 4,3. Again placing 3 cards under and dealing the next, we will deal card number 3, leaving card number 4 to be dealt last. The dealt cards are in order. Thus, the fourth row of the triangle is 2,4,3,1.
The triangle begins as follows:
 1
 2, 1;
 1, 3, 2;
 2, 4, 3, 1;
 5, 4, 2, 1, 3;
 3, 2, 4, 1, 6, 5;
 2, 7, 6, 1, 4, 3, 5;
 5, 4, 6, 1, 3, 8, 7, 2;
 9, 8, 3, 1, 6, 5, 7, 2, 4

Cf. A378635, A321298, A006257, A225381, A008586, A384772, A088333, A384774.

def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 1:
        i = (i + 3)%len(J)
        out.append(J.pop(i))
    out += [J[0]]
    return [out.index(j)+1 for j in list(range(1, n+1))]
print([e for n in range(1, 14) for e in row(n)])

T(n, 4) = 1 for n >= 4

T(n, k) = T(n-1, k-4 mod n) + 1 if k !== 4 (mod n).

A384772 Triangle read by row: T(n,k) is the number of the k-th eliminated person in a variant of the Josephus problem in which first three people are skipped, then one is eliminated, repeating until all n people are eliminated.

Original entry on oeis.org

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

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Jun 09 2025

The numbers 1 through n are arranged in a circle. A pointer starts at position 1. With each turn, the pointer skips three numbers and the next number is eliminated. The process repeats until no numbers remain. This sequence is a concatenation of the rows of the triangle T, where T(n, k) is the elimination order of the k-th number in a circle of n numbers.

This variation of the Josephus problem can equivalently be described in terms of under-under-under-down card dealing, where the cards of a deck are dealt by alternately cycling three cards from the top "under", and then dealing the next card "down". In particular, T(n,k) is the k-th card dealt in under-under-under-down dealing if the deck begins in order 1,2,3,...,n.

			Consider 4 people in a circle. Initially, people numbered 1, 2, and 3 are skipped, and person 4 is eliminated. The remaining people are now in order 1, 2, 3. Then all three are skipped and person 1 is eliminated. The remaining people are in order 2, 3. Now, we skip over 2, 3, 2 and eliminate person 3. Person 2 is eliminated last. Thus, the fourth row of the triangle is 4, 1, 3, 2.
The triangle begins as follows:
  1;
  2, 1;
  1, 3, 2;
  4, 1, 3, 2;
  4, 3, 5, 2, 1;
  4, 2, 1, 3, 6, 5;
  4, 1, 6, 5, 7, 3, 2;
  4, 8, 5, 2, 1, 3, 7, 6;
  4, 8, 3, 9, 6, 5, 7, 2, 1

Cf. A378635, A321298, A006257, A225381, A008586, A384770, A088333, A384774.

def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 0:
        i = (i + 3)%len(J)
        out.append(J.pop(i))
    return out
print([e for n in range(1, 14) for e in row(n)])

A360268 A version 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, delete the integer 5 places clockwise from i. Repeat, counting 5 places from the next undeleted integer, until only one integer remains.

Original entry on oeis.org

1, 1, 1, 3, 4, 4, 3, 1, 7, 3, 9, 3, 9, 1, 7, 13, 2, 8, 14, 20, 5, 11, 17, 23, 4, 10, 16, 22, 28, 4, 10, 16, 22, 28, 34, 4, 10, 16, 22, 28, 34, 40, 3, 9, 15, 21, 27, 33, 39, 45, 51, 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 3, 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 1, 7, 13, 19, 25

Offset: 1

Benjamin Lilley, Jan 31 2023

nonn

			a(7) = 3 because the elimination process gives (^1,2,3,4,5,6,7) -> (1,2,3,4,5,^7) -> (1,2,3,4,^7) -> (^1,2,3,4) -> (1,^3,4) -> (^3,4) -> (3), where ^ denotes the counting reference position.
a(13) = 9 => a(14) = (a(13) + 5) mod 14 + 1 = 1.

Wikipedia, Josephus problem.
Index entries for sequences related to the Josephus Problem.

6th column of A198789.

Cf. A006257, A054995, A088333, A181281.

a[1] = 1; a[n_] := a[n] = Mod[a[n - 1] + 5, n] + 1; Array[a, 100] (* Amiram Eldar, Feb 03 2023 *)

def A360268_up_to_n(n):
  val = 1
  return [val := (val + 5) % i + 1 for i in range(1,n+1)]

a(n) = (a(n-1) + 5) mod n + 1 if n > 1, a(1) = 1.

A385327 The numbers of people such that, in the variant of the Josephus problem in which three people are skipped and then one is eliminated, the first person is the last to be eliminated.

Original entry on oeis.org

1, 2, 5, 9, 12, 16, 218, 517, 1226, 6890, 12249, 16332, 21776, 38713, 122353, 687461, 1222153, 51443354, 385389994, 1218022698, 1624030264, 2887164914, 5132737625, 9124866889, 28839085477, 162036891790, 910429504490, 2877406829006, 5115389918233, 510385736583765

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Jun 25 2025

nonn

This sequence can be used in magic tricks with under-under-under-down dealing pattern. The deck sizes in this sequence guarantee that after the dealing, the last dealt card is the one that was initially on top.
The classical Josephus problem corresponds to under-down dealing. In this case, the first person is freed when the number of people is a power of 2: A000079.
If two people are skipped, then the corresponding sequence is A081614.

			Suppose there are 5 people in a circle. After three people are skipped, the person number 4 is eliminated. The leftover people are 5,1,2,3 in order. Then person number 3 eliminated, and the leftover people are 5,1,2 in order. Then person number 5 is eliminated, and the leftover people are 1,2 in order. Then person number 2 is eliminated, and person 1 is freed. Thus, 5 is in this sequence.

Cf. A000079, A081614, A088333, A384770, A384772, A384774, A385333.

def freed_person_sequence_periodic(trailingUs, periodic_portion, numterms):
    freed_person_table=[[0] for i in periodic_portion]
    for i in range(numterms):
        extend_freed_person_sequence(periodic_portion, freed_person_table)
    return [(freed_person_table[0][N] - trailingUs)%(N+1)+1 for N in range(len(freed_person_table[0]))]
def extend_freed_person_sequence(periodic_portion, freed_person_table):
    for offset in range(len(periodic_portion)):
        first_death = periodic_portion[offset]
        remaining_survivor = freed_person_table[(offset + 1)%len(periodic_portion)][len(freed_person_table[offset])-1]
        if remaining_survivor + first_death + 1 < len(freed_person_table[offset])+ 1:
            freed_person_table[offset].append(remaining_survivor + first_death + 1)
        else:
            freed_person_table[offset].append((remaining_survivor + first_death + 1) % (len(freed_person_table[offset]) + 1))
def first_freers_periodic(trailingUs, periodic_portion, numterms):
    freed_seq = freed_person_sequence_periodic(trailingUs, periodic_portion, numterms)
    return [i+1 for i in range(len(freed_seq)) if freed_seq[i] == 1]
print(first_freers_periodic(0, [3], 100000000))

More terms from Jinyuan Wang, Jul 01 2025

A385333 The numbers of people such that, in the variant of the Josephus problem in which three people are skipped and then one is eliminated, the last person is the last to be eliminated.

Original entry on oeis.org

1, 21, 38, 51, 122, 163, 689, 919, 2906, 3875, 5167, 51617, 68823, 163137, 290022, 1629537, 6866858, 9155811, 16276998, 28936886, 38582515, 121939802, 162586403, 216781871, 289042495, 513853325, 685137767, 913517023, 2165373685, 12166489185, 38452113969, 121527668842

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Jun 25 2025

nonn

This sequence can be used in magic tricks with under-under-under-down dealing pattern. The deck sizes in this sequence guarantee that after the dealing, the last card dealt is the one that was initially on the bottom.

			Suppose there are 5 people in a circle. After three people are skipped, the person number 4 is eliminated. The leftover people are 5,1,2,3 in order. Then person number 3 eliminated, and the leftover people are 5,1,2 in order. Then person number 5 is eliminated, and the leftover people are 1,2 in order. Then person number 2 is eliminated, and person 1 is freed. Thus, 5 is NOT in this sequence.

Cf. A088333, A384770, A384772, A384774, A385327.

Cf. A000225 (for skip 1 take 1), A182459 (for skip 2 take 1).

More terms from Jinyuan Wang, Jul 01 2025

cp's OEIS Frontend

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A198789 Array T(n,k) read by antidiagonals: Last survivor positions in Josephus problem for n numbers and a count of k, n >= 1, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A384774 Elimination order of the first person in a variation of the Josephus problem in which first three people are skipped, then one is eliminated, repeating until all n people are eliminated.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Python

A198788 Array T(k,n) read by descending antidiagonals: Last survivor positions in Josephus problem for n numbers and a count of k, n >= 1, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A384770 Triangle T(n,k) read by rows, where row n is a permutation of the numbers 1 through n, such that if a deck of n cards is prepared in this order, and under-under-under-down dealing is used, then the resulting cards will be dealt in increasing order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

A384772 Triangle read by row: T(n,k) is the number of the k-th eliminated person in a variant of the Josephus problem in which first three people are skipped, then one is eliminated, repeating until all n people are eliminated.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A385327 The numbers of people such that, in the variant of the Josephus problem in which three people are skipped and then one is eliminated, the first person is the last to be eliminated.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs