The OEIS is supported by the many generous donors to the OEIS Foundation. 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) 95
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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 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 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 => a(n) = (0)10011 = 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 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). P. 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 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(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 EXAMPLE 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) 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 *) Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (* Birkas Gyorgy *) m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (* Birkas Gyorgy *) PROG (PARI) a(n)=sum(k=1, n, if(bitxor(n, k) n == 0 ? 0 : 1 + (1 + (n - 1).cs_A006257()) % n; // Frank Hollstein, Feb 24 2021 CROSSREFS 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). Sequence in context: A334852 A160552 A256263 * A323555 A323553 A170898 Adjacent sequences:  A006254 A006255 A006256 * A006258 A006259 A006260 KEYWORD nonn,easy,nice AUTHOR EXTENSIONS More terms from Robert G. Wilson v, Sep 21 2003 STATUS approved

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

Last modified October 2 06:08 EDT 2022. Contains 357191 sequences. (Running on oeis4.)