Замечательные задачи Эрдёша по теории чисел

Задача 1 "ослабленная Гольдбаха" :

Эрдёш и Мозер( 1959 ) спрашивают :

" существует ли для каждого целого n > 0 два целых числа
a, b, таких, что фи(a) + фи(b) = 2*n. "
( где фи(x) - функция Эйлера, x > 0 целое число. )

Из справедливости гипотезы Гольдбаха следует положительный ответ на задачу Эрдёша !

Возможно ли независимое решение задачи Эрдёша ?

Воспользуемся приближением pi(x) = x/ln x :)

Пусть y >= x, y = kx, k >= 1.
Тогда надо доказать, что

(k+1)x / (ln(k+1) + ln x) <= x / ln x + kx / (ln k + ln x) = x * (ln k + ln x + k ln x) / (ln k + ln x) ln x

Сокращаем на x, переносим знаменатель левой части в числитель правой, а знаменатель правой - в числитель левой, раскрываем скобки, сокращаем и получаем:

k*ln k*ln x <= ln (k+1) * (ln k + ln x + k ln x)
Сиё неравенство очевидно (т.к. в правой части содержится k*ln(k+1)*ln x + ещё что-то).

Естественно, это решение является "решением", потому что особо придирчивых может не устроить приближение pi(x) = x/ln x ;)

pi(4) <= pi(2) + pi(2)
И у меня так же. Нестрогое неравенство сохраняется)

Во-первых, я хотел бы спросить, правильно ли считаю функцию Эйлера. У меня получается Фи(3)=2, Фи(4)=2, Фи(5)=4, Фи(6)=2, Фи(7)=6...
Если правильно, то, во-вторых, хотелось бы узнать, в чем заключается связь гипотезы Гольдбаха и приведенной задачи?

А откуда такой ответ берётся? Из того, что производная функции x/ln убывает? Я понимаю, что ряд простых чисел чем дальше в лес, тем больще разреженный, но строго как доказать?

А вообще, за исключением тривиальных примеров, это открытая проблема, которая носит имя Харди-Литтлвуда (2-я гипотеза Харди-Литтлвуда).

Можно показать, что существует интервал из 3159 последовательных чисел, среди которых имеется 447 чисел не делящихся на простые, непревосходящие 3159. Если окажется верна 1-я гипотеза Харди-Литтлвуда, то найдется отрезок (а точнее бесконечно много отрезков) из 3159 последовательных чисел [n+1,n+3159], содержащий 447 простых. Этот отрезок интересен тем, что пи(3159)=446<447, откуда немедленно следует контрпример ко 2-й гипотезе Харди-Литтвуда:
пи(n+3159)=пи(n)+447 > пи(n)+пи(3159)=пи(n)+446
Таким образом, 1-я гипотеза Харди-Литтлвуда влечет отрицание 2-й их же гипотезы.

Существование требуемого отрезка [n+1,n+3159] пока остается под вопросом - его ищут на http://www.opertech.com/primes/k-tuples.html.

Пусть A - такое множество натуральных чисел, что сумма величин, обратных элементам A, бесконечна. Верно ли, что A содержит сколь угодно длинные арифметические прогрессии?


Задача взята из статьи
М. В. Волков Пол Эрдёш: необычная жизнь и необычайная математика



С уважением,
Борис

Это очень известная задача. Упоминается в "Конкретной Математике". Кроме того, если мне память не изменяет, Рон Грэхем (один из авторов КМ) говорил, что Эрдёш назначил за ее решение определенную сумму (точную цифру не помню). Это денежное предложение должно в силе и по сей день (см. статью про про задачи и чеки от Эрдеша).

Как считать сумму чисел, принадлежащих множеству A? Если A - счётно, тогда это будет, понятно, сумма ряда этих чисел, занумерованных в любом порядке. А как быть с более чем счётным множеством? (не обязательно континуальным :))

И в самом деле %)