A306607 The bottom entry in the difference table of the binary digits of n.

0, 1, 1, 0, 1, 2, -1, 0, 1, 0, 4, 3, -2, -3, 1, 0, 1, 2, -3, -2, 7, 8, 3, 4, -3, -2, -7, -6, 3, 4, -1, 0, 1, 0, 6, 5, -9, -10, -4, -5, 11, 10, 16, 15, 1, 0, 6, 5, -4, -5, 1, 0, -14, -15, -9, -10, 6, 5, 11, 10, -4, -5, 1, 0, 1, 2, -5, -4, 16, 17, 10, 11, -19

Offset

0,6

Comments

By convention, a(0) = 0.

For any n > 0: let (b_0, ..., b_w) be the binary representation of n:

- b_w = 1, and for any k = 0..w, 0 <= b_k <= 1,

- n = Sum_{k = 0..w} b_k * 2^k,

- a(n) is the unique value remaining after taking successively the first differences of (b_0, ..., b_w) w times.

From Robert Israel, Mar 07 2019: (Start)

If n is odd then f(A030101(n)) = (-1)^A000523(n)*f(n).

In particular, if n is in A048701 then a(n)=0.

a(n) == 1 (mod A014963(A000523(n))) if n is even,

a(n) == 0 (mod A014963(A000523(n))) if n is odd. (End)

Links

Robert Israel, Table of n, a(n) for n = 0..10000

Formula

a(2^k) = 1 for any k >= 0.

a(2^k-1) = 0 for any k > 1.

a(3*2^k) = -k for any k >= 0.

a(n) = Sum_{k=0..A000523(n)} binomial(A000523(n), k)*(-1)^k*A030302(n,k). - David A. Corneth, Mar 07 2019

G.f.: 1/(x-1)*Sum_{k>=0}(x^(2^(k+1))-x^(2^k) + x^(2^k)/(x^(2^k)+1)*Sum_{m>=k+1}(binomial(m,k)*(-1)^(m-k)*(x^(2^(m+1))-x^(2^m)))). - Robert Israel, Mar 07 2019

Example

For n = 42:
- the binary representation of 42 is "101010",
- the corresponding difference table is:
   0   1   0   1   0   1
     1  -1   1  -1   1
      -2   2  -2   2
         4  -4   4
          -8   8
            16
- hence a(42) = 16.

Maple

f:= proc(n) local L;
  L:= convert(n, base, 2);
  while nops(L) > 1 do
    L:= L[2..-1]-L[1..-2]
  od;
  op(L)
end proc:
map(f, [$0..100]); # Robert Israel, Mar 07 2019

Mathematica

a[n_] := NestWhile[Differences, Reverse[IntegerDigits[n, 2]], Length[#] > 1 &][[1]]; Array[a, 100, 0] (* Amiram Eldar, Mar 08 2019 *)

Prog

(PARI) a(n) = if (n, my (v=Vecrev(binary(n))); while (#v>1, v=vector(#v-1, k, (v[k+1]-v[k]))); v[1], 0)
(PARI) a(n) = my(b = binary(n), s = -1); sum(i = 1, #b, s=-s; binomial(#b-1, i-1) * b[i] * s) \\ David A. Corneth, Mar 07 2019

Crossrefs

Cf. A000523, A007088, A030101, A030190, A030302, A048701, A014963, A187202, A241494.

Sequence in context: A072175 A280712 A363926 * A268611 A092147 A208134

Adjacent sequences: A306604 A306605 A306606 * A306608 A306609 A306610

Keyword

sign,base,look

Author

Rémy Sigrist, Feb 28 2019

Status

approved