One of the given formulas there is very interesting:

a(0) = 0;I've still yet to decypher how that formula is derived, but here's mine in Maple:

a(2n) = a(n)+a(n-1)+n;

a(2n+1) = 2a(n)+n+1

full := n -> n * 2^n / 2:My formula basically partitions the rectangle of bits into 3 parts: top (first 2^k lines, explicit formula trivial), bottom-left (a single column of 1's) and bottom-right (the rest, counted recursively).

flog2 := n -> floor(log[2](n)):

f := n -> `if`(n = 0, 0,

full(flog2(n)) + (1 + n - 2^flog2(n)) + f(n - 2^flog2(n))

):

Ah, got it. The first formula reduces the problem by separating out the rightmost column and deinterleaving what's left. In any case, this problem is inspired by a Facebook puzzle, whose exact definition I can no longer find. I can assume it to be the following:

GivenMy solution in Maple:`a, b`

, count how many numbers in the interval`[a, b]`

have prime number of 1's in their binary representation.

row := k -> add(binomial(k, i)*x^i, i=0..k):

g := (n, k) -> `if`(n = 0, 1,

`if`(2^k > n,

g(n, k - 1),

row(k) + x * g(n - 2^k, k - 1)

)

):

f := n -> expand(sort(

g(n, floor(evalf(log[2](n))))

)):

> f(100);Basically, a term

6 5 4 3 2

2 x + 11 x + 26 x + 33 x + 21 x + 7 x + 1

`c*x^i`

in the polynomial `f(n)`

means that among all the numbers in the interval `[0..n]`

, exactly `c`

have `i`

1's in their binary representation.The rest, of course, is straightforward:

frange := (lo, hi) -> f(hi) - f(lo - 1):

addprimecoeff := poly -> add(

`if`(isprime(i), coeff(poly, x, i), 0),

i=0..degree(poly)

):

> addprimecoeff(frange(2^50, 2^64));Alternatively, we can follow the admittedly more elegant partitioning scheme given in the first formula and generate the polynomial as follows:

4358342664758484397

h := n -> `if`(n = 0, 1,

`if`(type(n, even),

x * h(n / 2 - 1) + h(n / 2),

(1 + x) * h((n - 1) / 2)

)

):

f := n -> expand(sort(

h(n)

)):

> addprimecoeff(frange(999, 999999999));

328122619

This agrees with somebody else's solution (no source code).

## No comments:

## Post a Comment