RSS Feed

특수한 분할

Problem 333

출제 일시 : 2021-06-03 00:05:02

모든 양의 정수는 각 항이 2ix3j (i,j ≥ 0)인 형태로 분할할 수 있습니다.

어떠한 항도 다른 항으로 나뉘지 않는 분할을 유효하다고 합시다.
예를 들어, 다음 분할 17 = 2 + 6 + 9 = (21x30 + 21x31 + 20x32)은 6이 2로 나뉘기 때문에 유효하지 않습니다. 또 다른 분할 17 = 16 + 1 = (24x30 + 20x30)도 마찬가지로 16이 1로 나뉘기 때문에 유효하지 않습니다. 17의 분할 중 유효한 것은 8 + 9 = (23x30 + 20x32) 하나 뿐입니다.

많은 정수의 유효한 분할이 복수개고, 그 첫 정수는 11로 다음 두 개의 분할이 유효합니다.
11 = 2 + 9 = (21x30 + 20x32)
11 = 8 + 3 = (23x30 + 20x31)

P(n)를 정수 n의 유효한 분할의 수로 정의합니다. 예를 들어, P(11) = 2 입니다.

P(17)처럼 단 하나의 유효한 분할을 가지는 소수 q를 생각해 봅시다.

P(q)=1인 소수 q <100의 합은 233입니다.

P(q)=1인 소수 q <1000000의 합을 구하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.