login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006257 Josephus problem: a(2n) = 2*a(n)-1, a(2n+1) = 2*a(n)+1.
(Formerly M2216)
34
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

REFERENCES

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

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

C. Groer, The mathematics of survival ..., Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.

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)18-19 [From Paul Weisenhorn, Oct 10 2010]

LINKS

T. D. Noe, Table of n, a(n) for n=0..1000

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

R. Stephan, Some divide-and-conquer sequences ...

R. 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.: 2/(1-x) * ((3x-1)/(2-2x) - 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 (kevspage2001(AT)yahoo.co.uk), Oct 22 2009]

a(2^m+k)=1+2*k; with 0<=m and 0<=k<2^m; n=2^m+k; m=floor(lb(n)); k=n-2^m; a(n)=(a(n-1)+1)mod n +1; a(1)=1. - Paul Weisenhorn, Oct 10 2010

a(n) = 2*(n - 2^floor(log2(n))) + 1 (see comment above). - Gregory Pat Scandalis, Oct 15 2013

EXAMPLE

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;

  [Omar E. Pol, Jun 09 2009]

n=27; m=4; k=11; a(27)=1+2*11=23. - Paul Weisenhorn, Oct 10 2010

MAPLE

a(1)=1: for n:=2 to 100 do a(n):=(a(n-1)+1) mod n +1: end do: # Paul Weisenhorn, Oct 10 2010

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 8)

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, 1, 0)) (Hanna)

(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

CROSSREFS

Cf. A005428, A054995, A038572, A053644, A053645, A088147, A088442, A035327.

Second column of triangle A032434. Diagonal of triangle A032434.

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

Sequence in context: A182600 A179760 A160552 * A170898 A189442 A234587

Adjacent sequences:  A006254 A006255 A006256 * A006258 A006259 A006260

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 23 03:59 EDT 2014. Contains 244850 sequences.