A088442 A linear version of the Josephus problem.
1, 3, 1, 3, 9, 11, 9, 11, 1, 3, 1, 3, 9, 11, 9, 11, 33, 35, 33, 35, 41, 43, 41, 43, 33, 35, 33, 35, 41, 43, 41, 43, 1, 3, 1, 3, 9, 11, 9, 11, 1, 3, 1, 3, 9, 11, 9, 11, 33, 35, 33, 35, 41, 43, 41, 43, 33, 35, 33, 35, 41, 43, 41, 43, 129, 131, 129, 131, 137, 139, 137, 139, 129, 131
Offset: 0
Examples
If n=4, 2n+1 = 9 = 1 + 0*2 + 0*2^2 + 1*2^3, so a(4) = 1 + 0*2 + 1*2^3 = 9.
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
- C. Groer, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825. (This is the sequence W(2n+1).)
- Index entries for sequences related to the Josephus Problem
Programs
-
Haskell
a088442 = (+ 1) . a004514 -- Reinhard Zumkeller, Sep 26 2015
-
Magma
function A063694(n) if n le 1 then return n; else return 4*A063694(Floor(n/4)) + (n mod 2); end if; return A063694; end function; A088442:= func< n | 2*A063694(n) + 1 >; [A088442(n): n in [0..100]]; // G. C. Greubel, Dec 05 2022
-
Maple
a:=proc(n) local b: b:=convert(2*n+1,base,2): 1+sum(b[2*j]*2^(2*j-1),j=1..nops(b)/2) end: seq(a(n),n=0..100); with(Bits): seq(And(2*n+1, convert("aaaaaa", decimal, hex)) + 1, n=0..127); # Georg Fischer, Dec 03 2022 -
Mathematica
A004514[n_]:= A004514[n]= If[n==0, 0, 2*(n-A004514[Floor[n/2]])]; A088442[n_] := A004514[n] +1; Table[A088442[n], {n,0,100}] (* G. C. Greubel, Dec 05 2022 *)
-
Python
def A088442(n): return ((n&((1<<(m:=n.bit_length())+(m&1))-1)//3)<<1)+1 # Chai Wah Wu, Jan 30 2023
-
SageMath
def A063694(n): if (n<2): return n else: return 4*A063694(floor(n/4)) + (n%2) def A088442(n): return 2*A063694(n) + 1 [A088442(n) for n in range(101)] # G. C. Greubel, Dec 05 2022
Formula
To get a(n), write 2n+1 as Sum b_j 2^j, then a(n) = 1 + Sum_{j odd} b_j 2^j.
Equals A004514(n) + 1. - Chris Groer (cgroer(AT)math.uga.edu), Nov 10 2003
a(n) = 2*A063694(n) + 1. - G. C. Greubel, Dec 05 2022
Extensions
More terms from Emeric Deutsch, May 27 2004
Comments