A004514 -id:A004514 - cp's OEIS frontend

A053985 Replace 2^k with (-2)^k in binary expansion of n.

0, 1, -2, -1, 4, 5, 2, 3, -8, -7, -10, -9, -4, -3, -6, -5, 16, 17, 14, 15, 20, 21, 18, 19, 8, 9, 6, 7, 12, 13, 10, 11, -32, -31, -34, -33, -28, -27, -30, -29, -40, -39, -42, -41, -36, -35, -38, -37, -16, -15, -18, -17, -12, -11, -14, -13, -24, -23, -26, -25, -20, -19

Offset: 0

Henry Bottomley, Apr 03 2000

Base 2 representation for n (in lexicographic order) converted from base -2 to base 10.
Maps natural numbers uniquely onto integers; within each group of positive values, maximum is in A002450; a(n)=n iff n can be written only with 1's and 0's in base 4 (A000695).
a(n) = A004514(n) - n. - Reinhard Zumkeller, Dec 27 2003
Schroeppel gives formula n = (a(n) + b) XOR b where b = binary ...101010, and notes this formula is reversible.  The reverse a(n) = (n XOR b) - b is a bit twiddle to transform 1 bits to -1.  Odd position 0 or 1 in n is flipped by "XOR b" to 1 or 0, then "- b" gives 0 or -1.  Only odd position 1's are changed, so b can be any length sure to cover those. - Kevin Ryde, Jun 26 2020

			a(9)=-7 because 9 is written 1001 base 2 and (-2)^3 + (-2)^0 = -8 + 1 = -7.
Or by Schroeppel's formula, b = binary 1010 then a(9) = (1001 XOR 1010) - 1010 = decimal -7. - _Kevin Ryde_, Jun 26 2020

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Michael Beeler, R. William Gosper, and Richard Schroeppel, HAKMEM, MIT Artificial Intelligence Laboratory report AIM-239, February 1972, item 128 by Schroeppel, page 62. Also HTML transcription. Figure 7 path drawn 0, 1, -2, -1, 4, ... is the present sequence.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 45, 49.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625 [math.CO], 2020-2021.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Inverse of A005351. Cf. A039724, A007088, A065369, A073791, A073792, A073793, A073794, A073795, A073796 and A073835.

f[n_Integer, b_Integer] := Block[{l = IntegerDigits[n]}, Sum[l[[ -i]]*(-b)^(i - 1), {i, 1, Length[l]}]]; a = Table[ FromDigits[ IntegerDigits[n, 2]], {n, 0, 80}]; b = {}; Do[b = Append[b, f[a[[n]], 2]], {n, 1, 80}]; b
(* Second program: *)
Array[FromDigits[IntegerDigits[#, 2], -2] &, 62, 0] (* Michael De Vlieger, Jun 27 2020 *)

a(n) = fromdigits(binary(n), -2) \\ Rémy Sigrist, Sep 01 2018

def A053985(n): return  -(b:=int('10'*(n.bit_length()+1>>1),2)) + (n^b) if n else 0 # Chai Wah Wu, Nov 18 2022

From Ralf Stephan, Jun 13 2003: (Start)
G.f.: (1/(1-x)) * Sum_{k>=0} (-2)^k*x^2^k/(1+x^2^k).
a(0) = 0, a(2*n) = -2*a(n), a(2*n+1) = -2*a(n)+1. (End)
a(n) = Sum_{k>=0} A030308(n,k)*A122803(k). - Philippe Deléham, Oct 15 2011
a(n) = (n XOR b) - b where b = binary ..101010 [Schroeppel].  Any b of this form (A020988) with bitlength(b) >= bitlength(n) suits. - Kevin Ryde, Jun 26 2020

A063694 Remove odd-positioned bits from the binary expansion of n.

Original entry on oeis.org

0, 1, 0, 1, 4, 5, 4, 5, 0, 1, 0, 1, 4, 5, 4, 5, 16, 17, 16, 17, 20, 21, 20, 21, 16, 17, 16, 17, 20, 21, 20, 21, 0, 1, 0, 1, 4, 5, 4, 5, 0, 1, 0, 1, 4, 5, 4, 5, 16, 17, 16, 17, 20, 21, 20, 21, 16, 17, 16, 17, 20, 21, 20, 21, 64, 65, 64, 65, 68, 69, 68, 69, 64, 65, 64, 65, 68, 69, 68

Offset: 0

Antti Karttunen, Aug 03 2001

a(n) is the formal derivative of x*n (evaluated at x=2 after being lifted to Z[x]) where n is interpreted as a polynomial in GF(2)[x] via its binary expansion. - Keith J. Bauer, Mar 17 2024

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

			a(25) = 17 because 25 = 11001 in binary and when we AND this with 10101 we are left with 10001 = 17.

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, A063695 (remove even-positioned bits), A088442.

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

function A063694(n)
  if n le 1 then return n;
  else return 4*A063694(Floor(n/4)) + ((n mod 4) mod 2);
  end if; return A063694;
end function;
[A063694(n): n in [0..120]]; // G. C. Greubel, Dec 05 2022

every_other_pos := proc(nn, x, w) local n, i, s; n := nn; i := 0; s := 0; while(n > 0) do if((i mod 2) = w) then s := s + ((x^i)*(n mod x)); fi; n := floor(n/x); i := i+1; od; RETURN(s); end: [seq(every_other_pos(j, 2, 0), j=0..120)];

a[n_] := BitAnd[n, Sum[2^k, {k, 0, Log[2, n] // Floor, 2}]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 28 2016 *)
A063694[n_] := FromDigits[ReplaceAll[IntegerDigits[n, 4], {2 -> 0, 3 -> 1}], 4];
Array[A063694, 100, 0] (* Paolo Xausa, Feb 27 2025 *)

a(n)=sum(k=0,n,(-1)^k*2^k*floor(n/2^k))  /* since n> ceil(log(n)/log(2)) */

a(n)=if(n<0,0,sum(k=0,n,(-1)^k*2^k*floor(n/2^k))) /* since n> ceil(log(n)/log(2)) */

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

def A063694(n):
    if (n<2): return n
    else: return 4*A063694(floor(n/4)) + ((n%4)%2)
[A063694(n) for n in range(121)] # G. C. Greubel, Dec 05 2022

a(n) = Sum_{k>=0} (-1)^k*2^k*floor(n/2^k).
a(n) + A063695(n) = n.
a(n) = n - 2*a(floor(n/2)). - Vladeta Jovovic, Feb 23 2003
G.f.: 1/(1-x) * Sum_{k>=0} (-2)^k*x^2^k/(1-x^2^k). - Ralf Stephan, May 05 2003
a(n) = 4*a(floor(n/4)) + (n mod 4) mod 2. - Reinhard Zumkeller, Sep 26 2015
a(n) = Sum_{k>=0} A030308(n,k)*A199572(k). - Philippe Deléham, Jan 12 2023

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

Original entry on oeis.org

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

cp's OEIS Frontend

A053985 Replace 2^k with (-2)^k in binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A063694 Remove odd-positioned bits from the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

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