Решение в цели числа

[peyo]

Търся решения на следното уравнение в цели положителни числа:

$ 528440 \cdot x + 375241 = (220 \cdot 10^y + 91 )^2 $

За y до 100,000 няма решения и след това търсенето се забавя. Ще мога да проверя до 1,000,000 на моя компютър предполагам, но си мислех има ли по-лесен/бърз начин?

[ptj]

По принцип има : динамично решето по списък от модули.

Преди много години реших една друга подобна задача: търсеха се всички точни квадрати измежду числата на Фибоначи. Условието бе да се проверят номера до 1000000 (в реално време).
Програмата ми на Intel286 за 13 секунди доказваше, че единственото такова число е 144.

П.П. Въпроса е доколко е важно това за теб, защото реализирането на алгоритъма не е много лесно.

[peyo]

По принцип има : динамично решето по списък от модули.

Преди много години реших една друга подобна задача: търсеха се всички точни квадрати измежду числата на Фибоначи. Условието бе да се проверят номера до 1000000 (в реално време).
Програмата ми на Intel286 за 13 секунди доказваше, че единственото такова число е 144.

П.П. Въпроса е доколко е важно това за теб, защото реализирането на алгоритъма не е много лесно.

Не е кой знае колко важно, но ми е забавно, защото е свързано е с този проблем:
https://research.ibm.com/haifa/ponderthis/challenges/October2023.html

Днес наех един евтин virtual server с 4 процесора и го пуснах да търси и ще го оствавя цял ден да видя какво ще направи. Но още в началото виждам, че проверката става много бавна за по-големите числа и няма да стигна близо то милион.

Какво е динамично решето по списък от модули? Има ли някъде примерeн проблем решен да го разгледам?

[pal702004]

Търся решения на следното уравнение в цели положителни числа:

$ 528440 \cdot x + 375241 = (220 \cdot 10^y + 91 )^2 $

За y до 100,000 няма решения и след това търсенето се забавя. Ще мога да проверя до 1,000,000 на моя компютър предполагам, но си мислех има ли по-лесен/бърз начин?

Разбира се че има.
Първо решаваме уравнението
$ 528440x + 375241 = (220 z+ 91 )^2 $

Получаваме две серии решения за $z$:
$z=1201 n+731$
$z=1201 n+1026$

Сега проверяваме (може и на Excel на компютърчето) за решения
$10^y\equiv 731 \pmod{1201}$

$10^y\equiv 1026 \pmod{1201}$

и виждаме че няма решения.

[peyo]

Сега проверяваме (може и на Excel на компютърчето) за решения
$10^y\equiv 731 \pmod{1201}$

$10^y\equiv 1026 \pmod{1201}$

и виждаме че няма решения.

Това не го разбрах. Защо няма решения? Няма решения за малки числа или въобще няма?

[ptj]

По принцип има : динамично решето по списък от модули.

Преди много години реших една друга подобна задача: търсеха се всички точни квадрати измежду числата на Фибоначи. Условието бе да се проверят номера до 1000000 (в реално време).
Програмата ми на Intel286 за 13 секунди доказваше, че единственото такова число е 144.

П.П. Въпроса е доколко е важно това за теб, защото реализирането на алгоритъма не е много лесно.

Не е кой знае колко важно, но ми е забавно, защото е свързано е с този проблем:
https://research.ibm.com/haifa/ponderthis/challenges/October2023.html

Днес наех един евтин virtual server с 4 процесора и го пуснах да търси и ще го оствавя цял ден да видя какво ще направи. Но още в началото виждам, че проверката става много бавна за по-големите числа и няма да стигна близо то милион.

Какво е динамично решето по списък от модули? Има ли някъде примерeн проблем решен да го разгледам?

Ако си в БГ е лесно. Трябва ти голяма библиотека (като "Иван Вазов" в Пловдив). Търси по каталог списание "Компютър за вас" броевете от 1988 или 1989 година. На времето Емил Келеведжиев водеше един задочен конкурс. Спомената задача е от него, а в някой от следващите броеве има моето решение (доколкото си спомням на Си++). Обяснена е и цялата идея за динамично решето.

[pal702004]

Това не го разбрах. Защо няма решения? Няма решения за малки числа или въобще няма?

И за малки, и въобще. Степените на 10 по модул 1201 са циклични (по принцип на всяко число по всеки модул). В случая са цилични с цикъл 200.

$10^0 \equiv 1 \pmod {1201}$

$10^{200} \equiv 1 \pmod {1201}$

Тоест, степените на 10 имат точно 200 различни остатъка при делене на 1201. И търсените два не са между тях.

Може в Excel Да се провери. В клетка A1 пишем 10. В клетка B1 пишем =MOD(10*A1,1201). Копираме формулата от B1 в колона B (не цялата, разбира се, до B201 е достатъчно). И виждаме всички остатъци на степените на 10 при делене на 1201.

[peyo]

Това не го разбрах. Защо няма решения? Няма решения за малки числа или въобще няма?

И за малки, и въобще. Степените на 10 по модул 1201 са циклични (по принцип на всяко число по всеки модул). В случая са цилични с цикъл 200.

$10^0 \equiv 1 \pmod {1201}$

$10^{200} \equiv 1 \pmod {1201}$

Тоест, степените на 10 имат точно 200 различни остатъка при делене на 1201. И търсените два не са между тях.

Може в Excel Да се провери. В клетка A1 пишем 10. В клетка B1 пишем =MOD(10*A1,1201). Копираме формулата от B1 в колона B (не цялата, разбира се, до B201 е достатъчно). И виждаме всички остатъци на степените на 10 при делене на 1201.

Аха! Мерси, сега става много по-ясно.

Добре това уравнение не доведе до решение, но има друг подход, който се оказа добър и намерих решение на първия въпрос на задачата от ponderthis. Втория въпрос е още под въпрос.