A054995 -id:A054995 - cp's OEIS frontend

A165735 Surviving integers under the double-count Josephus problem (see A054995), modulo 3.

1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Ryohei Miyadera and Masakazu Naito, Sep 25 2009

nonn

Old name was: The pattern is obvious. The sequence can be divided into subsequences of {1,1,1,...} and {2,2,2,...}.

Let n be a natural number. We put n numbers in a circle, and we are going to remove every third number. Let J3(n) be the last number that remains. This is the traditional Josephus Problem. Let J3 (mod 3) be the residue of the sequence J3(n) under mod 3. J3 (mod 3) produces the sequence {1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2,...}.

			If we use n = 10, then we put numbers 1,2,3,4,5,6,7,8,9,10 in a circle. We eliminate 3,6,9,2,7,1,8,5,10, and the last number that remains is 4. Therefore J3(10) = 4 and J3(10) = 1 mod 3.

Hiroshi Matsui, Masakazu Naito and Naoyuki Totani, The Period and the Distribution of the Fibonacci-like Sequence Under Various Moduli, Undergraduate Math Journal, Rose-Hulman Institute of Technology, Vol. 10, Issue 1, 2009.
Masakazu Naito and Ryohei Miyadera, The Self-Similarity of the Josephus Problem and its Variants, Visual Mathematics, Volume 11, No.2, 2009.
Wolfram MathWorld, Josephus Problem
Index entries for sequences related to the Josephus Problem

Cf. A010872, A054995, A114144, A113648, A165556.

J3[1] = 1; J3[2] = 2; J3[n_] := J3[n] = Block[{m, t}, t = Mod[n, 3]; m = (n - t)/3; Which[t == 0, J3[2 m] + Floor[(J3[2 m] - 1)/2], t == 1, If[J3[2 m + 1] == 1, 3 m + 1, J3[2 m + 1] + Floor[J3[2 m + 1]/2] - 2], t == 2, J3[2 m + 1] + Floor[J3[2 m + 1]/2] + 1]]; Table[Mod[J3[n], 3], {n, 1, 200}]

(1) J3(1) = 1 and J3(2) = 2.
(2) J3(3m) = J3(2m) + [(J3(2m)-1)/2].
(3a) J3(3m+1) = 3m + 1 (if J3(2m + 1) = 1).
(3b) J3(3m+1) = J3(2m+1) + [J3(2m+1)/2] - 2 (if J3(2m + 1) > 1).
(4) J3(3m+2) = J3(2m+1) + [J3(2m+1)/2] + 1
a(n) = A010872(A054995(n)). - Gordon Atkinson, Aug 21 2019

New name from Gordon Atkinson, Aug 21 2019

A006257 Josephus problem: a(2n) = 2a(n)-1, a(2n+1) = 2a(n)+1.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

Offset: 0

N. J. A. Sloane

Write the numbers 1 through n in a circle, start at 1 and cross off every other number until only one number is left.
A version of the children's game "One potato, two potato, ...".
a(n)/A062383(n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumerates all binary fractions in the unit interval [0, 1). - Fredrik Johansson, Aug 14 2006
Iterating a(n), a(a(n)), ... eventually leads to 2^A000120(n) - 1. - Franklin T. Adams-Watters, Apr 09 2010
By inspection, the solution to the Josephus Problem is a sequence of odd numbers (from 1) starting at each power of 2.  This yields a direct closed form expression (see formula below). - Gregory Pat Scandalis, Oct 15 2013
Also zero together with a triangle read by rows in which row n lists the first 2^(n-1) odd numbers (see A005408), n >= 1. Row lengths give A011782. Right border gives A000225. Row sums give A000302, n >= 1. See example. - Omar E. Pol, Oct 16 2013
For n > 0: a(n) = n + 1 - A080079(n). - Reinhard Zumkeller, Apr 14 2014
In binary, a(n) = ROL(n), where ROL = rotate left = remove the leftmost digit and append it to the right. For example, n = 41 = 101001_2 => a(n) = (0)10011_2 = 19. This also explains FTAW's comment above. - M. F. Hasler, Nov 02 2016
In the under-down Australian card deck separation: top card on bottom of a deck of n cards, next card separated on the table, etc., until one card is left. The position a(n), for n >= 1, from top will be the left over card. See, e.g., the Behrends reference, pp. 156-164. For the down-under case see 2*A053645(n), for n >= 3, n not a power of 2. If n >= 2 is a power of 2 the botton card survives. - Wolfdieter Lang, Jul 28 2020

			From _Omar E. Pol_, Jun 09 2009: (Start)
Written as an irregular triangle the sequence begins:
  0;
  1;
  1,3;
  1,3,5,7;
  1,3,5,7,9,11,13,15;
  1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31;
  1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,
   43,45,47,49,51,53,55,57,59,61,63;
...
(End)
From _Omar E. Pol_, Nov 03 2018: (Start)
An illustration of initial terms, where a(n) is the area (or number of cells) in the n-th region of the structure:
   n   a(n)       Diagram
   0    0     _
   1    1    |_|_ _
   2    1      |_| |
   3    3      |_ _|_ _ _ _
   4    1          |_| | | |
   5    3          |_ _| | |
   6    5          |_ _ _| |
   7    7          |_ _ _ _|
(End)

Erhard Behrends, Der mathematische Zauberstab, Rowolth Taschenbuch Verlag, rororo 62902, 4. Auflage, 2019, pp. 156-164. [English version: The Math Behind the Magic, AMS, 2019.]
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 10.
M. S. Petković, "Josephus problem", Famous Puzzles of Great Mathematicians, page 179, Amer. Math. Soc. (AMS), 2009.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Paul Weisenhorn, Josephus und seine Folgen, MNU, 59(2006), pp. 18-19.

Iain Fox, Table of n, a(n) for n = 0..100000 (terms 0..1000 from T. D. Noe, terms 1001..10000 from Indranil Ghosh).
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 34.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Daniel Erman and Brady Haran, The Josephus Problem, Numberphile video (2016)
Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.
Alasdair MacFhraing, Aireamh Muinntir Fhinn Is Dhubhain, Agus Sgeul Josephuis Is An Da Fhichead Iudhaich, [Gaelic with English summary], Proc. Royal Irish Acad., Vol. LII, Sect. A., No. 7, 1948, 87-93.
Yuri Nikolayevsky and Ioannis Tsartsaflis, Cohomology of N-graded Lie algebras of maximal class over Z_2, arXiv:1512.87676 [math.RA], (2016), pages 2, 6.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Josephus Problem
Wikipedia, Josephus problem
Index entries for sequences related to the Josephus Problem

Cf. A005428, A035327, A038572, A049940, A049964, A053644, A053645, A088147, A088442.
Second column, and main diagonal, of triangle A032434.
Cf. A181281 (with s=5), A054995 (with s=3).
Column k=2 of A360099.

Require Import ZArith.
Fixpoint a (n : positive) : Z :=
match n with
| xH => 1
| xI n' => (2*(a n') + 1)%Z
| xO n' => (2*(a n') - 1)%Z
end.
(* Stefan Haan, Aug 27 2023 *)

a006257 n = a006257_list !! n
a006257_list =
   0 : 1 : (map (+ 1) $ zipWith mod (map (+ 1) $ tail a006257_list) [2..])
-- Reinhard Zumkeller, Oct 06 2011

[0] cat [2*(n-2^Floor(Log(2,n)))+1: n in [1..100]]; // Vincenzo Librandi, Jan 14 2016

a(0):=0: for n from 1 to 100 do a(n):=(a(n-1)+1) mod n +1: end do:
seq(a(i),i=0..100); # Paul Weisenhorn, Oct 10 2010; corrected by Robert Israel, Jan 13 2016
A006257 := proc(n)
    convert(n,base,2) ;
    ListTools[Rotate](%,-1) ;
    add( op(i,%)*2^(i-1),i=1..nops(%)) ;
end proc: # R. J. Mathar, May 20 2016
A006257 := n -> 2*n  - Bits:-Iff(n, n):
seq(A006257(n), n=0..78); # Peter Luschny, Sep 24 2019

Table[ FromDigits[ RotateLeft[ IntegerDigits[n, 2]], 2], {n, 0, 80}] (* Robert G. Wilson v, Sep 21 2003 *)
Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (* Birkas Gyorgy, Feb 07 2011 *)
m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (* Birkas Gyorgy, Feb 07 2011 *)

a(n)=sum(k=1,n,if(bitxor(n,k)Paul D. Hanna

a(n)=if(n, 2*n-2^logint(2*n,2)+1, 0) \\ Charles R Greathouse IV, Oct 29 2016

import math
def A006257(n):
     return 0 if n==0 else 2*(n-2**int(math.log(n,2)))+1 # Indranil Ghosh, Jan 11 2017

def A006257(n): return bool(n&(m:=1<Chai Wah Wu, Jan 22 2023
(C#)
static long cs_A006257(this long n) => n == 0 ? 0 : 1 + (1 + (n - 1).cs_A006257()) % n; // Frank Hollstein, Feb 24 2021

To get a(n), write n in binary, rotate left 1 place.
a(n) = 2*A053645(n) + 1 = 2(n-msb(n))+1. - Marc LeBrun, Jul 11 2001. [Here "msb" = "most significant bit", A053644.]
G.f.: 1 + 2/(1-x) * ((3*x-1)/(2-2*x) - Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = number of positive integers k < n such that n XOR k < n. a(n) = n - A035327(n). - Paul D. Hanna, Jan 21 2006
a(n) = n for n = 2^k - 1. - Zak Seidov, Dec 14 2006
a(n) = n - A035327(n). - K. Spage, Oct 22 2009
a(2^m+k) = 1+2*k; with 0 <= m and 0 <= k < 2^m; n = 2^m+k; m = floor(log_2(n)); k = n-2^m; a(n) = ((a(n-1)+1) mod n) + 1; a(1) = 1. E.g., n=27; m=4; k=11; a(27) = 1 + 2*11 = 23. - Paul Weisenhorn, Oct 10 2010
a(n) = 2*(n - 2^floor(log_2(n))) + 1 (see comment above). - Gregory Pat Scandalis, Oct 15 2013
a(n) = 0 if n = 0 and a(n) = 2*a(floor(n/2)) - (-1)^(n mod 2) if n > 0. - Marek A. Suchenek, Mar 31 2016
G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 + x). - Ilya Gutkovskiy, Aug 31 2019
For n > 0: a(n) = 2 * A062050(n) - 1. - Frank Hollstein, Oct 25 2021

More terms from Robert G. Wilson v, Sep 21 2003

A321298 Triangle read by rows: T(n,k) is the number of the k-th eliminated person in the Josephus elimination process for n people and a count of 2, 1 <= k <= n.

Original entry on oeis.org

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

Offset: 1

Zeph L. Turner, Nov 02 2018

In the Josephus elimination process for n and k, the numbers 1 through n are written in a circle. A pointer starts at position 1. Each turn, the pointer skips (k-1) non-eliminated number(s) going around the circle and eliminates the k-th number, until no numbers remain. This sequence represents the triangle J(n, i), where n is the number of people in the circle, i is the turn number, and k is fixed at 2 (every other number is eliminated).

			Triangle begins:
  1;
  2, 1;
  2, 1, 3;
  2, 4, 3, 1;
  2, 4, 1, 5,  3;
  2, 4, 6, 3,  1,  5;
  2, 4, 6, 1,  5,  3, 7;
  2, 4, 6, 8,  3,  7, 5, 1;
  2, 4, 6, 8,  1,  5, 9, 7,  3;
  2, 4, 6, 8, 10,  3, 7, 1,  9,  5;
  2, 4, 6, 8, 10,  1, 5, 9,  3, 11, 7;
  2, 4, 6, 8, 10, 12, 3, 7, 11,  5, 1, 9;
  2, 4, 6, 8, 10, 12, 1, 5,  9, 13, 7, 3, 11;
  ...
For n = 5, to get the entries in 5th row from left to right, start with (^1, 2, 3, 4, 5) and the pointer at position 1, indicated by the caret. 1 is skipped and 2 is eliminated to get (1, ^3, 4, 5). (The pointer moves ahead to the next "live" number.) On the next turn, 3 is skipped and 4 is eliminated to get (1, 3, ^5). Then 1, 5, and 3 are eliminated in that order (going through (^3, 5) and (^3)). This gives row 5 of the triangle and entries a(11) through a(15) in this sequence.

Index entries for sequences related to the Josephus Problem

The right border of this triangle is A006257.

Cf. A032434, A054995, A181281, A225381, A378635 (row permutation inverses).

Table[Rest@ Nest[Append[#1, {Delete[#2, #3 + 1], #2[[#3 + 1]], #3}] & @@ {#, #[[-1, 1]], Mod[#[[-1, -1]] + 1, Length@ #[[-1, 1]]]} &, {{Range@ n, 0, 0}}, n][[All, 2]], {n, 14}] // Flatten (* Michael De Vlieger, Nov 13 2018 *)

def A321298(n,k):
    if 2*k<=n: return 2*k
    n2,r=divmod(n,2)
    if r==0: return 2*A321298(n2,k-n2)-1
    if k==n2+1: return 1
    return 2*A321298(n2,k-n2-1)+1 # Pontus von Brömssen, Sep 18 2022

From Pontus von Brömssen, Sep 18 2022: (Start)
The terms are uniquely determined by the following recursive formulas:
  T(n,k) = 2*k if k <= n/2;
  T(2*n,k) = 2*T(n,k-n)-1 if k > n;
  T(2*n+1,k) = 2*T(n,k-n-1)+1 if k > n+1;
  T(2*n+1,n+1) = 1.
(End)
From Pontus von Brömssen, Dec 11 2024: (Start)
The terms are also uniquely determined by the following recursive formulas:
  T(1,1) = 1;
  T(n,1) = 2 if n > 1;
  T(n,k) = T(n-1,k-1)+2 if k > 1 and T(n-1,k-1) != n-1;
  T(n,k) = 1 if k > 1 and T(n-1,k-1) = n-1.
T(n,A225381(n)) = 1.
T(n,A225381(n+1)-1) = n.
(End)

Name clarified by Pontus von Brömssen, Sep 18 2022

A032434 Triangle read by rows: last survivors of Josephus elimination process.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

T(n,k) 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 k - 1 places clockwise from i. Repeat, counting k - 1 places from the next undeleted integer, until only one integer remains. [After John W. Layman]
From Gerhard Kirchner, Jan 08 2017: (Start)
The fast recurrence is useful for large n, if single values of T(n,k) are to be determined (not the whole sequence). The number of steps is about log(n)/log(n/(k/(k-1))) instead of n, i.e., many basic steps are bypassed by a shortcut.
Example: For computing T(10^80, 7), about 1200 steps are needed, done in a second, whereas even the age of the universe would not be sufficient for the basic recurrence. Deduction of the fast recurrence and the reason for its efficiency: See the link "Fast recurrence". (End)

			Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins
  1;
  2, 1;
  3, 3, 2;
  4, 1, 1, 2;
  5, 3, 4, 1, 2;
  6, 5, 1, 5, 1, 4;
  7, 7, 4, 2, 6, 3, 5;
  ...
Fast recurrence for n = 7 and k = 3:
m =    1 2 3 4 5 6,
z(m) = 1 2 3 4 6 9,
r(m) = 1 2 2 1 1,
z(6) > n => M = 5.
Result: T(7,3) = r(5) + 3*(n - z(5)) = 4.

W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987, see pp. 32-36.
M. Kraitchik, "Josephus' Problem." Sec. 3.13 in Mathematical Recreations. New York: W. W. Norton, pp. 93-94, 1942.

T. D. Noe, Rows n = 1..50, flattened
Philippe Dumas, Algebraic aspects of B-regular series, inria-00074743, 1993.
Philippe Dumas, Algebraic aspects of B-regular series, in: A. Lingas, R. Karlsson, S. Carlsson S. (eds), Automata, Languages and Programming, ICALP 1993 (Lecture Notes in Computer Science, vol 700, Springer, Berlin, Heidelberg), pp. 457-468, 1993.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, preprint, 1997.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, preprint, 1997.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, Journal de Théorie des Nombres de Bordeaux 9 (1997), 303-318.
Gerhard Kirchner, Fast recurrence.
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, preprint, 1991. [Cached copy, with permission]
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33 (1991), 235-240.
Eric Weisstein's World of Mathematics, Josephus Problem.
Wikipedia, Josephus problem.
Index entries for sequences related to the Josephus problem

Cf. A032435, A032436, A321781.

Second column is A006257, third column is A054995. Diagonal T(n, n) is A007495.

t[1, k_] = 1; t[n_, k_] := t[n, k] = If[m = Mod[t[n-1, k] + k, n]; m != 0, m, n]; Flatten[ Table[ t[n, k], {n, 1, 14}, {k, 1, n}]] (* Jean-François Alcover, Sep 25 2012 *)

T(n,k)=local(t): if(n<2,n>0,t=(T(n-1,k)+k)%n: if(t,t,n))

Recurrence: T(1, k) = 1, T(n, k) = (T(n-1, k) + k) mod n if this is nonzero and n if not.
From Gerhard Kirchner, Jan 08 2017: (Start)
The same recurrence without these conditions:
T(1, k) = 1,  T(n, k) = 1 + (T(n-1, k) + k - 1) mod n.
This "basic" recurrence is used in the following:
Fast recurrence (n >= k):
z(1) = 1, r(1) = 1,
if z(m) < k-1 then
  z(m+1) = z(m) + 1,
  r(m+1) = 1 + (r(m)+k-1) mod z(m+1) (basic recurrence),
else
  e(m) = -z(m) mod (k-1),
  if r(m) + e(m) <= 0 then e(m) -> e(m) + k - 1,
  z(m+1) = z(m) + (z(m) + e(m))/(k-1),
  r(m+1) = r(m) + e(m).
Result for m = M with z(M) <= n < z(M+1):
T(n,k) = r(M) + k(n - z(M)). (End)
From Gerhard Kirchner, Jan 12 2017: (Start)
Another fast (and shorter) recurrence is given in "Functional iteration and the Josephus problem", p. 1, (see link):
D(m,k) = ceiling(k/(k-1)*D(m-1,k)), m >= 1; D(0,k)=1.
Result for m with D(m-1,k) <= (k-1)*n < D(m,k):
T(n,k) = k*n + 1 - D(m,k). (End)

Edited by Ralf Stephan, May 18 2004

A083286 Decimal expansion of K(3), a constant related to the Josephus problem.

Original entry on oeis.org

1, 6, 2, 2, 2, 7, 0, 5, 0, 2, 8, 8, 4, 7, 6, 7, 3, 1, 5, 9, 5, 6, 9, 5, 0, 9, 8, 2, 8, 9, 9, 3, 2, 4, 1, 1, 3, 0, 6, 6, 1, 0, 5, 5, 6, 2, 3, 1, 3, 0, 3, 7, 4, 3, 2, 1, 8, 5, 4, 4, 3, 3, 8, 7, 3, 7, 8, 4, 3, 3, 9, 9, 9, 7, 2, 7, 4, 8, 4, 4, 7, 6, 3, 8, 3, 6, 1, 6, 5, 3, 9, 8, 3, 3, 2, 3, 3, 4, 1, 1, 0, 0

Offset: 1

Ralf Stephan, Apr 23 2003

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

The number also occurs in Washburn's solution cited in References. Regarding Washburn's limit more generally (with x in place of 3/2) results in a disconnected function as plotted by the Mathematica program below. - Clark Kimberling, Oct 24 2012

			1.62227050288476731595695...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Sections 2.13 and 2.30.1, pp. 131, 196.

A.H.M. Smeets, Table of n, a(n) for n = 1..20000
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33 (1991), 235-240.
A.H.M. Smeets, 100000 decimal digits.
E. T. H. Wang, Phillip C. Washburn, Problem E2604, American Mathematical Monthly, 84 (1977), 821-822.
Eric Weisstein's World of Mathematics, Power Ceilings.
Index entries for sequences related to the Josephus Problem.

Cf. A054995, A083287.

s[x_, 0] := 0; s[x_, n_] := Floor[x*s[x, n - 1]] + 1
c[x_, n_] := ((1/x)^n) s[x, n]
t = N[c[3/2, 800], 120]
RealDigits[t, 10]  (* A083286 *)
(* Display of the surroundings of 3/2 *)
Plot[N[c[x, 20]], {x, 1, 3}]
(* Clark Kimberling, Oct 24 2012 *)

p=1; N=10^4; for(n=1, N, p=ceil(3/2*p)); c=(p/(3/2)^N)+0.

d, a, n, nmax = 3, 0, 0, 150000
while n < nmax:
    n, a = n+1, (a*d)//(d-1)+1
nom, den, pos = a*(d-1)**n, d**n, 0
while pos < 20000:
    dig, nom, pos = nom//den, (nom%den)*10, pos+1
    print(pos,dig) # A.H.M. Smeets, Jul 05 2019

A007495 Josephus problem: survivors.

Original entry on oeis.org

1, 1, 2, 2, 2, 4, 5, 4, 8, 8, 7, 11, 8, 13, 4, 11, 12, 8, 12, 2, 13, 7, 22, 2, 8, 13, 26, 4, 26, 29, 17, 27, 26, 7, 33, 20, 16, 22, 29, 4, 13, 22, 25, 14, 22, 37, 18, 46, 42, 46, 9, 41, 12, 7, 26, 42, 24, 5, 44, 53, 52, 58, 29, 22, 12, 48, 27, 30, 58, 52, 49, 57, 13, 14, 32, 24, 75, 8, 67

Offset: 1

N. J. A. Sloane, Robert G. Wilson v

If, in a circle of k persons, every n-th person is removed, the survivor is t(k,n) + 1. So the recurrence generates a sequence of survivors. See the formula. For more details see the "Proof of the formula". - Gerhard Kirchner, Oct 23 2016

The recurrence formula looks like a simple congruential generator for pseudo-random numbers. Is a(n) pseudo-random? It seems so, see: "Stochastic aspects". I used the formula for extending a(n) up to n=2^20. - Gerhard Kirchner, Nov 10 2016

			From _Gerhard Kirchner_, Oct 23 2016: (Start)
If n = 4 we have that:
  t(1,4) = 0.
  t(2,4) = (0+4) mod 2 = 0.
  t(3,4) = (0+4) mod 3 = 1.
  t(4,4) = (1+4) mod 4 = 1.
So a(4) = 1 + 1 = 2. (End)

Friend H. Kierstead, Jr., Computer Challenge Corner, J. Rec. Math., 10 (1977), see p. 124.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 1..5000 (first 1000 terms from T. D. Noe)
Gerhard Kirchner, Proof of the formula.
Gerhard Kirchner, Stochastic aspects.
Eric Weisstein's World of Mathematics, Josephus Problem.
Robert G. Wilson v, Notes, n.d..
Index entries for sequences related to the Josephus Problem

Cf. A032434, A054995.

(* First do *) Needs["Combinatorica`"] (* then *) f[n_] := Last@ InversePermutation@ Josephus[n, n]; Array[f, 80] (* Robert G. Wilson v, Jul 31 2010 *)
t[k_, n_] := t[k, n] = Mod[t[k-1, n]+n, k]; t[1, ] = 0; a[n] := t[n, n]+1; Array[a, 1000] (* Jean-François Alcover, Oct 23 2016, after Gerhard Kirchner *)

Let t(k,n) = (t(k-1,n) + n) mod k and t(1,n) = 0; then a(n) = t(n,n) + 1. - Gerhard Kirchner, Oct 23 2016

More terms from Robert G. Wilson v, Jul 31 2010

A088333 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 3 places clockwise from i. Repeat, counting 3 places from the next undeleted integer, until only one integer remains.

Original entry on oeis.org

1, 1, 2, 2, 1, 5, 2, 6, 1, 5, 9, 1, 5, 9, 13, 1, 5, 9, 13, 17, 21, 3, 7, 11, 15, 19, 23, 27, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42

Offset: 1

N. J. A. Sloane, Nov 13 2003

If one counts only one place (resp. two places) at each stage to determine the element to be deleted, we get A006257 (resp. A054995).

See A054995 for references and links.

Index entries for sequences related to the Josephus Problem

Cf. A006257, A054995, A032434, A005427, A005428, A006257, A007495, A000960, A056530.

It is tempting (in view of A054995) to conjecture that a(1)=1 and, for n>1, a(n) = (a(n-1)+4) mod n. The conjecture is false; counterexample: a(21)=21; a(20)=17; (a(20)+4)mod 21=0; corrected formula: a(n)=(a(n-1)+3) mod n +1;
The conjecture is true. After removing the 4th number, we are reduced to the n-1 case, but starting with 5 instead of 1. - David Wasserman, Aug 08 2005
a(n) = A032434(n,4) if n>=4. - R. J. Mathar, May 04 2007

More terms from David Wasserman, Aug 08 2005

A081614 Subsequence of A005428 with state = 1.

Original entry on oeis.org

1, 4, 6, 9, 31, 70, 105, 355, 799, 1798, 2697, 9103, 20482, 30723, 69127, 155536, 233304, 349956, 524934, 787401, 2657479, 5979328, 8968992, 13453488, 20180232, 30270348, 45405522, 68108283, 153243637, 1745540806, 2618311209, 8836800331, 19882800745, 67104452515, 150985018159, 339716290858, 509574436287, 1146542481646, 1719813722469, 13059835455001, 44076944660629, 753095921662471, 1694465823740560

Offset: 0

N. J. A. Sloane, Apr 23 2003

Values of n such that A054995(n) = 1. - Ryan Brooks, Jul 17 2020
From Petros Hadjicostas, Jul 20 2020: (Start)
From a(1) = 4 to a(28) = 153243637, the values appear in Table 18 (p. 374) in Schuh (1968) under the Survivor No. 1 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(29) here is 1745540806 but 1595540806 in Schuh (1968). Burde (1987) agrees with Schuh (1968). See the table on p. 207 of the paper (with q = 0). Actually, 1595540806 is the last number on the table with q = 0.
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..2816
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, A081615, A061419.

/* 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 1. See A073941 or Schuh (1968) for more details. */
first(n) = {my(res = vector(n), t = 1, wn = wo = 4, go = gn = 1); res[1] = 1; for(i = 1, oo, c = wo % 2; if(go == 1, 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 20 2020

a(n) = [(n+1)-th even number of A061419]/2. - John-Vincent Saddic, May 29 2021

More terms from Hans Havermann, Apr 23 2003

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.

Original entry on oeis.org

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.

cp's OEIS Frontend

A165735 Surviving integers under the double-count Josephus problem (see A054995), modulo 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A006257 Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Coq

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A321298 Triangle read by rows: T(n,k) is the number of the k-th eliminated person in the Josephus elimination process for n people and a count of 2, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A032434 Triangle read by rows: last survivors of Josephus elimination process.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A083286 Decimal expansion of K(3), a constant related to the Josephus problem.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

A007495 Josephus problem: survivors.

Views

Author

Keywords

Comments

Examples

A006257 Josephus problem: a(2n) = 2a(n)-1, a(2n+1) = 2a(n)+1.