login
A linear version of the Josephus problem.
9

%I #34 Jan 30 2023 09:42:33

%S 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,

%T 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,

%U 41,43,33,35,33,35,41,43,41,43,129,131,129,131,137,139,137,139,129,131

%N A linear version of the Josephus problem.

%C Or a(n) is in A145812 such that (2*n + 3 - a(n))/2 is in A145812 as well. Note also that a(n) + 2*A090569(n+1) = 2*n + 3. - _Vladimir Shevelev_, Oct 20 2008

%H Reinhard Zumkeller, <a href="/A088442/b088442.txt">Table of n, a(n) for n = 0..10000</a>

%H C. Groer, <a href="https://www.jstor.org/stable/3647800">The Mathematics of Survival: From Antiquity to the Playground</a>, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825. (This is the sequence W(2n+1).)

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%F To get a(n), write 2n+1 as Sum b_j 2^j, then a(n) = 1 + Sum_{j odd} b_j 2^j.

%F Equals A004514(n) + 1. - Chris Groer (cgroer(AT)math.uga.edu), Nov 10 2003

%F a(n) = 2*A063694(n) + 1. - _G. C. Greubel_, Dec 05 2022

%e 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.

%p 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);

%p with(Bits): seq(And(2*n+1, convert("aaaaaa", decimal, hex)) + 1, n=0..127); # _Georg Fischer_, Dec 03 2022

%t A004514[n_]:= A004514[n]= If[n==0, 0, 2*(n-A004514[Floor[n/2]])];

%t A088442[n_] := A004514[n] +1;

%t Table[A088442[n], {n,0,100}] (* _G. C. Greubel_, Dec 05 2022 *)

%o (Haskell)

%o a088442 = (+ 1) . a004514 -- _Reinhard Zumkeller_, Sep 26 2015

%o (Magma)

%o function A063694(n)

%o if n le 1 then return n;

%o else return 4*A063694(Floor(n/4)) + (n mod 2);

%o end if; return A063694;

%o end function;

%o A088442:= func< n | 2*A063694(n) + 1 >;

%o [A088442(n): n in [0..100]]; // _G. C. Greubel_, Dec 05 2022

%o (SageMath)

%o def A063694(n):

%o if (n<2): return n

%o else: return 4*A063694(floor(n/4)) + (n%2)

%o def A088442(n): return 2*A063694(n) + 1

%o [A088442(n) for n in range(101)] # _G. C. Greubel_, Dec 05 2022

%o (Python)

%o def A088442(n): return ((n&((1<<(m:=n.bit_length())+(m&1))-1)//3)<<1)+1 # _Chai Wah Wu_, Jan 30 2023

%Y Cf. A006257, A063694, A088443, A088452, A090569, A145812.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_, Nov 09 2003

%E More terms from _Emeric Deutsch_, May 27 2004