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