## Quintinomial coefficients

Published on Sunday, 29th January 2017, 04:00 am; Solved by 337;
Difficulty rating: 40%

### Problem 588

The coefficients in the expansion of $(x+1)^k$ are called binomial coefficients.
Analoguously the coefficients in the expansion of $(x^4+x^3+x^2+x+1)^k$ are called quintinomial coefficients.
(quintus= Latin for fifth).

Consider the expansion of $(x^4+x^3+x^2+x+1)^3$:
$x^{12}+3x^{11}+6x^{10}+10x^9+15x^8+18x^7+19x^6+18x^5+15x^4+10x^3+6x^2+3x+1$
As we can see 7 out of the 13 quintinomial coefficients for $k=3$ are odd.

Let $Q(k)$ be the number of odd coefficients in the expansion of $(x^4+x^3+x^2+x+1)^k$.
So $Q(3)=7$.

You are given $Q(10)=17$ and $Q(100)=35$.

Find $\sum_{k=1}^{18}Q(10^k)$.