projecteuler.net

5-Smooth Pairs

Published on Sunday, 6th October 2019, 10:00 am; Solved by 123

Problem 682

5-smooth numbers are numbers whose largest prime factor doesn't exceed 5.
5-smooth numbers are also called Hamming numbers.

Let $\Omega(a)$ be the count of prime factors of $a$ (counted with multiplicity).
Let $s(a)$ be the sum of the prime factors of $a$ (with multiplicity).
For example, $\Omega(300) = 5$ and $s(300) = 2+2+3+5+5 = 17$.

Let $f(n)$ be the number of pairs, $(p,q)$, of Hamming numbers such that $\Omega(p)=\Omega(q)$ and $s(p)+s(q)=n$.
You are given $f(10)=4$ (the pairs are $(4,9),(5,5),(6,6),(9,4)$) and $f(10^2)=3629$.

Find $f(10^7) \bmod 1\,000\,000\,007$.