A006257 Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.
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
Examples
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)
References
- 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.
Links
- 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
Crossrefs
Programs
-
Coq
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 *)
-
Haskell
a006257 n = a006257_list !! n a006257_list = 0 : 1 : (map (+ 1) $ zipWith mod (map (+ 1) $ tail a006257_list) [2..]) -- Reinhard Zumkeller, Oct 06 2011
-
Magma
[0] cat [2*(n-2^Floor(Log(2,n)))+1: n in [1..100]]; // Vincenzo Librandi, Jan 14 2016
-
Maple
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
-
Mathematica
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 *) -
PARI
a(n)=sum(k=1,n,if(bitxor(n,k)
-
PARI
a(n)=if(n, 2*n-2^logint(2*n,2)+1, 0) \\ Charles R Greathouse IV, Oct 29 2016
-
Python
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
-
Python
def A006257(n): return bool(n&(m:=1<
Formula
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(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
Extensions
More terms from Robert G. Wilson v, Sep 21 2003
Comments