login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006257 Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.
(Formerly M2216)
91

%I M2216

%S 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,

%T 27,29,31,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,

%U 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

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

%C Write the numbers 1 through n in a circle, start at 1 and cross off every other number until only one number is left.

%C A version of the children's game "One potato, two potato, ...".

%C 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

%C In base 2 n-a(n) is equal to n with all digits reverted (leading zeros not considered). For instance a(43)=23 -> 43 is 101011, 43-23 = 20 is 10100. - _Paolo P. Lava_, Mar 09 2010

%C Iterating a(n), a(a(n)), ... eventually leads to 2^A000120(n) - 1. - _Franklin T. Adams-Watters_, Apr 09 2010

%C 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

%C 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

%C For n > 0: a(n) = n + 1 - A080079(n). - _Reinhard Zumkeller_, Apr 14 2014

%C 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

%C 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

%D 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].

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 10.

%D M. S. Petković, "Josephus problem", Famous Puzzles of Great Mathematicians, page 179, Amer. Math. Soc.(AMS), 2009.

%D Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D P. Weisenhorn, Josephus und seine Folgen, MNU, 59(2006), pp. 18-19.

%H Iain Fox, <a href="/A006257/b006257.txt">Table of n, a(n) for n = 0..100000</a> (terms 0..1000 from T. D. Noe, terms 1001..10000 from Indranil Ghosh).

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197, ex. 34.

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.

%H Daniel Erman and Brady Haran, <a href="https://www.youtube.com/watch?v=uCsD3ZGzMgE">The Josephus Problem</a>, Numberphile video (2016)

%H Chris Groër, <a href="http://www.jstor.org/stable/3647800">The Mathematics of Survival: From Antiquity to the Playground</a>, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.

%H Alasdair MacFhraing, <a href="https://www.jstor.org/stable/20488493">Aireamh Muinntir Fhinn Is Dhubhain, Agus Sgeul Josephuis Is An Da Fhichead Iudhaich</a>, [Gaelic with English summary], Proc. Royal Irish Acad., Vol. LII, Sect. A., No. 7, 1948, 87-93.

%H Yuri Nikolayevsky and Ioannis Tsartsaflis, <a href="http://arxiv.org/abs/1512.07676">Cohomology of N-graded Lie algebras of maximal class over Z_2</a>, arXiv:1512.87676 [math.RA], (2016), pages 2, 6.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/JosephusProblem.html">Josephus Problem</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Josephus_problem">Josephus problem</a>

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%F To get a(n), write n in binary, rotate left 1 place.

%F a(n) = 2*A053645(n) + 1 = 2(n-msb(n))+1. - _Marc LeBrun_, Jul 11 2001. Here "msb" = "most significant bit", A053644.

%F 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

%F 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

%F a(n) = n for n = 2^k - 1. - _Zak Seidov_, Dec 14 2006

%F a(n) = n - A035327(n). - _K. Spage_, Oct 22 2009

%F 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

%F a(n) = 2*(n - 2^floor(log_2(n))) + 1 (see comment above). - _Gregory Pat Scandalis_, Oct 15 2013

%F 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

%F G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 + x). - _Ilya Gutkovskiy_, Aug 31 2019

%e From _Omar E. Pol_, Jun 09 2009: (Start)

%e Written as an irregular triangle the sequence begins:

%e 0;

%e 1;

%e 1,3;

%e 1,3,5,7;

%e 1,3,5,7,9,11,13,15;

%e 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31;

%e 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,

%e 43,45,47,49,51,53,55,57,59,61,63;

%e ...

%e (End)

%e From _Omar E. Pol_, Nov 03 2018: (Start)

%e An illustration of initial terms, where a(n) is the area (or number of cells) in the n-th region of the structure:

%e n a(n) Diagram

%e 0 0 _

%e 1 1 |_|_ _

%e 2 1 |_| |

%e 3 3 |_ _|_ _ _ _

%e 4 1 |_| | | |

%e 5 3 |_ _| | |

%e 6 5 |_ _ _| |

%e 7 7 |_ _ _ _|

%e (End)

%p a(0):=0: for n from 1 to 100 do a(n):=(a(n-1)+1) mod n +1: end do:

%p seq(a(i),i=0..100); # _Paul Weisenhorn_, Oct 10 2010; corrected by _Robert Israel_, Jan 13 2016

%p A006257 := proc(n)

%p convert(n,base,2) ;

%p ListTools[Rotate](%,-1) ;

%p add( op(i,%)*2^(i-1),i=1..nops(%)) ;

%p end proc: # _R. J. Mathar_, May 20 2016

%p A006257 := n -> 2*n - Bits:-Iff(n, n):

%p seq(A006257(n), n=0..78); # _Peter Luschny_, Sep 24 2019

%t Table[ FromDigits[ RotateLeft[ IntegerDigits[n, 2]], 2], {n, 0, 80}] (* _Robert G. Wilson v_ *)

%t Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (* _Birkas Gyorgy_ *)

%t m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (* _Birkas Gyorgy_ *)

%o (PARI) a(n)=sum(k=1,n,if(bitxor(n,k)<n,1,0)) \\ _Paul D. Hanna_

%o (PARI) a(n)=if(n, 2*n-2^logint(2*n,2)+1, 0) \\ _Charles R Greathouse IV_, Oct 29 2016

%o (Haskell)

%o a006257 n = a006257_list !! n

%o a006257_list =

%o 0 : 1 : (map (+ 1) $ zipWith mod (map (+ 1) $ tail a006257_list) [2..])

%o -- _Reinhard Zumkeller_, Oct 06 2011

%o (MAGMA) [0] cat [2*(n-2^Floor(Log(2,n)))+1: n in [1..100]]; // _Vincenzo Librandi_, Jan 14 2016

%o (Python)

%o import math

%o def A006257(n):

%o return 0 if n==0 else 2*(n-2**int(math.log(n,2)))+1 # _Indranil Ghosh_, Jan 11 2017

%o (C#)

%o static long cs_A006257(this long n) => n == 0 ? 0 : 1 + (1 + (n - 1).cs_A006257()) % n; // _Frank Hollstein_, Feb 24 2021

%Y Cf. A005428, A035327, A038572, A049940, A049964, A053644, A053645, A054995, A088147, A088442.

%Y Second column, and main diagonal, of triangle A032434.

%Y Cf. A181281 (with s=5), A054995 (with s=3).

%K nonn,easy,nice

%O 0,4

%A _N. J. A. Sloane_

%E More terms from _Robert G. Wilson v_, Sep 21 2003

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 13 01:36 EDT 2021. Contains 342934 sequences. (Running on oeis4.)