|
| |
|
|
A006257
|
|
Josephus problem: a(2n) = 2a(n)-1, a(2n+1) = 2a(n)+1.
(Formerly M2216)
|
|
32
| |
|
|
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; 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. [From Paolo P. Lava (paoloplava(AT)gmail.com), Mar 09 2010]
Iterating a(n), a(a(n)), ... eventually leads to 2^A000120(n) - 1. [From Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Apr 09 2010]
|
|
|
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 Weisenhorn Paul (weisenhorn-f.p(AT)online.de), 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.
G.f.: 2/(1-x) * ((3x-1)/(2-2x) - sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan (ralf(AT)ark.in-berlin.de), 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 (pauldhanna(AT)juno.com), Jan 21 2006
a(n)=n for n=2^k-1, Zak Seidov, Dec 14, 2006
a(n) = n - A035327(n) [From K Spage (kevspage2001(AT)yahoo.co.uk), Oct 22 2009]
Contribution from Weisenhorn Paul (weisenhorn-f.p(AT)online.de), Oct 10 2010: (Start)
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;
(End)
|
|
|
EXAMPLE
| Contribution from Omar E. Pol (info(AT)polprimos.com), Jun 09 2009: (Start)
We can write the initial term followed by a triangle:
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,...
(End)
Contribution from Weisenhorn Paul (weisenhorn-f.p(AT)online.de), Oct 10 2010: (Start)
n=27; m=4; k=11; a(27)=1+2*11=23;
(End)
|
|
|
MAPLE
| Contribution from Weisenhorn Paul (weisenhorn-f.p(AT)online.de), Oct 10 2010: (Start)
a(1)=1: for n:=2 to 100 do a(n):=(a(n-1)+1) mod n +1: end do:
(End)
|
|
|
MATHEMATICA
| Table[ FromDigits[ RotateLeft[ IntegerDigits[n, 2]], 2], {n, 0, 80}] (from Robert G. Wilson v)
Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (Gyorgy Birkas)
m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (Gyorgy Birkas)
|
|
|
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
| a(n) = 2 * A053645(n) + 1 = 2(n-msb(n))+1. - Marc LeBrun (mlb(AT)well.com), Jul 11 2001. Here "msb" = "most significant bit", A053644.
Cf. A054995, A038572, A053644, A053645, A088147, A088442, A035327.
Second column of triangle A032434. Diagonal of triangle A032434.
A181281 with s=5; A054995 with s=3; [Weisenhorn Paul (weisenhorn-f.p(AT)online.de), Oct 10 2010]
Cf. A005428.
Sequence in context: A182600 A179760 A160552 * A170898 A189442 A114144
Adjacent sequences: A006254 A006255 A006256 * A006258 A006259 A006260
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Robert G. Wilson v, Sep 21, 2003
|
| |
|
|
