0%

Problem 543


Problem 543


Prime-Sum Numbers

Define function P(n,k) = 1 if n can be written as the sum of k prime numbers (with repetitions allowed), and P(n,k) = 0 otherwise.

For example, P(10,2) = 1 because 10 can be written as either 3 + 7 or 5 + 5, but P(11,2) = 0 because no two primes can sum to 11.

Let S(n) be the sum of all P(i,k) over 1 ≤ i,k ≤ n.

For example, S(10) = 20, S(100) = 2402, and S(1000) = 248838.

Let F(k) be the kth Fibonacci number (with F(0) = 0 and F(1) = 1).

Find the sum of all S(F(k)) over 3 ≤ k ≤ 44


素和数

定义函数P(n,k)如下,若n能够写成k个可重复素数的和,则值为1,否则值为0。

例如,P(10,2) = 1因为10可以写成3 + 7或者5 + 5,但是P(11,2) = 0因为不存在两个素数的和为11。

记S(n)是所有满足1 ≤ i,k ≤ n的P(i,k)之和。

例如,S(10) = 20,S(100) = 2402,以及S(1000) = 248838。

记F(k)是第k个斐波那契数(初值为F(0) = 0和F(1) = 1)。

对于所有3 ≤ k ≤ 44,求S(F(k))的和。