Less than a million and divisible by three

Let $P_k(x)$ be $P_k(x)=(x+x^3+x^5+x^7+x^9)^k$ Imagine that you have expanded $P_k(x)$ . $P_k(x)=a_{9k}x^{9k}+...+a_1x+a_0$ The answer of this problem in the case that numbers have $k$ digits is the sum $a_0+a_3+...+a_{9k}$ , which is, by the "root of unity filter" theorem, $\frac{P_k(1)+P_k(\omega)+P_k(\omega^2)}{3}$ Where $1,\omega,\omega^2$ are the three complex cubic roots of unity. Summing up from $1$ to $6$ gives $\sum_{k=1}^6\frac{P_k(1)+P_k(\omega)+P_k(\omega^2)}{3}$ recalling that $1+\omega+\omega^2=0$ and that $\omega^k=\omega^{k \pmod 3}$ , we can easily find all these values:
$\frac{5^6-2}{3}+\frac{5^5+1}{3}+\frac{5^4-1}{3}+\frac{5^3-2}{3}+\frac{5^2-1}{3}+\frac{5+1}{3}=\boxed{6510}$

Let $P(n,k)$ denote the number of integers with $n$ digits comprising of all odd numerals such that it leaves remainder $k$ when divided by $3$ , where $0\leq k \leq 2$ .

We have the following recursions $P(n,0)=2P(n-1,0)+P(n-1,1)+2P(n-1,2)\\ P(n,1)=2P(n-1,0)+ 2P(n-1,1)+ P(n-1,2)\\ P(n,2)=P(n-1,0)+2P(n-1,1)+2P(n-1,2)$ with the initial conditions $P(1,0)=2, P(1,1)=2,P(1,2)=1$ . Hence the recursion is now fully specified. We require $\sum_{n=1}^{6}P(n,0)=6510$

Of the natural numbers less than $10^n$ , $5^n$ have only odd digits (when viewed as $n$ -digit numbers with leading zeros). Therefore, the answer is $\displaystyle\frac{1}{3}\sum_{k=1}^65^k=\frac{5}{12}(5^6-1)=\boxed{6510}.$

>> a=[x for x in range(1,1000000) if len([i for i in str(x) if int(i)%2!=0])==len(str(x)) and x%3==0]

>> len(a)

6510

product is an iterator that makes Cartesian products. In this case then, it behaves like an odometer, creating lists of digits from only the odd digits. The reduce / lambda construction turns the lists of digits from product into numbers to find out if they are divisible by three.