задачка Эрдеша с продолжением
Назовем (p,q)-числами натуральные числа, у которых нет других простых делителей, кроме p и q.

Задачка. [см.]
Доказать, что любое натуральное число можно представить в виде суммы различных (2,3)-чисел, из которых ни одно не делится на другое.

Решение советую поискать самим: несложное и изящное; удовольствие, если найдете, обеспечено.

Продолжение задачки.
Для каких p,q любое достаточно большое натуральное число можно представить в виде суммы различных (p,q)-чисел, из которых ни одно не делится на другое?

Полного решения я не знаю, но после артподготовки остаются лишь отдельные очаги сопротивления.

Пусть p > q. Обозначим L=log_q(p).
Возьмем большое число N, и оценим, сколько есть подходящих сумм, меньших p^N. Ясно, что если их окажется сильно меньше, чем p^N, то пара (p,q) не подходит.
Какие числа можно использовать? Только вида p^aq^b, причем a < N и
b <= [LN] (на самом деле даже a+b/L < N, но это оставим на случай, если грубого подхода не хватит).
Далее: каждое значение показателя a встречается в сумме не более раза, и соответствующие показатели b уменьшаются с ростом a. Теперь нетрудно увидеть (кто не знает, как - хорошее упражнение), что подходящих сумм не более числа сочетаний из [LN]+1+N по N. При больших N это ведет себя как экспонента: x^N, и значение x легко сосчитать:
x=(1+L)(1+1/L)^L.
Значит, если окажется, что x < p, то пара (p,q) не подходит.
Поупражнявшись с калькулятором, обнаруживаем, что остается совсем немножко вариантов:
(2,3) (2,5) (2,7) (2,11) (3,5) (3,7)
(если я не напутал).

И напоследок - совсем простая задачка: доказать, что (2,7) не годится.