|
%I M2216 #225 Feb 07 2024 01:15:22
%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 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 Paul 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 Paul Barry, <a href="https://arxiv.org/abs/2107.00442">Conjectures and results on some generalized Rueppel sequences</a>, arXiv:2107.00442 [math.CO], 2021.
%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
%F For n > 0: a(n) = 2 * A062050(n) - 1. - _Frank Hollstein_, Oct 25 2021
%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_, Sep 21 2003 *)
%t Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (* _Birkas Gyorgy_, Feb 07 2011 *)
%t m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (* _Birkas Gyorgy_, Feb 07 2011 *)
%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 (Python)
%o def A006257(n): return bool(n&(m:=1<<n.bit_length()-1))+((n&m-1)<<1) if n else 0 # _Chai Wah Wu_, Jan 22 2023
%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
%o (Coq)
%o Require Import ZArith.
%o Fixpoint a (n : positive) : Z :=
%o match n with
%o | xH => 1
%o | xI n' => (2*(a n') + 1)%Z
%o | xO n' => (2*(a n') - 1)%Z
%o end.
%o (* _Stefan Haan_, Aug 27 2023 *)
%Y Cf. A005428, A035327, A038572, A049940, A049964, A053644, A053645, A088147, A088442.
%Y Second column, and main diagonal, of triangle A032434.
%Y Cf. A181281 (with s=5), A054995 (with s=3).
%Y Column k=2 of A360099.
%K nonn,easy,nice
%O 0,4
%A _N. J. A. Sloane_
%E More terms from _Robert G. Wilson v_, Sep 21 2003
|
