|
|
A053985
|
|
Replace 2^k with (-2)^k in binary expansion of n.
|
|
23
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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).
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
|
|
LINKS
|
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.
|
|
FORMULA
|
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) = (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
|
|
EXAMPLE
|
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
|
|
MATHEMATICA
|
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: *)
|
|
PROG
|
(PARI) a(n) = fromdigits(binary(n), -2) \\ Rémy Sigrist, Sep 01 2018
(Python)
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
base,easy,sign
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|