Project Euler Problem 967
nA positive integer n is considered B-trivisible if the sum of all different prime factors of n which are not larger tha
Solution
Answer: 357591131712034236
Let
$$s_B(n)=\sum_{\substack{p\mid n\ p\le B}} p \pmod 3,$$
where the sum is over distinct prime divisors $p\le B$.
We want the count
$$F(N,B)=#{n\le N:\ s_B(n)\equiv 0\pmod 3}.$$
Using the standard cube-root-of-unity filter with
$$\omega=e^{2\pi i/3},$$
the indicator of divisibility by $3$ is
$$\frac{1+\omega^{s_B(n)}+\omega^{-s_B(n)}}{3}.$$
Hence
$$F(N,B) = \frac13 \sum_{n\le N} \left( 1+\omega^{s_B(n)}+\omega^{-s_B(n)} \right).$$
Expanding multiplicatively over the primes $p\le 120$ gives
$$\omega^{s_B(n)} = \prod_{\substack{p\le120\ p\ne3}} \left(1+(\omega^{p}-1)\mathbf 1_{p\mid n}\right).$$
After inclusion–exclusion,
$$F(N,120) = \frac13 \sum_{d} \Bigl(c(d)+\overline{c(d)}\Bigr) \left\lfloor\frac{10^{18}}{d}\right\rfloor,$$
where $d$ runs over squarefree products of primes $\le120,\ p\neq3$, and
$$c(d)=\prod_{p\mid d}(\omega^p-1).$$
If $a$ is the number of prime factors $p\equiv1\pmod3$ and $b$ the number with $p\equiv2\pmod3$, then
$$c(d)+\overline{c(d)} = 3^{\min(a,b)}, t_{|a-b|},$$
where
$$t_0=2,\qquad t_1=-3,\qquad t_n=-3t_{n-1}-3t_{n-2}.$$
A depth-first enumeration of all admissible squarefree divisors $d\le10^{18}$ (about $7.0\times10^7$ states) evaluates the sum exactly in under a second in optimized C++.
The resulting value is
Answer: 357591131712034236