Problem 618

Numbers with a given prime factor sum

Consider the numbers 15, 16 and 18:
$15 = 3 \times 5$ and $3 + 5 = 8$ .
$16 = 2 \times 2 \times 2 \times 2$ and $2 + 2 + 2 + 2 = 8$ .
$18 = 2 \times 3 \times 3$ and $2 + 3 + 3 = 8$ .
15, 16 and 18 are the only numbers that have 8 as sum of the prime factors (counted with multiplicity).

We define $S (k)$ to be the sum of all numbers $n$ where the sum of the prime factors (with multiplicity) of $n$ is $k$ .
Hence $S (8) = 15 + 16 + 18 = 49$ .
Other examples: $S (1) = 0$ , $S (2) = 2$ , $S (3) = 3$ , $S (5) = 5 + 6 = 11$ .

The Fibonacci sequence is $F_{1} = 1$ , $F_{2} = 1$ , $F_{3} = 2$ , $F_{4} = 3$ , $F_{5} = 5$ , $\dots$
Find the last nine digits of $\sum_{k = 2}^{24} S (F_{k})$ .

给定质因数和的整数

考虑整数15，16和18的质因数分解：
$15 = 3 \times 5$ ，而 $3 + 5 = 8$ 。
$16 = 2 \times 2 \times 2 \times 2$ ，而 $2 + 2 + 2 + 2 = 8$ 。
$18 = 2 \times 3 \times 3$ ，而 $2 + 3 + 3 = 8$ 。
15，16和18是仅有的质因数和（包括重复）为8的整数。

记 $S (k)$ 为所有质因数和（包括重复）为 $k$ 的整数 $n$ 的和。
因此 $S (8) = 15 + 16 + 18 = 49$ 。
其它例子包括： $S (1) = 0$ ， $S (2) = 2$ ， $S (3) = 3$ ， $S (5) = 5 + 6 = 11$ 。

考虑斐波那契数列 $F_{1} = 1$ ， $F_{2} = 1$ ， $F_{3} = 2$ ， $F_{4} = 3$ ， $F_{5} = 5$ ， $\dots$
求 $\sum_{k = 2}^{24} S (F_{k})$ 的最后九位数字。