Determining coefficient of x^m term in (x^2 + x + 1)^n is even or odd

Question

For a given integers n and m, determine that coefficient of x^m term in (x^2+x+1)^n is even or odd?

For example, if n=3 and m=4, (x^2+x+1)^3 = x^6 + 3x^5 + [[6x^4]] + 7x^3 + 6x^2 + 3x + 1, so coefficient of x^4 term is 6 (=even).

n and m is as large as 10^12 and I want to calculate in a few seconds, so you can't calculate in linear time.

Do you have any efficient algorithm?

Answer 1

Yes, linear time in the number of bits in the input.

The coefficients in question are trinomial coefficients T(n, m). For binomial coefficients, we would use Lucas's theorem; let's work out the trinomial analog for p = 2.

Working mod 2 and following the proof of Nathan Fine,

(1 + x + x^2)^{2^i} = 1 + x^{2^i} + x^{2^{2 i}}

(1 + x + x^2)^n
    = prod_i ((1 + x + x^2)^{2^i n_i})
        where n = sum_i n_i 2^i and n_i in {0, 1} for all i
        (i.e., n_i is the binary representation of n
    = prod_i (1 + x^{2^i n_i} + x^{2^i 2 n_i})
    = prod_i sum_{m_i = 0}^{2 n_i} x^{2^i}
    = sum_{(m_i)} prod_i x^{2^i m_i}
        taken over sequences (m_i) where 0 ≤ m_i ≤ 2 n_i.

In the binomial case, the next step is to observe that, for the coefficient of x^m, there's at most one choice of (m_i) whose x^{2^i m_i} factors have the right product, i.e., the binary representation of m.

In the trinomial case, we have to consider binary pseudo-representations (m_i) of m where pseudo-bits can be zero, one, or two. There is a contribution to the sum if and only if for all i such that n_i = 0, we have m_i = 0.

We can write an automaton that scans n and m bit by bit. State a is initial and accepting.

a (0:0:nm') -> a nm'    [emit 0]
a (1:0:nm') -> a nm'    [emit 0]
            -> b nm'    [emit 2]
a (1:1:nm') -> a nm'    [emit 1]

b (0:1:nm') -> a nm'    [emit 0]
b (1:0:nm') -> b nm'    [emit 1]
b (1:1:nm') -> a nm'    [emit 0]
            -> b nm'    [emit 2]

We can use dynamic programming to count the paths. In code form:

def trinomial_mod_two(n, m):
    a, b = 1, 0
    while m:
        n1, n = n & 1, n >> 1
        m1, m = m & 1, m >> 1
        if n1:
            if m1:
                a, b = a ^ b, b
            else:
                a, b = a, a ^ b
        elif m1:
            a, b = b, 0
        else:
            a, b = a, 0
    return a

Branchless version for giggles:

def trinomial_mod_two_branchless(n, m):
    a, b = 1, 0
    while m:
        n1, n = n & 1, n >> 1
        m1, m = m & 1, m >> 1
        a, b = ((n1 | ~m1) & a) ^ (m1 & b), ((n1 & ~m1) & a) ^ (n1 & b)
    return a

Answer 2

First note, that if one is only interested in whether the coefficient of x^m is odd or even, one can consider the coefficients of the polynomial to be elements of the finite field F2.

Note (1+x+x^2)^2 = (1+x^2+x^4) mod 2 because cross terms are all even. In fact, if n is a power of 2, then (1+x+x^2)^n = (1 + x^n + x^2n) mod 2.

For general n, write it as a sum of powers of 2 (that is, in binary).

n = (2^a1 + 2^a2 + 2^a3 + ... + 2^ak).

Then multiply together the powers corresponding to each power of 2:

(1+x+x^2)^n = (1+x^(2^a1)+x^(2^(a1+1))) * ((1+x^(2^a2)+x^(2^(a2+1))) * ...

Each of the terms in this product now has only 3 factors, and there's at most 35 or 36 of them if n is bounded by 10^12. So it's easy to multiply them together.

Here's some Python code that does this:

# poly_times computes the product of polynomials
# p and q over the field F2. They are each
# represented by a set of non-zero coefficients.
# For example set([0, 2, 5]) corresponds to x^0 + x^2 + x^5.
def poly_times(p, q):
    result = set()
    for i in p:
        for j in q:
            if i+j in result:
                result.remove(i+j)
            else:
                result.add(i+j)
    return result

# Return the coefficient of x^m in (1+x+x^2)^n.
def coeff(n, m):
    prod = set([0])
    i = 0
    while n:
        if n % 2:
            prod = poly_times(prod, [0, 2**i, 2**(i+1)])
        i += 1
        n >>= 1
    return 1 if m in prod else 0

for m in xrange(10):
    print m, coeff(3, m)

print coeff(1947248745, 1947248745034)    

Optimization

For n with a large number of bits set, this gets too slow as n approached 10^12.

But, one can speed things up greatly by splitting the polynomial power into two parts, and then finding the coefficient of m in the last step not by doing a full polynomial multiplication but instead by counting pairs of coefficient in each part which sum to m. Here's the optimized coeff:

# poly_times computes the product of polynomials
# p and q over the field F2. They are each
# represented by a set of non-zero coefficients.
# For example set([0, 2, 5]) corresponds to x^0 + x^2 + x^5.
# Coefficients larger than m are discarded.
def poly_times(p, q, m):
    result = set()
    for i in p:
        for j in q:
            if i + j > m:
                continue
            if i+j in result:
                result.remove(i+j)
            else:
                result.add(i+j)
    return result

# Return the coefficient of x^m in (1+x+x^2)^n.
def coeff(n, m):
    if m > 2*n: return 0
    prod = [set([0]), set([0])]
    i = 0
    while n:
        if n % 2:
            prod[i//20] = poly_times(prod[i//20], [0, 2**i, 2**(i+1)], m)
        i += 1
        n >>= 1
    s = 0
    for x in prod[0]:
        s += m-x in prod[1]
    return s % 2

for m in xrange(10):
    print m, coeff(3, m)

print coeff(0xffffffffff, 0xffffffffff)

Note that this can compute coeff(0xffffffffff, 0xffffffffff) in a few seconds, and 0xffffffffff is larger than 10**12.