A054995 -id:A054995 - cp's OEIS frontend

A081615 Subsequence of A005428 where state = 2.

1, 2, 3, 14, 21, 47, 158, 237, 533, 1199, 4046, 6069, 13655, 46085, 103691, 1181102, 1771653, 3986219, 102162425, 229865456, 344798184, 517197276, 775795914, 1163693871, 3927466814, 5891200221, 13255200497, 29824201118, 44736301677, 100656678773, 226477527239, 764361654431, 2579720583704, 3869580875556, 5804371313334, 8706556970001, 19589753182502, 29384629773753, 66115416990944, 99173125486416

Offset: 0

N. J. A. Sloane, Apr 23 2003

Excluding the initial 1, the values of n such that A054995(n) = 2. - Ryan Brooks, Jul 17 2020
From Petros Hadjicostas, Jul 20 2020: (Start)
From a(1) = 2 to a(22) = 775795914, the values appear in Table 18 (p. 374) in Schuh (1968) under the Survivor No. 2 column (in a variation of Josephus's counting off game where m people on a circle are labeled 1 through m and every third person drops out).
a(23) here is 1163693871 but 1063693871 in Schuh (1968). Burde (1987) agrees with Schuh (1968). See the table on p. 207 of the paper (with q = 1).
It seems Schuh (1968) made a calculation error and Burde (1987) copied it. See my comment for A073941 for more details. (End)

Fred Schuh, The Master Book of Mathematical Recreations, Dover, New York, 1968. [See Table 18, p. 374.]

David A. Corneth, Table of n, a(n) for n = 0..2862
K. Burde, Das Problem der Abzählreime und Zahlentwicklungen mit gebrochenen Basen [The problem of counting rhymes and number expansions with fractional bases], J. Number Theory 26(2) (1987), 192-209. [The author deals with the representation of n in fractional bases k/(k-1) and its relation to counting-off games. Here k = 3. See the table on p. 207. See also the review in MathSciNet (MR0889384) by R. G. Stoneham.]
Index entries for sequences related to the Josephus Problem

Cf. A005428, A073941, A081614.

/* In the program below, we use a truncated version of either A005428 or A073941 and choose those terms that correspond to "state" or "number of last survivor" equal to 2. See A073941 or Schuh (1968) for more details. */
first(n) = {my(res = vector(n), t = 1, wn = wo = gn = go = 2); res[1] = 1; for(i = 1, oo, c = wo % 2; if(go == 2, t++; res[t] = wo; if(t >= n, return(res))); wn = floor(wo*3/2) + c * (2 - go); gn = 3 * c + go * (-1)^c; wo = wn; go = gn; )} \\ David A. Corneth and Petros Hadjicostas, Jul 21 2020

More terms from Hans Havermann, Apr 23 2003

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.

Original entry on oeis.org

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

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.

A380195 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-down dealing is used, then the resulting cards will be dealt in increasing order.

Original entry on oeis.org

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

Offset: 1

Tanya Khovanova and the MIT PRIMES STEP junior group, Jan 15 2025

Under-under-down dealing is a dealing pattern where the top card is placed at the bottom of the deck, then the next card is also 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 is related to a variation on the Josephus problem, where two people are skipped, and the third person is eliminated. The card in row n and column k is x if and only if in the corresponding Josephus problem with n people, the person number x is the k-th person eliminated. Equivalently, each row of Josephus triangle A381667 is an inverse permutation of the corresponding row of this triangle.
The total number of moves for row n is 3n.
The first column is A381591, the order of elimination of the first person in the Josephus problem.
The index of the largest number in row n is A054995(n), corresponding to the index of the freed person in the corresponding Josephus problem.
T(n,3j) = j, for 3j <= n.

			Consider a deck of four cards arranged in the order 4,2,1,3. Card 4 goes under, card 2 goes under, and card 1 is dealt. Now the deck is ordered 3,4,2. Card 3 goes under, card 4 goes under, and card 2 is dealt. Now the leftover deck is ordered 3,4. Card 3 goes under, card 4 goes under, and card 3 is dealt. Then card 4 is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 4,2,1,3.
Table begins:
  1 ;
  1, 2;
  2, 3, 1;
  4, 2, 1, 3;
  2, 4, 1, 5, 3;
  6, 4, 1, 3, 5, 2;
  6, 3, 1, 7, 5, 2, 4;
  3, 5, 1, 7, 4, 2, 8, 6;
  9, 7, 1, 4, 6, 2, 8, 5, 3;

Cf. A006257, A054995, A225381, A321298, A378635, A380195, A008585, A381591 A381667.

def UUD(n):
    return invPerm(UUDES(n))
def UUDES(n):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=2
        index=index%len(l)
        P.append(l[index])
        l.pop(index)
    return P
def invPerm(p):
    inv = []
    for i in range(len(p)):
        inv.append(None)
    for i in range(len(p)):
        inv[p[i]-1]=i+1
    return inv
sequence = []
for i in range(1,20):
    sequence += [str(v) for v in UUD(i)]
print(", ".join(sequence))

def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 0:
        i = (i + 2)%len(J)
        out.append(J.pop(i))
    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)]) # Michael S. Branicky, Mar 27 2025

T(n, 3 mod n) = 1

T(n, k) = T(n-1, k-3 mod n) + 1 if k != 3 mod n, where "a mod b" denotes the representative of the a's modular equivalence class in {0, ..., b-1}.

A381591 Elimination order of the first person in a variation of the Josephus problem, where there are n people total and two people are skipped each time.

Original entry on oeis.org

1, 1, 2, 4, 2, 6, 6, 3, 9, 6, 4, 7, 11, 5, 11, 15, 6, 13, 11, 7, 12, 16, 8, 23, 18, 9, 22, 16, 10, 17, 31, 11, 27, 30, 12, 35, 21, 13, 22, 37, 14, 30, 35, 15, 32, 26, 16, 27, 35, 17, 47, 37, 18, 53, 31, 19, 32, 47, 20, 57, 56, 21, 51, 36, 22, 37, 65, 23, 49, 70

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Mar 02 2025

nonn

a(3k-1) = k.

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

Cf. A006257, A054995, A225381, A321298, A378635, A380195, A008585, A381591 A381667.

def UUD(n):
    return invPerm(UUDES(n))
def UUDES(n):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=2
        index=index%len(l)
        P.append(l[index])
        l.pop(index)
    return P
def invPerm(p):
    inv = []
    for i in range(len(p)):
        inv.append(None)
    for i in range(len(p)):
        inv[p[i]-1]=i+1
    return inv
sequence = []
for i in range(1, 71):
    sequence += [str(UUD(i)[0])]
print(", ".join(sequence))

def a(n):
    c, i, J = 1, 0, list(range(1, n+1))
    while len(J) > 0:
        i = (i + 2)%len(J)
        q = J.pop(i)
        if q == 1: return c
        c = c+1
print([a(n) for n in range(1, 71)]) # Michael S. Branicky, Mar 24 2025

A381667 Triangle read by row: T(n,k) is the number of the k-th eliminated person in the variation of the Josephus elimination process for n people where two people are skipped each step.

Original entry on oeis.org

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

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Mar 03 2025

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

This variation of the Josephus problem is related to under-under-down card dealing, where the cards of a deck are dealt by alternately cycling two 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-down dealing if the deck begins in order 1,2,3,...,n.

			Consider 4 people in a circle. Initially, people numbered 1 and 2 are skipped, and person 3 is eliminated. The remaining people are now in order 4, 1, 2. Then 4 and 1 are skipped, and person 2 is eliminated. The remaining people are in order 4, 1. Now, 4 and 1 are skipped, and 4 is eliminated. Person 1 is eliminated last. Thus, the fourth row of the triangle is 3, 2, 4, 1.
Triangle begins;
  1;
  1, 2;
  3, 1, 2;
  3, 2, 4, 1;
  3, 1, 5, 2, 4;
  3, 6, 4, 2, 5, 1;
  3, 6, 2, 7, 5, 1, 4;
  3, 6, 1, 5, 2, 8, 4, 7;

Cf. A006257, A054995, A225381, A321298, A378635, A380195, A008585, A381591 A381667.

def UUDES(n):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=2
        index=index%len(l)
        P.append(l[index])
        l.pop(index)
    return P
def invPerm(p):
    inv = []
    for i in range(len(p)):
        inv.append(None)
    for i in range(len(p)):
        inv[p[i]-1]=i+1
    return inv
sequence = []
for i in range(1,20):
    sequence += [str(v) for v in UUDES(i)]
print(", ".join(sequence))

def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 0:
        i = (i + 2)%len(J)
        out.append(J.pop(i))
    return out
print([e for n in range(1, 14) for e in row(n)]) # Michael S. Branicky, Mar 24 2025

A083287 Continued fraction expansion of K(3), a constant related to the Josephus problem.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 5, 10, 19, 1, 4, 4, 4, 3, 10, 1, 42, 2, 23, 33, 1, 4, 7, 1, 12, 1, 1, 2, 9, 2, 11, 3, 4, 1, 1, 3, 2, 4, 25, 3, 1, 16, 5, 10, 1, 1, 1, 3, 1, 1, 1, 3, 2, 2, 1, 1, 1, 2, 3, 2, 1, 3, 4, 3, 1, 1, 117, 2, 1, 12, 4, 1, 4, 3, 3, 15, 1, 5, 16, 7, 2, 7, 21, 1, 3, 1, 2, 2, 2, 1, 1, 1, 1

Offset: 0

Ralf Stephan, Apr 23 2003

The constant K(3)=1.62227050288476731595695... is related to the Josephus problem with q=3 and the computation of A054995.

A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33, 235-240, 1991.
Index entries for sequences related to the Josephus Problem

Cf. A054995, A083286 (decimal expansion).

For[p = 1; nn = 10^4; n = 1, n <= nn, n++, p = Ceiling[3/2*p]]; p/(3/2)^nn // ContinuedFraction[#, 93] & (* Jean-François Alcover, Jul 11 2013, after Pari *)

p=1; N=10^4; for(n=1, N, p=ceil(3/2*p)); c=(p/(3/2)^N)+0. \\ This gives K(3) not the sequence!

Offset changed by Andrew Howroyd, Aug 07 2024

A343780 If n good guys followed by n bad guys stand in a circle, a(n) is the least q such that executing every q-th person gets all bad guys first.

Original entry on oeis.org

2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657, 2504881, 13482720, 25779600, 68468401, 610346880, 1271932200, 327280800, 11605393800, 10071626400, 270022896000, 212719197601, 673534461600, 80276676481, 7618206526561, 14227357636801

Offset: 1

Nicholas Matteo, Apr 29 2021

nonn

There are 2n people in a circle, numbered 1 through 2n; the first n are "good guys" and the last n are "bad guys." We count, starting from 1, to the q-th person, who is executed; then, starting from the next position, repeat until all bad guys are gone.
This is a variant of the Josephus problem. In exercise 1.21 of Concrete Mathematics, it is proved there is always a q such that all bad guys are executed before any good guys, namely the least common multiple of n+1, n+2, ..., 2n (which provides an upper bound for a(n)).
According to Ball and Coxeter, in medieval times this was called the "Turks and Christians problem", described as n Turks and n Christians aboard a ship in a storm, which will sink unless half the passengers are thrown overboard; every q-th person will be tossed in the sea.
Schumer (2002) mentions this version along with more variants (e.g., eliminating all odd-numbered people first) in the section "Subsets marked for elimination".
Graham, Knuth and Patashnik say a non-rigorous argument suggests that a "random" value of q will succeed with probability (n/(2n)) * ((n-1)/(2n-1)) * ... * (1/(n+1)) = 1/binomial(2n,n) ~ sqrt(Pi*n)/4^n, so we might expect to find such a q less than 4^n (page 500). All the known values of a(n) are (much) less than 4^n.

			For n = 2, we have four people; with q = 7 we count 1,2,3,4,1,2,3 and person 3 is eliminated. Next we count 4,1,2,4,1,2,4, so person 4 is eliminated, leaving only 1 and 2. Attempting this with any q < 7 does not eliminate 3 and 4 first.

R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994, p. 20.
W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, Dover, 1987, pp. 32-36.

Bert Dobbelaere, Table of n, a(n) for n = 1..40
P. Schumer, The Josephus Problem: Once More Around, Mathematics Magazine, Vol. 75:1 (2002), 12-17.
Index entries for sequences related to the Josephus Problem
Bert Dobbelaere, Python program

Cf. A198791, least q eliminating the odd-numbered people.
Cf. A006257, last survivor with q = 2.
Cf. A054995, last survivor with q = 3.
Cf. A321781, least q leaving position j as last survivor.
Cf. A321793, maximum q needed to ensure survival of one of n people.

def A343780(n):
    q = 1
    while True:
        s, c = [1]*n+[0]*n, 0
        for i in range(n):
            c = (c+q)%(2*n-i)
            if s[c]: break
            s = s[:c]+s[c+1:]
        else:
            return q+1
        q += 1 # Chai Wah Wu, Apr 30 2021

a(17)-a(21) from Chai Wah Wu, Apr 30 2021
a(22) from Nicholas Matteo, Apr 30 2021
a(23)-a(25) from Jon E. Schoenfield, Apr 30 2021
a(26)-a(27) from Bert Dobbelaere, May 01 2021

A348533 Generalized Josephus problem: Let T(m,k), k>=2, m=1,2,3,.., be the number of people on a circle such that the survivor is one of the first k-1 people after every k-th person has been removed.

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 8, 3, 2, 1, 16, 4, 3, 2, 1, 32, 6, 4, 3, 2, 1, 64, 9, 5, 4, 3, 2, 1, 128, 14, 7, 5, 4, 3, 2, 1, 256, 21, 9, 6, 5, 4, 3, 2, 1, 512, 31, 12, 8, 6, 5, 4, 3, 2, 1, 1024, 47, 16, 10, 7, 6, 5, 4, 3, 2, 1, 2048, 70, 22, 12, 8, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Gerhard Kirchner, Oct 21 2021

The table, see example, is read by ascending antidiagonals.

Trivial cases: T(m,k)=m for m

The recurrence in the formula section does not only yield T(m,k), but also the survivor's number S(m,k) so that the Josephus problem can be solved for any number N of people, especially for large N because T(m,k) grows exponentially, see link "Derivation of the recurrence", section II.

T(m,k) compared with other sequences ("->" means that the sequences can be made equal by removing repeated terms, see link "Derivation of the recurrence", section IV).

T(m,2) = A000079(m)=2^(m-1)

T(m,3) -> A073941

T(m,4) -> A072493

T(m+4,4)= A005427(m)

T(m,5) -> A120160

T(m,6) -> A120170

T(m,7) -> A120178

T(m,8) -> A120186

T(m,9) -> A120194

T(m,10)-> A120202

			k=4: 7 people, survivors number 2 <4.
k=4: 6 people, survivors number 5>=4, counterexample.
Table T(m,k) begins:
  m\k____2____3____4____5
   1:    1    1    1    1
   2:    2    2    2    2
   3:    4    3    3    3
   4:    8    4    4    4
   5:   16    6    5    5
   6:   32    9    7    6
   7:   64   14    9    8
   8:  128   21   12   10
   9:  256   31   16   12
  10:  512   47   22   15

Gerhard Kirchner, Derivation of the recurrence
Gerhard Kirchner, Table for 2<=k<=10 and 1<=m<=30
Index entries for sequences related to the Josephus Problem

Cf. A005428, A032434, A054995, A007495.

block(k:10, mmax:30, t:1, s:1, T:[1],
/*Terms T(m,k), m=1 thru mmax */
for m from 1 thru mmax-1 do(
    p:  mod(t, k-1),
    if s>p then e:-p else e:k-1-p,
    t: (k*t+e)/(k-1), s: 1+mod(s+e-1, t),
    T:append(T,[t])),
return (T));

Recurrence for T(m,k) and S(m,k), the survivor's number.
Start: T(1,k)=S(1,k)=1.
T(m+1,k)=(k*T(m,k)+e)/(k-1),
S(m+1,k)=1 + (S(m,k)+e-1) mod T(m+1,k),
with e=-p if S(m,k)>p and e=k-1-p otherwise, p = T(m,k) mod (k-1).

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.

Previous Showing 11-20 of 23 results. Next

cp's OEIS Frontend

A081615 Subsequence of A005428 where state = 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

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

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

A380195 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-down dealing is used, then the resulting cards will be dealt in increasing order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Python

Formula

A381591 Elimination order of the first person in a variation of the Josephus problem, where there are n people total and two people are skipped each time.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Python

A381667 Triangle read by row: T(n,k) is the number of the k-th eliminated person in the variation of the Josephus elimination process for n people where two people are skipped each step.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Python

A083287 Continued fraction expansion of K(3), a constant related to the Josephus problem.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A343780 If n good guys followed by n bad guys stand in a circle, a(n) is the least q such that executing every q-th person gets all bad guys first.

Views

Author

Keywords

Comments

Examples

References