Сейчас я занимаюсь проблемой 245, но столкнулся с некоторыми проблемами. Я уже проделал над этим некоторую работу, но не чувствую, что сделал какие-то реальные шаги к ее решению. Вот что у меня есть:
Нам нужно найти n=ab с положительными целыми числами a и b. Мы также можем считать gcd(a, b) = 1 без ограничения общности и, таким образом, phi(n) = phi(ab) = phi(a)phi(b).
Мы пытаемся решить:
Следовательно:
В этот момент я подумал, что было бы неплохо увидеть, как эти числа были распределены. Я собрал программу грубой силы, которую использовал для поиска всех (составных) решений до 104:
15, 85, 255, 259, 391, 589, 1111, 3193, 4171, 4369, 12361, 17473, 21845, 25429, 28243, 47989, 52537, 65535, 65641, 68377, 83767, 91759
Главное, как там выглядит не будет слишком много меньше 1011 ограничения, указанного в задаче. Самое интересное/полезное, что я обнаружил, заключалось в том, что k было довольно мало даже для больших значений n. На самом деле самое большое k было всего 138. (Кроме того, кажется, что k всегда четно.)
Учитывая это, я предполагаю, что можно рассмотреть каждое значение k и найти, какое значение (значения) n может быть с этим значением k.
Возвращаясь к исходному уравнению, обратите внимание, что его можно переписать как:
Поскольку мы знаем к:
И это все, что у меня есть; Я все еще преследую некоторые из своих маршрутов, но мне интересно, не упускаю ли я смысл! С помощью грубой силы я нашел сумму до 108, что составляет 5699973227 (всего 237 решений для n).
У меня почти закончились идеи; может кто подскажет?
Обновление: много людей проделали большую работу, и вместе мы смогли доказать несколько вещей. Вот список:
n всегда нечетно, а k всегда четно. k ‹= 105,5. n не должно быть квадратным.
Я нашел все решения, когда n=pq (2 простых множителя) с p>q. Я использовал тот факт, что для двух простых чисел q = k+factor(k^2-k+1) и p = k+[k^2-k+1]/factor(k^2-k+1). Мы также знаем для 2 простых чисел k ‹ q ‹ 2k.
Для n с двумя или более простыми делителями все простые числа n больше k.
