cp's OEIS Frontend

A088442 A linear version of the Josephus problem.

%I A088442 #34 Jan 30 2023 09:42:33
%S A088442 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 A088442 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 A088442 41,43,33,35,33,35,41,43,41,43,129,131,129,131,137,139,137,139,129,131
%N A088442 A linear version of the Josephus problem.
%C A088442 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 A088442 Reinhard Zumkeller, <a href="/A088442/b088442.txt">Table of n, a(n) for n = 0..10000</a>
%H A088442 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 A088442 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F A088442 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 A088442 Equals A004514(n) + 1. - Chris Groer (cgroer(AT)math.uga.edu), Nov 10 2003
%F A088442 a(n) = 2*A063694(n) + 1. - _G. C. Greubel_, Dec 05 2022
%e A088442 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 A088442 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 A088442 with(Bits): seq(And(2*n+1, convert("aaaaaa", decimal, hex)) + 1, n=0..127); # _Georg Fischer_, Dec 03 2022
%t A088442 A004514[n_]:= A004514[n]= If[n==0, 0, 2*(n-A004514[Floor[n/2]])];
%t A088442 A088442[n_] := A004514[n] +1;
%t A088442 Table[A088442[n], {n,0,100}] (* _G. C. Greubel_, Dec 05 2022 *)
%o A088442 (Haskell)
%o A088442 a088442 = (+ 1) . a004514  -- _Reinhard Zumkeller_, Sep 26 2015
%o A088442 (Magma)
%o A088442 function A063694(n)
%o A088442   if n le 1 then return n;
%o A088442   else return 4*A063694(Floor(n/4)) + (n mod 2);
%o A088442   end if; return A063694;
%o A088442 end function;
%o A088442 A088442:= func< n | 2*A063694(n) + 1 >;
%o A088442 [A088442(n): n in [0..100]]; // _G. C. Greubel_, Dec 05 2022
%o A088442 (SageMath)
%o A088442 def A063694(n):
%o A088442     if (n<2): return n
%o A088442     else: return 4*A063694(floor(n/4)) + (n%2)
%o A088442 def A088442(n): return 2*A063694(n) + 1
%o A088442 [A088442(n) for n in range(101)] # _G. C. Greubel_, Dec 05 2022
%o A088442 (Python)
%o A088442 def A088442(n): return ((n&((1<<(m:=n.bit_length())+(m&1))-1)//3)<<1)+1 # _Chai Wah Wu_, Jan 30 2023
%Y A088442 Cf. A006257, A063694, A088443, A088452, A090569, A145812.
%K A088442 nonn,easy
%O A088442 0,2
%A A088442 _N. J. A. Sloane_, Nov 09 2003
%E A088442 More terms from _Emeric Deutsch_, May 27 2004