Последовательность с большими числами

[Dmitriy40]

daniel starodubtsev в сообщении #1365080 писал(а):

Если $p > 10^2^5$, то $p > 10^2^6$, поскольку любой палиндром, содержащий четное число цифр делится на 11

Хм, не знал, это ж позволяет втрое ускорить проверку.

daniel starodubtsev в сообщении #1365080 писал(а):

P.S. Нашел еще интересный пример: $117 + 78078720702787087 = 279425698^2$

Добавлю ещё для $n<200,\;y>10^6$:
$150+1184355534811=1088281^2$
$115+1234778774321=1111206^2$
$192+3384661664833=1839745^2$
$152+7142721272417=2672587^2$
$177+7480400040847=2735032^2$
$163+121149161941121=11006778^2$
$153+13597467176479531=116608178^2$
$184+14827520102572841=121768305^2$
$187+31410487078401413=177230040^2$
$178+36848614341684863=191959929^2$
$102+93591709290719539=305927621^2$
$112+7546612456542166457=2747109837^2$
$183+121469394292493964121=11021315452^2$
$145+131431076181670134131=11464339326^2$
$129+179930084363480039971=13413802010^2$

[Dmitriy40]

Переписал внутренний цикл перебора на любимом AVX2 (ради чего собственно всё и затевалось), ускорение почти два порядка, теперь при фиксированном $n$ (что позволяет практически вдвое ускорить перебор) скорость составляет $12\text{ч}$ до $p<10^{30}\Leftrightarrow y<10^{15}$ (и $120\text{ч}$ до $p<10^{32}\Leftrightarrow y<10^{16}$). Запустил для младших до сих пор не найденных $n=10,19,21$, ждём-с.

daniel starodubtsev
Походу крупно не повезло Вам с числом $n=10$ (и с остальными двумя), до $p<10^{30}\Leftrightarrow y<10^{15}$ решений не нашлось. Оставил пока считаться дальше.

[Dmitriy40]

За ночь найдено лишь одно интересное решение:
$56+359937041639919936140739953=18972006790003^2$

[Dmitriy40]

Оказалось что для фиксированного $n$ можно ещё сильно ускорить перебор исключив сразу все точно неподходящие $y$, не дающие в квадрате в младших цифрах нужного значения (получаемого из старших цифр квадрата). Переписанный код (даже AVX не понадобилось) вместо ~500 суток до $y<10^{18}$ проверил все числа $10^{17}<y<10^{18}$ (только для $n=10,19,21$) всего за 3ч!

Думаю пора подвести некоторые итоги.
Для $n<130$ все найденные решения для $y<2^{64}\approx 1{,}8\cdot10^{19}$ соберу вместе ($y<10^4$ не привожу за тривиальностью):

85+911919119=30198^2
41+95042724059=308290^2
28+1289830389821=1135707^2
60+1418240428141=1190899^2
55+183499696994381=13546206^2
86+323663595366323=17990653^2
30+11490066766009411=107191729^2
69+78035565456553087=279348466^2
 3+1219261354531629121=1104201682^2
83+161073063979360370161=12691456338^2
12+3126605100926290015066213=1768220885785^2
56+359937041639919936140739953=18972006790003^2
66+32054389246986119391168964298345023=179037396224884033^2

Приведу также и все решения для $100<n<1000,\;y<10^{16}$ ($y<10^4$ снова опущены):

Используется синтаксис Text

911+9851655695724046404275965561589=3138734728473250^2
857+7677034917439134319347194307767=2770746274460932^2
837+7653140133057604067503310413567=2766430937698898^2
699+7367724481943077703491844277637=2714355260820344^2
664+1650992516894293924986152990561=1284909536463285^2
420+1629630168892425242988610369261=1276569688224041^2
805+1179394189741330331479814939711=1085999166547254^2
491+35526198660588588506689162553=188483948018362^2
698+30700153006423832460035100703=175214591305701^2
744+18469515211650105611251596481=135902594572915^2
688+18446083549593239594538064481=135816359653737^2
205+11052066628538483582666025011=105128809698096^2
934+762835559929888929955538267=27619477908351^2
796+371667810300101003018766173=19278687981813^2
243+371243600951393159006342173=19267682812196^2
741+349035988397747793889530943=18682504874822^2
258+324952003002070200300259423=18026425130959^2
244+189778237975060579732877981=13776002249385^2
595+162572026472505274620275261=12750373581684^2
198+152779071142464241170977251=12360383130893^2
520+144802309666939666903208441=12033383134719^2
989+114535525629373926525535411=10702127154420^2
136+9801888702856582078881089=3130796815965^2
992+9611940580894980850491169=3100312981119^2
662+7416502883547453882056147=2723325702803^2
208+3513541176932396711453153=1874444231481^2
486+3409168189580859818619043=1846393292227^2
705+1998832729610169272388991=1413800809736^2
104+1255288932814182398825521=1120396774725^2
979+75750856373737365805757=275228734644^2
521+38858780754545708785883=197126306602^2
456+37498600554145500689473=193645553923^2
381+36683643272627234638663=191529745138^2
916+35846903243734230964853=189332784387^2
811+35690193751015739109653=188918484408^2
951+33037061022122016073033=181760999728^2
918+32931189149394198113923=181469526779^2
261+32313395392529359331323=179759270672^2
541+32170123993039932107123=179360318892^2
406+30204419210101291440203=173794186353^2
858+19721170874647807112791=140432086343^2
255+18068861049494016886081=134420463656^2
963+16967781807470818776961=130260438382^2
759+14391155800800855119341=119963143510^2
995+12703158331313385130721=112708288654^2
304+12303136850105863130321=110919506175^2
577+975402877828778204579=31231440534^2
746+972394279464972493279=31183237155^2
567+965085075595570580569=31065818444^2
355+909833341393143338909=30163443792^2
599+792683181202181386297=28154629836^2
552+376967114858411769673=19415640985^2
957+346422916797619224643=18612439840^2
534+190550876363678055091=13804016675^2
129+179930084363480039971=13413802010^2
433+158252719666917252851=12579853722^2
684+145302319707913203541=12054141185^2
145+131431076181670134131=11464339326^2
183+121469394292493964121=11021315452^2
636+9859197989897919589=3139935985^2
627+9664220641460224669=3108732964^2
455+9478795144415978749=3078765198^2
874+7821657474747561287=2796722631^2
112+7546612456542166457=2747109837^2
621+3858110325230118583=1964207302^2
713+3822591525251952283=1955144886^2
512+3172890340430982713=1781260885^2
336+3135667676767665313=1770781657^2
978+1769517421247159671=1330232093^2
945+1534354065604534351=1238690464^2
708+1496728130318276941=1223408407^2
594+1343938013108393431=1159283405^2
742+99227564746572299=315004071^2
211+98107094149070189=313220520^2
351+94212752925721249=306940960^2
102+93591709290719539=305927621^2
117+78078720702787087=279425698^2
859+75348550305584357=274496904^2
756+39647835753874693=199117643^2
178+36848614341684863=191959929^2
201+36554014541045563=191191042^2
658+34798645654689743=186543951^2
187+31410487078401413=177230040^2
616+31133112221133113=176445777^2
821+30954854745845903=175939918^2
334+19811008680011891=140751585^2
184+14827520102572841=121768305^2
153+13597467176479531=116608178^2
993+13029530303592031=114146968^2
723+10112870307821101=100562768^2
462+977464020464779=31264421^2
615+964169444961469=31051078^2
960+940020454020049=30659753^2
352+771701898107177=27779523^2
822+766795191597667=27691067^2
374+743376898673347=27264939^2
867+711994656499117=26683228^2
876+394788565887493=19869287^2
721+388440818044883=19708902^2
217+383758696857383=19589760^2
236+375819050918573=19386053^2
748+337927666729733=18382809^2
816+334005121500433=18275807^2
643+316929575929613=17802516^2
487+314256101652413=17727270^2
309+195841272148591=13994330^2
829+170842414248071=13070670^2
675+162117676711261=12732544^2
523+160977020779061=12687672^2
530+159935454539951=12646559^2
268+149718545817941=12235953^2
645+136379747973631=11678174^2
453+136377505773631=11678078^2
163+121149161941121=11006778^2
778+117398676893711=10835067^2
656+9637578757369=3104445^2
177+7480400040847=2735032^2
152+7142721272417=2672587^2
932+3927788877293=1981865^2
791+3911408041193=1977728^2
672+3530246420353=1878895^2
226+3473329233743=1863687^2
192+3384661664833=1839745^2
976+3343971793433=1828653^2
533+1963731373691=1401332^2
819+1859077709581=1363480^2
903+1611650561161=1269508^2
849+1578440448751=1256360^2
704+1299201029921=1139825^2
715+1280844480821=1131744^2
115+1234778774321=1111206^2
483+1213518153121=1101598^2
150+1184355534811=1088281^2
611+98771917789=314280^2
925+97501310579=312252^2
997+97235453279=311826^2
846+97160006179=311705^2
161+93220302239=305320^2
725+91498989419=302488^2
516+90742524709=301235^2
974+74332023347=272639^2
314+70018981007=264611^2
826+36277677263=190467^2
186+36249494263=190393^2
581+34422122443=185532^2
971+33985658933=184352^2
866+32604440623=180567^2
461+32443934423=180122^2
987+31113431113=176390^2
554+17412121471=131955^2
229+17226562271=131250^2
693+17202420271=131158^2
964+16699099661=129225^2
480+16594849561=128821^2
680+14087078041=118689^2
285+13946664931=118096^2
905+13364746331=115606^2
703+10272227201=101352^2
380+989919989=31463^2
640+984515489=31377^2
750+977999779=31273^2
202+972878279=31191^2
980+960565069=30993^2
365+933424339=30552^2
281+916272619=30270^2
279+790959097=28124^2
824+758505857=27541^2
432+391050193=19775^2
942+380444083=19505^2
427+376747673=19410^2
936+376242673=19397^2
861+369868963=19232^2
753+364656463=19096^2
562+360050063=18975^2
771+356000653=18868^2
691+339737933=18432^2
941+327898723=18108^2
677+323999323=18000^2
743+318050813=17834^2
561+308282803=17558^2
446+306494603=17507^2
888+186676681=13663^2
644+183737381=13555^2
513+174979471=13228^2
435+162919261=12764^2
478+150626051=12273^2
585+133494331=11554^2
135+126202621=11234^2
915+121131121=11006^2
508+120494021=10977^2
410+111070111=10539^2
295+107868701=10386^2
228+105616501=10277^2
120+102232201=10111^2
408+102070201=10103^2
940+101424101=10071^2

(Ну и небольшой бонус к наступившему году - обратите внимание на величину решения для $n=2019$ )

2030+1988891=1411^2
2028+181=47^2
2026+3812183=1953^2
2024+1008001=1005^2
2022+3=45^2
2021+34843=192^2
2020+5=45^2
2019+1857693429615169243967581=1362972277640^2
2018+7=45^2
2015+101=46^2
2014+11=45^2
2013+19891=148^2
2012+797=53^2
2010+95959=313^2
2009+7472747=2734^2
2008+370263540101045362073=19242233241^2
2007+3997993=2000^2
2006+91019=305^2
2002+740497624090426794047=27212085993^2
2000+1489549459841=1220471^2
1000+1489841=1221^2

[daniel starodubtsev]

Dmitriy40, спасибо Вам огромное за Вашу помощь! Мне очень приятно, что Вы нашли время и помогли мне с этой проблемой.

[Dmitriy40]

daniel starodubtsev
Завершилась проверка всех $n<130$ до $y<2^{64}$, нашлось одно новое решение с $n=66$.
Также досчитались $n<1000$ до $y<10^{16}$, нашлись $n=805, 420, 664, 699, 837, 857, 911$.
Всё найденное добавил в таблицы выше, поправив достигнутые пределы.
Список так и не найденных решений: $n=10, 19, 21, 37, 39, 50, 51, 52, 67, 71, 82, 96, 99, 106, 130, 132, 147$ и далее всё больше и больше.

На этом эпопею считаю завершённой и счёт останавливаю, слишком уж он медленно дальше продвигается: оценка времени счёта $y=10^{16}\ldots10^{17}$ более месяца (в одном потоке); проверка одного конкретного $n$ в диапазоне $y=10^{16}\ldots2^{64}\approx1{,}84\cdot10^{19}$ занимает до полутора суток; мыслей по дальнейшей оптимизации вычислений не осталось (несколько проверенных ускорения не дают); выходить за предел $y>2^{64}$ (хотя бы ради $n=10$) огромный гемор (переписывать без малого всё) и никакого желания нет. Впрочем, если появятся новые мысли, продолжения не исключаю.