Задача 333
Особые разложения

Все положительные целые числа можно разложить таким образом, что каждый член такого разложения можно представить в виде 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 <100, таких, что P(q) =1, составляет 233.

Найдите сумму простых чисел q <1000000, таких, чтобы P(q)=1.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net