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

[daniel starodubtsev]

$n$-ный член последовательности - наименьший простой палиндром $p$, такой, что $n+p=y^2$ для целого $y$.

Начало последовательности (первые 50 членов):
$3, 2, ?, 5, 11, 3, 2, 353, 7, ?, 5, ?, 3, 2, 181, ?, 383, 7, ?, 5, ?, 3, 2, 7392937, 11, 38783, 373, 1289830389821, 7, ?, 5, $$, 929, 3, 2, 1245421, ?, ?, 11, ?, 1461641, 95042724059, 7, 101, 5, 151, 3, 2, 313, ?, ?$

Все члены последовательности, обозначенные знаком вопроса, превышают $5 \cdot 10^1^4$. Кто-нибудь поможет их найти?

[Dmitriy40]

Я Вас наверное огорчу: для всех $n \in \{3, 10, 12, 16, 19, 21, 30, 36, 37, 39, 49, 50, 51, 52, 56, 64, 66, 67, 69, 71, 81, 82, 83, 96, 99, 100\}$ как минимум $p>10^{16}$.
Для остальных $n<100:\q p<10^{10}$, за исключением:
$28+1289830389821=1135707^2$
$41+95042724059=308290^2$
$55+183499696994381=13546206^2$
$60+1418240428141=1190899^2$
$86+323663595366323=17990653^2$

[Dmitriy40]

Найдены ещё пара решений:
$3+1219261354531629121=1104201682^2$
$30+11490066766009411=107191729^2$
$69+78035565456553087=279348466^2$
Для остальных $n\le100:p>10^{19}$.

[daniel starodubtsev]

Dmitriy40
Спасибо!

Если $n=z^2$ является квадратом числа, то тогда $p=y^2 - z^2 = (y-z)(y+z)$, а значит может быть простым только если $y-z=1$. таким образом члены под номерами 16, 36, 49, 64, 81, 100 можно обозначить как $\infty$.
Остается найти члены номер 10, 12, 19, 21, 37, 39, 50, 51, 52, 56, 66, 67, 71, 82, 83, 96, 99. (из тех, что до ста)

[Dmitriy40]

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

Если $n=z^2$ является квадратом числа, то тогда $p=y^2 - z^2 = (y-z)(y+z)$, а значит может быть простым только если $y-z=1$. таким образом члены под номерами 16, 36, 49, 64, 81, 100 можно обозначить как $\infty$.

Хм, а ведь точно, это можно проверить легко и быстро. Для $n=z^2<10^6$ находятся лишь эти:
$1+3=2^2$
$4+5=3^2$
$9+7=4^2$
$25+11=6^2$
$2500+101=51^2$
$4225+131=66^2$
$5625+151=76^2$
$8100+181=91^2$
$9025+191=96^2$
$24336+313=157^2$
$30976+353=177^2$
$34596+373=187^2$
$36481+383=192^2$
$131769+727=364^2$
$142884+757=379^2$
$154449+787=394^2$
$158404+797=399^2$
$210681+919=460^2$
$215296+929=465^2$

Я тут вчера вечером написал на асме x64 перебор по $y$ для диапазона $p\le10^{19}$, каждый такой перебор (для фиксированного $n$) занимал 25с плюс полуручная проверка на простоту, собственно ночные результаты это оно и есть, а сегодня на свежую голову подумал что перебирать прям уж все $y$ и вовсе не надо, можно идти очень крупными шагами, типа по миллиарду, ведь условие палиндромичности очень жёсткое и можно сразу получать единственный возможный $n$. Вот сейчас напишу программульку и посмотрим что она найдёт.

[Dmitriy40]

Написал, проверил, работает. На PARI/GP выигрыш действительно в разы. Заодно где-то за час она подтвердила все ночные результаты (для всех $p<10^{20}$).
А вот на асм выигрыша незаметно, на 9 чисел проще сделать 18 делений с проверкой на палиндром чем 11 извлечений квадратного корня и 1 обращение цифр.
Чуть доработав прогу на асме (для поддержки чисел $10^{19}..10^{25}$) запустил её считать и она выдала ещё результаты:
$83+161073063979360370161=12691456338^2$
$41+387360350636053063783=19681472268^2$
Скорость перебора примерно 70 млрд значений $y$ в час, $n$ не перебираются, они сразу все находятся.

[daniel starodubtsev]

А можно узнать код на PARI/GP? Мне такой скорости с моими навыками программирования достичь не удастся...

P.S. Для 41 можно гораздо меньше: $41 + 95042724059 = 308290^2$

[kotenok gav]

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

Для 41 можно гораздо меньше: $41 + 95042724059 = 308290^2$

Dmitriy40 в сообщении #1364629 писал(а):

$41+95042724059=308290^2$

[daniel starodubtsev]

Цитата:

$41+387360350636053063783=19681472268^2$

[kotenok gav]

Так я говорю, что он написал еще раньше.

[DanilovV]

Dmitriy40 в сообщении #1364652 писал(а):

Найдены ещё пара решений:
$3+1219261354531629121=1104201682^2$

Можно и в OEIS загнать

[Dmitriy40]

Да, про $n=41$ я недосмотрел что уже было (я оставлял некоторые уже решённые $n$ в программе для контроля).

Код на PARI/GP медленный, вот пример проверки диапазона $p=10^{9}..10^{13}$:

? nn=[3, 10, 12, 19, 21, 28, 30, 37, 39, 41, 50, 51, 52, 55, 56, 60, 66, 67, 69, 71, 82, 83, 86, 96, 99];
? t(p)={ my(n,y); y=ceil(sqrt(p)); n=y^2-p; if(n<100 && vecsearch(nn,n) && ispseudoprime(p), printf("%d+%d=%d^2\n", n,p,y)); }
? for(i=10^4,10^6, d=digits(i); r=fromdigits(Vecrev(d)); t(i*10^#d+r); m=i*10^#d*10+r; forstep(k=0,9*10^#d, 10^#d, t(m+k)); );
41+95042724059=308290^2
28+1289830389821=1135707^2
60+1418240428141=1190899^2
time = 57,191 ms.

Или примерно 200 млн значений $y$ в час.
Почему мне показалось что примерно за час досчиталось до $y=1104201682, n=3$ - не знаю, похоже ошибся, наверное про час это лишь до $y=279348466, n=69$.

-- 30.12.2018, 21:11 --

Что-то я запутался, похоже код выше наоборот медленнее старого доброго перебора $y$:

? n=3; forstep(y=110*10^7,111*10^7,2, p=y^2-n; if(!ispseudoprime(p), next); d=digits(p); if(d==Vecrev(d), printf("%d+%d=%d^2\n", n,p,y)));
3+1219261354531629121=1104201682^2
time = 15,116 ms.

Тут скорость порядка 2.4 млрд значений $y$ в час. Зато проверяется только один вариант $n$.

[Dmitriy40]

Переписал асм прогу, отказался от обоих делений (на каждое $y$), оставил лишь одно умножение и простые операции. Ускорилось на порядок, за час работы догнала и перегнала работающий с 15ч предыдущий вариант.
И даже уже нашла новое решение:
$12+3126605100926290015066213=1768220885785^2$
До $p<10^{25}$ больше решений не найдено.

[daniel starodubtsev]

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

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

[daniel starodubtsev]

Dmitriy40 в сообщении #1364715 писал(а):

$1+3=2^2$
$4+5=3^2$
$9+7=4^2$
$25+11=6^2$
$2500+101=51^2$
$4225+131=66^2$
$5625+151=76^2$
$8100+181=91^2$
$9025+191=96^2$
$24336+313=157^2$
$30976+353=177^2$
$34596+373=187^2$
$36481+383=192^2$
$131769+727=364^2$
$142884+757=379^2$
$154449+787=394^2$
$158404+797=399^2$
$210681+919=460^2$
$215296+929=465^2$

Вот это наверное следует добавить в OEIS. Я имею в виду такие $n$, что $2n + 1$ - простой палиндром