A090569 -id:A090569 - cp's OEIS frontend

A063695 Remove even-positioned bits from the binary expansion of n.

0, 0, 2, 2, 0, 0, 2, 2, 8, 8, 10, 10, 8, 8, 10, 10, 0, 0, 2, 2, 0, 0, 2, 2, 8, 8, 10, 10, 8, 8, 10, 10, 32, 32, 34, 34, 32, 32, 34, 34, 40, 40, 42, 42, 40, 40, 42, 42, 32, 32, 34, 34, 32, 32, 34, 34, 40, 40, 42, 42, 40, 40, 42, 42, 0, 0, 2, 2, 0, 0, 2, 2, 8, 8, 10, 10, 8, 8, 10, 10, 0, 0

Offset: 0

Antti Karttunen, Aug 03 2001

In the base 4 expansion of n, change 1 to 0 and 3 to 2. - Paolo Xausa, Feb 27 2025

			a(25) = 8 because 25 = 11001 in binary and when we AND this with 1010 we are left with 1000 = 8.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A004514 (bisection), A063694 (remove odd-positioned bits), A090569.

a063695 0 = 0
a063695 n = 4 * a063695 n' + 2 * div q 2
            where (n', q) = divMod n 4
-- Reinhard Zumkeller, Sep 26 2015

[seq(every_other_pos(j,2,1),j=0..120)]; # Function every_other_pos given at A063694.

A063695[n_] := FromDigits[ReplaceAll[IntegerDigits[n, 4], {1 -> 0, 3 -> 2}], 4];
Array[A063695, 100, 0] (* Paolo Xausa, Feb 27 2025 *)

def A063695(n): return n&((1<<(m:=n.bit_length())+(m&1^1))-1)//3 # Chai Wah Wu, Jan 30 2023

a(n) + A063694(n) = n.
a(n) = 2*(floor(n/2)-a(floor(n/2))). - Vladeta Jovovic, Feb 23 2003
From Ralf Stephan, Oct 06 2003: (Start)
G.f. 1/(1-x) * Sum_{k>=0} (-2)^k*2t^2/(1-t^2) where t = x^2^k.
Members of A004514 written twice.
(End)
a(n) = 4 * a(floor(n / 4)) + 2 * floor(n mod 4 / 2). - Reinhard Zumkeller, Sep 26 2015
a(n) = A090569(n+1)-1. - R. J. Mathar, Jun 22 2020
a(n) = 2*(n - A380110(n)). - Paolo Xausa, Feb 27 2025

A088442 A linear version of the Josephus problem.

Original entry on oeis.org

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

N. J. A. Sloane, Nov 09 2003

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

			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.

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

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

a088442 = (+ 1) . a004514  -- Reinhard Zumkeller, Sep 26 2015

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

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

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

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

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

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

More terms from Emeric Deutsch, May 27 2004

A088452 The survivor w(n,4) in a modified Josephus problem, with a step of 4.

Original entry on oeis.org

1, 1, 1, 3, 2, 6, 5, 1, 3, 10, 7, 9, 1, 2, 6, 5, 17, 18, 11, 13, 15, 10, 2, 1, 11, 10, 7, 9, 17, 30, 31, 31, 19, 22, 22, 27, 26, 23, 18, 1, 1, 1, 6, 19, 17, 18, 17, 13, 15, 14, 30, 29, 53, 50, 55, 55, 50, 33, 34, 38, 38, 39, 49, 47, 46, 46, 41, 29, 31, 1, 2, 6, 1, 1, 3, 10, 34, 34, 34, 30

Offset: 1

N. J. A. Sloane, Nov 09 2003

nonn

Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110(9) (2003), 812-825.
Index entries for sequences related to the Josephus Problem

Cf. A006257, A088442, A088443, A090569.

w4[1] = v4[1] = u4[1] = 1; w4[n_] := w4[n] = Switch[ Mod[n, 4], 0, n + 1 - Ceiling[4w4[ Ceiling[3n/4]]/3], 1, n + 1 - Floor[(4w4[ Ceiling[3n/4]] + 1)/3], 2, n + 1 - Floor[4v4[ Ceiling[3n/4]]/3], 3, n + 1 - Floor[(4u4[ Ceiling[3n/4]] - 1)/3]]; v4[n_] := v4[n] = Switch[ Mod[n, 4], 0, n + 1 - Floor[(4w4[ Ceiling[3n/4]] + 1)/3], 1, n + 1 - Floor[(4v4[ Ceiling[3n/4]])/3], 2, n + 1 - Floor[(4u4[ Ceiling[3n/4]] - 1)/3], 3, n + 1 - Ceiling[ 4w4[ Floor[3n/4]]/3]]; u4[n_] := u4[n] = Switch[ Mod[n, 4], 0, n + 1 - Floor[ 4v4[ Ceiling[3n/4]]/3], 1, n + 1 - Floor[ (4u4[ Ceiling[3n/4]] - 1)/3], 2, n + 1 - Ceiling[ 4w4[ Floor[3n/4]]/3], 3, n + 1 - Floor[(4w4[ Floor[3n/4]] + 1)/3]]; Table[ w4[n], {n, 81}] (* from Chris Groer modified by Robert G. Wilson v Nov 15 2003 *)

Terms computed by Chris Groer (cgroer(AT)math.uga.edu)

A088443 A linear version of the Josephus problem: a(n) = the function w_3(n).

Original entry on oeis.org

1, 2, 1, 4, 1, 1, 7, 8, 8, 1, 2, 1, 2, 5, 14, 14, 17, 17, 17, 17, 14, 2, 1, 4, 1, 1, 2, 4, 4, 5, 11, 32, 31, 34, 31, 31, 37, 38, 38, 38, 41, 37, 38, 37, 38, 31, 31, 1, 4, 5, 1, 7, 8, 8, 1, 2, 1, 2, 5, 4, 1, 8, 8, 8, 8, 11, 11, 20, 23, 25, 71, 71, 68, 70, 68, 76, 74, 68, 68, 68, 70, 82, 83, 82

Offset: 1

N. J. A. Sloane, Nov 09 2003

nonn

The survivor w(n,3) in a modified Josephus problem, with a step of 3.

See A090569 or the reference for the definition of w(n,q).

Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.
Index entries for sequences related to the Josephus Problem

Cf. A006257, A088442, A088452, A090569.

A recurrence is given in the reference.

Terms computed by Chris Groer (cgroer(AT)math.uga.edu)

More terms from John W. Layman, Feb 05 2004

A225489 Elimination order for the first person in a linear Josephus problem.

Original entry on oeis.org

1, 2, 2, 3, 5, 6, 5, 6, 8, 9, 8, 9, 12, 13, 11, 12, 17, 18, 14, 15, 21, 22, 17, 18, 23, 24, 20, 21, 27, 28, 23, 24, 32, 33, 26, 27, 36, 37, 29, 30, 38, 39, 32, 33, 42, 43, 35, 36, 48, 49, 38, 39, 52, 53, 41, 42, 53, 54, 44, 45, 57, 58, 47, 48, 65, 66, 50, 51

Offset: 1

Marcus Hedbring, May 08 2013

nonn

The process is identical to that of A090569 where n persons are arranged on a line and every second person is eliminated. When we reach the end of the line the direction is reversed without double-counting the person at the end. a(n) is the order in which the person originally first in line is eliminated.

			If there are 7 persons to begin with, they are eliminated in the following order: 2,4,6,5,1,7,3. So the first person (the person originally first in line) is eliminated as number 5. Therefore a(7) = 5.

Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.
Index entries for sequences related to the Josephus Problem

Cf. A090569, A088442.

t = {1}; Do[AppendTo[t, Switch[Mod[n,4], 0, 3*n/4, 1, t[[1 + (n-1)/4]] + 3*(n-1)/4, 2, t[[1 + (n-2)/4]] + 3*(n-2)/4 + 1, 3, 3*(n-3)/4 + 2, 4, Mod[n,4] + 1]], {n, 2, 100}]; t (* T. D. Noe, May 17 2013 *)

For n=4m then a(n) = 3*n/4;
for n=4m+1 then a(n) = a(1+(n-1)/4) + 3*(n-1)/4;
for n=4m+2 then a(n) = a(1+(n-2)/4) + 3*(n-2)/4 + 1;
for n=4m+3 then a(n) = 3*(n-3)/4 + 2.

A335552 Triangle T(n,k) read by rows: in the Josephus problem with n initial numbers on a line: eliminate each second and reverse left-right-direction of elimination. T(n,k) is the (n-k+1)st element removed, 1<=k<=n.

Original entry on oeis.org

1, 3, 1, 3, 1, 4, 1, 5, 3, 4, 1, 5, 3, 6, 4, 3, 7, 1, 5, 6, 4, 3, 7, 1, 5, 8, 6, 4, 9, 1, 5, 3, 7, 8, 6, 4, 9, 1, 5, 3, 7, 10, 8, 6, 4, 11, 3, 7, 1, 5, 9, 10, 8, 6, 4, 11, 3, 7, 1, 5, 9, 12, 10, 8, 6, 4, 9, 1, 13, 5, 3, 7, 11, 12, 10, 8, 6, 4, 9, 1, 13, 5, 3, 7, 11, 14, 12, 10, 8, 6, 4, 11, 3, 15

Offset: 1

R. J. Mathar, Jun 22 2020

			The triangle starts
   1
   3   1
   3   1   4
   1   5   3   4
   1   5   3   6   4
   3   7   1   5   6   4
   3   7   1   5   8   6   4
   9   1   5   3   7   8   6   4
   9   1   5   3   7  10   8   6   4
  11   3   7   1   5   9  10   8   6   4
  11   3   7   1   5   9  12  10   8   6   4
   9   1  13   5   3   7  11  12  10   8   6   4
   9   1  13   5   3   7  11  14  12  10   8   6   4
  11   3  15   7   1   5   9  13  14  12  10   8   6   4
  11   3  15   7   1   5   9  13  16  14  12  10   8   6   4
   1  17   9  13   5   3   7  11  15  16  14  12  10   8   6   4
   1  17   9  13   5   3   7  11  15  18  16  14  12  10   8   6   4
   3  19  11  15   7   1   5   9  13  17  18  16  14  12  10   8   6   4
   3  19  11  15   7   1   5   9  13  17  20  18  16  14  12  10   8   6   4

Georg Fischer, Table of n, a(n) for n = 1..1000
K. Matsumoto, T. Nakamigawa, M. Watanabe, On the switchback vertion of Josephus Problem, Yokohama Math. J. 53 (2007) 83, function f_k(n).
Index to sequences related to the Josephus problem

Cf. A090569 (column k=1).

sigr := proc(n,r)
    floor(n/2^r) ;
end proc:
# A063695
f := proc(n)
    local ndigs,fn,k ;
    ndigs := convert(n,base,2) ;
    fn := 0 ;
    for k from 2 to nops(ndigs) by 2 do
        fn := fn+op(k,ndigs)*2^(k-1)
    end do;
    fn ;
end proc:
g := proc(t,n)
    local r;
    if t =1 then
        0 ;
    elif t > 1 then
        r := ilog2( (n-1)/(t-1) ) ;
        (-2)^r*(f( sigr(2*n-1,r) )+f( sigr(n-1,r) )-2*t+3) ;
    end if;
end proc:
ft := proc(t,n)
    f(n-1)+1+g(t,n) ;
end proc:
for n from 1 to 20 do
    for t from 1 to n-1 do
        printf("%3d ", ft(t,n)) ;
    end do:
    printf("\n") ;
end do:

cp's OEIS Frontend

A063695 Remove even-positioned bits from the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Formula

A088442 A linear version of the Josephus problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Python

SageMath

Formula

Extensions

A088452 The survivor w(n,4) in a modified Josephus problem, with a step of 4.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A088443 A linear version of the Josephus problem: a(n) = the function w_3(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A225489 Elimination order for the first person in a linear Josephus problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A335552 Triangle T(n,k) read by rows: in the Josephus problem with n initial numbers on a line: eliminate each second and reverse left-right-direction of elimination. T(n,k) is the (n-k+1)st element removed, 1<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple