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,2

Comments

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

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

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

Example

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.

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

Prog

(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
(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
(Python)
def A088442(n): return ((n&((1<<(m:=n.bit_length())+(m&1))-1)//3)<<1)+1 # Chai Wah Wu, Jan 30 2023

Crossrefs

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

Sequence in context: A082511 A265307 A133579 * A037095 A160654 A146436

Adjacent sequences: A088439 A088440 A088441 * A088443 A088444 A088445

Keyword

nonn,easy

Author

N. J. A. Sloane, Nov 09 2003

Extensions

More terms from Emeric Deutsch, May 27 2004

Status

approved