Сейчас я занимаюсь проблемой 245, но столкнулся с некоторыми проблемами. Я уже проделал над этим некоторую работу, но не чувствую, что сделал какие-то реальные шаги к ее решению. Вот что у меня есть:
Нам нужно найти n=ab с положительными целыми числами a и b. Мы также можем считать gcd(a, b) = 1 без ограничения общности и, таким образом, phi(n) = phi(ab) = phi(a)phi(b).
Мы пытаемся решить:
Следовательно:
В этот момент я подумал, что было бы неплохо увидеть, как эти числа были распределены. Я собрал программу грубой силы, которую использовал для поиска всех (составных) решений до 104:
Главное, как там выглядит не будет слишком много меньше 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.
Эта проблема Эйлера сбивает с толку, если вы не знаете терминов; они лучше определены в # 243: projecteuler.net/index.php?section=problems&id= 243. Glenn 17.05.2009
Вся необходимая информация содержится в ссылке, которую я разместил. Вопрос звучит буквально: найдите сумму всех целых чисел 1‹n‹=10^11, для которых [n-φ(n)]/[n-1] = 1/k для некоторого целого числа k. 17.05.2009
Мне удалось немного выяснить: k должно делить n-1 (получите это из манипулирования вашим самым первым уравнением, чтобы в целочисленном числе был член вроде (n-1)/k). выражение), k не (обязательно) делит phi(n) (контрпримеры в вашем списке грубой силы), и n должно быть нечетным (следовательно, k четным) (легко показать, что (k- 1)n = k phi(n) - 1, рассмотрите это выражение по модулю 2 и запомните/докажите, что phi(n) всегда четно при n > 2). Я не вижу, куда идти дальше, и это все время, которое у меня сейчас есть. kquinn 18.05.2009
Я не думаю, что обсуждение переполнения стека соответствует духу проекта Эйлера;) leif 18.05.2009
Спасибо kquinn. Вы правы насчет k, делящего n-1. Это означало бы, что n = jk+1 = ab для некоторого j. Мне нужно выйти, но я пойду за остальными позже. Спасибо! 18.05.2009
kquinn, второе уравнение должно быть: (k-1)(n-1) = k(phi(n)-1) я думаю. Для n › 2 phi(n) четно (mod 2) (k-1)(n-1) = k → n(k-1) = 1. Чтобы это было правдой, n должно быть нечетным, а k четное. 18.05.2009
Умножьте простые числа. Что я сделал, так это сначала проверил каждый продукт с двумя простыми числами; сохранить те, которые являются успехами. Затем, используя сохраненные продукты, проверьте те, у которых больше простых чисел (каждый продукт с тремя простыми числами, показанный в вашем переборе, имеет подмножество из двух простых чисел, которое работает). Используйте эти сохраненные продукты и повторите попытку с 4 простыми числами, 5 простыми числами и т. д.
Единственным недостатком является то, что вам нужно хорошее сито или список простых чисел.
Project Euler не любит обсуждать проблемы на публичных форумах, таких как StackOverflow. Все задачи сделаны для самостоятельного выполнения, если вы столкнетесь с проблемами, вы можете попросить помощи для конкретной математической или программной концепции, но вы не можете просто решить спросить, как решить стоящую задачу - лишает смысла проект Эйлер.
Суть в том, чтобы учиться и придумывать решения самостоятельно, а также изучать новые концепции.
Ответ 3 · рейтинг 5 · Accipitridae
Позвольте мне продолжить то, что начал кувшин, но попробуйте несколько иной подход. Цель снова состоит в том, чтобы просто найти числа, которые имеют два разных множителя n=pq. Как вы уже заметили, мы ищем такие числа, что n-phi(n) делит n-1. То есть, если n=pq, то это означает, что мы ищем такие p,q, что
p+q-1 divides pq-1
Предположим, что мы фиксируем p и ищем все простые числа q, удовлетворяющие приведенному выше уравнению. Приведенное выше уравнение не выглядит очень простым для решения, поэтому следующим шагом будет максимально возможное устранение q. В частности, мы используем, что если a делит b, то a также делит b + ka для любого целого k. Следовательно
p+q-1 divides pq - 1 - p(p+q-1)
а его упрощение приводит к условию
p+q-1 divides p^2 - p + 1.
Можно предположить, что p - меньший простой множитель числа n. Тогда p меньше квадратного корня из 1011. Следовательно, можно найти все числа с двумя множителями путем перебора всех простых чисел p, меньших квадратного корня из 1011, затем найти делители p^2-p+1, найти q и проверить если q простое число и pq является решением задачи.
Это, конечно, по-прежнему оставляет целые числа с более чем двумя простыми множителями. Здесь тоже работает несколько похожий подход, но он более сложен и требует дальнейшей оптимизации.
Один вопрос, на который я не могу ответить, заключается в том, почему эта проблема сформулирована так сложно. Разве авторы не могли просто запросить сумму составных целых чисел, где n-phi(n) делит n-1. Так что, возможно, мне не хватает большого намека.
Теперь, когда известны решения с двумя простыми множителями, я попытаюсь найти потенциальный алгоритм для поиска решений с более чем двумя простыми множителями. Цель состоит в том, чтобы найти алгоритм, который по заданному составному целому числу m находит все простые числа q, такие что mq является решением. т. е. q должно быть таким, чтобы
mq - phi(mq) divides mq - 1.
Позволять
F = mq - phi(mq).
Тогда конечно
F = (m-phi(m)) q + phi(m).
Как и в случае двух простых множителей, можно найти условие для F, исключив q из левой части приведенного выше уравнения. Поскольку F делит mq-1, оно также делит
(m-phi(m))(mq - 1)
и, следовательно, также
m F - (m-phi(m))(mq - 1) = m phi(m) + m - phi(m).
Таким образом, найдя все делители F числа m phi(m) + m - phi(m) и проверив, является ли (F - phi(m))/(m - phi(m)) простым, можно найти все решения mq для данного m. Поскольку только те дивизоры F, которые удовлетворяют
F == phi(m) (mod m - phi(m))
может привести к новым решениям, этот факт иногда можно использовать для оптимизации факторизации m phi(m) + m - phi(m).
Ответ 4 · рейтинг 1 · Community
Чтобы не отдавать слишком много, я бы предложил две вещи:
Проанализируйте последовательность чисел, которую вы произвели методом грубой силы: все они имеют общую характеристику. Если вы обнаружите, что это такое, у вас может быть шанс найти решение методом грубой силы.
Найдите более сложный алгоритм факторинга. Или еще лучше: вместо того, чтобы находить множители по числам, строить числа по множителям...
РЕДАКТИРОВАТЬ: Образцы, которые вы найдете, только добавят к вашему пониманию и, надеюсь, покажут вам, как вы могли бы достичь такого же объема знаний путем адекватного манипулирования аналитическим выражением. Боюсь, не зная этой закономерности, пути к решению нет. Кроме того, это, вероятно, одна из самых сложных задач Project Euler, поэтому вам не нужно беспокоиться о том, чтобы найти решение без большого труда и пота...
Ответ 5 · рейтинг 1 · Community
прямой помощи в решении этой задачи нет, но может быть интересно для будущих математических проектов: вместо использования WolframAlpha для анализа последовательности я бы рекомендовал "Интерактивная энциклопедия целочисленных последовательностей" на сайте research.att.com.
Получайте удовольствие, решая все задачи Эйлера!
Ответ 6 · kgiannakakis
Я не нашел полного решения, но я хотел бы поделиться своими мыслями. Возможно, кто-то мог бы помочь.
Я считаю, что нужно попытаться свести проблему к
(источник: texify.com)
сложность. Для повышения эффективности поиска можно использовать следующие факты:
Любое решение должно быть нечетным числом
Любое решение должно быть кратно различным простым числам (множители квадратных чисел не допускаются)
Другие указывали на это, и их легко доказать, используя только основные свойства функции totient.
Я начну с анализа всех простых и составных чисел до sqrt(10^11). Это несложная задача, и требуемое время должно быть значительно меньше требуемой 1 минуты. Все решения выше квадратного корня имеют вид:
a*b, where at least one of a,b < sqrt(10^11)
При повторении диапазона 0..sqrt(10^11) я буду искать кратные числа в итерации, которые являются решениями. Я расскажу только о случае умножения числа меньше квадратного корня на одно простое число. Набор решений, который я получу таким образом, будет надмножеством набора решений с двумя простыми факторами. Это все равно не будет полным набором решений, так как не будут найдены решения вида p1p2p3, где p1p2,p2p3,p1p3›sqrt(10^11).
Пусть b - число меньше квадратного корня, а a - простое число для его умножения.
(источник: texify.com)
У нас есть:
(источник: texify.com)
На основании фактов, что
phi(a) = a - 1 and phi(a)*phi(b) = phi(a*b) if a, b coprime
у нас есть
(источник: texify.com)
Часть "по модулю" справа может быть записана как:
(источник: texify.com)
Позвольте мне временно принять это
(источник: texify.com)
Тогда я мог бы решить приведенное выше уравнение для a (m = 1), проверить, что результат является простым, и тогда у меня будет единственное решение, кратное b. Если m не находится в пределах, чтобы быть фактическим по модулю, тогда мне нужно либо решить уравнение для разных значений k:
(источник: texify.com)
(значения k должны быть как-то ограничены) или доказать, что в этом случае будет более высокое значение b ‹ sqrt(10^11), чтобы покрыть это.
Существует особый случай для b простого или b составного и mb = 0. В этом случае:
(источник: texify.com)
Это можно рассчитать. Для b простое число:
(источник: texify.com)
Мне нужно найти простое число a, удовлетворяющее уравнению:
(источник: texify.com)
Например, пусть b=3, phi(b)=2.
Мне нужно решить:
k[3a-2(a-1)] - 6 = 1 => k(a + 2) = 5
Для k = 1, a = 7, простое число (решение) Для всех других значений k приведенное выше уравнение не может быть выполнено.
