PARI/GP в поиске квадратов с красивыми хвостами.

[gris]

Вот порекомендовали интересную задачу. Первоисточник у Raingirl Ann.
Доказать, что существует бесконечное число натуральных чисел, квадрат которых заканчивается на сколь угодное количество повторяющихся пар. Например:

$$4466388009895478^2 = 19948621854938088484848484848484$$

Я попробовал потеоретизировать и даже написал формальное условие.

$$\exists m\in [1,99]:\quad \forall n \exists k:\quad k^2 \mod 100^n=(100^n-1)/99\cdot m$$

Кроме тривиального повтора нулей, легко найти повторы нескольких пар.
Но бывает, что у пары бывает три повтора, а четыре уже никак.
Приходится делать перебор. Вот число повторов и подходящие пары.
1 [01, 04, 09, 16, 21, 24, 25, 29, 36,
41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96]
2 [04 16, 21, 29, 36, 61, 64, 69, 84, 96]
3 [16, 21, 29, 61, 64, 69, 84]
4 [21, 29, 61, 64, 69, 84]
5 [21, 29, 61, 69, 84]
Дальше уже перебирать сложно.
Для каждой пары-кандидата определим двузначные окончания
чисел, дающих эту пары.
21 [11, 39, 61, 89]
29 [23, 27, 73, 77]
61 [19, 31, 69, 81]
69 [13, 37, 63, 87]
84 [22, 78]
И дальше основная программа. Для каждой пары формируем четыре потока начиная с вектора окончаний и последовательно очень экономным перебором
увеличиваем продвижение вдаль. Есть и нюансы. Но получить число, у квадрата которого 1000 повторений пары, можно за 12 секунд.
Конечно, для бытового применения вполне нормально, но это не решает проблему существования для любого количества пар.
Некто посоветовал использовать КТО, но я не знаю — как?
Что делать? С чего начать? Кто виноват?
Извечные вопросы.

{m=21; nm=4;
ww=[11, 39, 61, 89];
wi=vector(nm);
forstep( n=2,2000,2,
  r=(10^(n+2)-1)\99*m; 
  for( nrem=1,nm,
    rem=ww[nrem]; 
    forstep(i=rem,10^400,10^(n-2), 
      if(i^2%(10^(n+2))==r,
         ww[nrem]=i%(10^n);wi[nrem]=i;break);
    )); 
);    print(m, " 1001: ",wi);\\ print(n," ",ww);
}

+++ поправил $...k^2 \mod 10^n=...$ на $...k^2 \mod 100^n=...$

[Dmitriy40]

Интересно что начиная с 5 пар варианты больше не меняются, так и остаются [21, 29, 61, 69, 84], и их дают ровно 48 остатков по соответствующему модулю, и хотя остатки и меняются, но их так и остаётся всегда ровно 48, вплоть до 4000 пар.

[wrest]

gris в сообщении #1692238 писал(а):

Но получить число, у квадрата которого 1000 повторений пары, можно за 12 секунд.

Ну можно и быстрее.

\\ Функция для вычисления числа, квадрат которого заканчивается на k пар "21"
n_k(k) = {
    my(n, M, b_prev, c, a_coeff_mod, d, m1, c1, a1, inv, a0, solutions, a_val, n_new, M_next, b_new, found);
    \\ Базовый случай: k = 1
    n = 11;
    if(k == 1, return(n));
    
    for(i = 2, k,
        \\ Вычисление M = 10^{2(i-1)}
        M = 10^(2*(i-1));
        \\ b_prev = floor(n^2 / M)
        b_prev = n^2 \ M;
        \\ c = (21 - b_prev) mod 100
        c = (21 - b_prev) % 100;
        \\ Коэффициент для уравнения: 2*n mod 100
        a_coeff_mod = (2 * n) % 100;
        \\ Находим НОД коэффициента и модуля
        d = gcd(a_coeff_mod, 100);
        \\ Проверка разрешимости
        if(c % d != 0,
            error("No solution for k=", i, ": ", a_coeff_mod, "a ≡ ", c, " mod 100")
        );
        \\ Приведение уравнения
        m1 = 100 \ d;
        c1 = c \ d;
        a1 = a_coeff_mod \ d;
        \\ Обратный элемент для a1 по модулю m1
        inv = lift(Mod(a1, m1)^(-1));
        a0 = (inv * c1) % m1;
        \\ Все решения уравнения
        solutions = vector(d, j, a0 + (j-1)*m1);
        found = 0;
        \\ Перебор решений для нахождения подходящего a
        for(j = 1, #solutions,
            a_val = solutions[j];
            n_new = n + a_val * M;
            M_next = 100 * M;  \\ 10^{2i}
            b_new = n_new^2 \ M_next;
            \\ Проверка, что b_new нечетное (условие для следующей итерации)
            if(b_new % 2 == 1,
                n = n_new;
                found = 1;
                break
            )
        );
        if(!found, error("No solution with odd b_new for k=", i))
    );
    return(n);
}

Написано искусственным интеллектом, работает норм. Число, которое при возведении в квадрат даёт 10 тыс. пар "21", считает за 4 секунды.
Результат для 10 пар:

? n=n_k(10);print(n," ",n*n)
55908536764491146011 3125764483146458101321212121212121212121
time = 1 ms.
?

[Geen]

gris в сообщении #1692238 писал(а):

даже написал формальное условие

Кажется, не совсем верно: для любого $n$ должно быть в начале.
И почему основание именно $10$?...

[gris]

Спасибо! Надо обдумать. Но как же быть с доказательством? Впрочем, мне достаточно и сотни пар.
Geen, это моя неточность в условии задачи. Там было задано конкретное число 21. Я подумал, а что, если бы не было задано? Но требовалось именно для него определить повторения.
Задание $\forall n \exists m...$ именно для основания 10 мне кажется более слабым, но наверняка количество решений в виде последовательности \{a_n\}, в которой каждый член $a_n$ имеет $n$ произвольных повторений в некоторой фиксированной(?) системе счисления, будет больше.
И, всё же, можно ли доказать хотя бы в конкретном случае $21_{10}$?
А, понял, про основание Конечно, $...k^2 \mod 100^n=...$. Поправил. Спасибо.

[wrest]

gris в сообщении #1692303 писал(а):

Но как же быть с доказательством

Можно попробовать показать, что если существует одно решение с $k$ повторениями пары $21$ то их существует так же и бесконечно много, причем решения составляют арифметическую прогрессию с разностью $10^{2k}$
Например, для $k=1$ имеем прогрессию $n_d=11+100d, d\in \mathbb{N}$, все квадраты членов которой $n_d^2$ оканчиваются на $21$
Для $k=2$ имеем прогрессию $n_d=1006011+10^4d,d\in \mathbb{N}$ все квадраты членов которой $n_d^2$ оканчиваются на $2121$
Функция что я привел выше, как раз и вычисляет первый член прогрессии.
Ну а дальше можно показать что если существует решение с $k$ повторениями $21$, то существует и с $k+1$ повторениями (и функция ровно так и работает -- рекурсивно вычисляя следующее из предыдущего).

Для обобщения надо потом вывести условие какие пары подходят.

[gris]

wrest, ну да, если есть решение, то по формуле квадрата суммы все числа с добавлением произвольного начала являются решением того же порядка. Можно организовать поиск прибавления, чтобы повысить порядок на две цифры. Я брал первое попавшееся прибавление.
Например,

$39^2= 1521$

$2739^2= 7502121 \quad stop$

$7739^2= 59892121$

$447739^2= 200470212121\quad stop$

$947739^2= 898209212121$

$04947739^2= 24480121212121$

$54947739^2= 3019254021212121 \quad stop$

Но это часто приводило в тупик, поэтому я перебирал с четырьмя цифрами. Интересно посмотреть на последовательность добавления начал: [39, 77, 44, 04...]. По-моему, это то, о чём говорил Dmitriy40. Нет ли там какой периодичности и с существованием не понятно. Мне не понятно . Это я всё сам себе объясняю. Интересно, как представляются деревья в ПАРИ?С помощью map?

[wrest]

gris
Зачем вам деревья?
Смотрите, если часть с арифметической прогрессией понятна

wrest в сообщении #1692305 писал(а):

Можно попробовать показать, что если существует одно решение с $k$ повторениями пары $21$ то их существует так же и бесконечно много, причем решения составляют арифметическую прогрессию с разностью $10^{2k}$
Например, для $k=1$ имеем прогрессию $n_d=11+100d, d\in \mathbb{N}$, все квадраты членов которой $n_d^2$ оканчиваются на $21$
Для $k=2$ имеем прогрессию $n_d=1006011+10^4d,d\in \mathbb{N}$ все квадраты членов которой $n_d^2$ оканчиваются на $2121$

То было бы неплохо это зафиксировать формально. Т.к. это инструмент производства бесконечного количества чисел, квадраты которых оканчиваются на конкртеное количество повторений. Вы же хотите доказательство? Докажите сперва это. Пусть дано $n_0$ такое, что $n_0^2$ оканчивается на $k$ повторений 21. Покажите что $n_d^2=(n_0+d\cdot 10^{2k})^2, d=1,2,...$ так же оканчивается на $k$ повторений 21.

[gris]

wrest, я чисто по ощущениям: если раскрыть скобки в выражении $n_d^2=(n_0+d\cdot 10^{2k})^2=n_0^2+2\cdot n_0\cdot 10^{2k}+10^{4k}, d=1,2,...$ то видно, что второе и третье слагаемые оканчиваются на 2к нулей и последние 2к цифр квадрата любого члена прогрессии будут одинаковыми всегда.
Это можно расписать с модулями, но я не очень там
Проблема даже не в первом шаге, а в таком, чтобы он не привёл к мёртвой ветви дерева Про деревья я не в связи с этой задачей. Изучаю вашу программу.

+++ Dmitriy40, спасибо за совет по Мар. Надо поизучать и попробовать.

[Dmitriy40]

Деревья в PARI можно хранить в Map(), используя в качестве ключа список родительских вершин.
Список можно представить в виде $k$-ричного числа и получим просто число (в $k$-ричной системе счисления). Переход от текущего к родителю n=n\k, к потомку n=n*k+a, корень n=0, высота текущего h=logint(n,k).

-- 26.06.2025, 14:37 --

Предлагаю посмотреть на переходы при удлинении пар с 5 по 9:

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

2: [4, 16, 21, 29, 36, 61, 64, 69, 84, 96], #=80

3: [16, 21, 29, 61, 64, 69, 84], #=80

4: [21, 29, 61, 64, 69, 84], #=80

5: [21, 29, 61, 69, 84], #=48

4491146011 -> 264491146011 764491146011
9491146011 ->
4458286813 ->
9458286813 -> 19458286813 519458286813
3681179119 ->
8681179119 -> 448681179119 948681179119
1482292022 ->
3982292022 ->
6482292022 ->
8982292022 -> 28982292022 278982292022 528982292022 778982292022
1990104522 -> 111990104522 361990104522 611990104522 861990104522
4490104522 ->
6990104522 ->
9490104522 ->
2161759423 ->
7161759423 -> 317161759423 817161759423
162459327 -> 190162459327 690162459327
5162459327 ->
2080539631 -> 332080539631 832080539631
7080539631 ->
639369437 -> 330639369437 830639369437
5639369437 ->
4004947739 -> 194004947739 694004947739
9004947739 ->
995052261 ->
5995052261 -> 305995052261 805995052261
4360630563 ->
9360630563 -> 169360630563 669360630563
2919460369 ->
7919460369 -> 167919460369 667919460369
4837540673 ->
9837540673 -> 309837540673 809837540673
2838240577 -> 182838240577 682838240577
7838240577 ->
509895478 ->
3009895478 ->
5509895478 ->
8009895478 -> 138009895478 388009895478 638009895478 888009895478
1017707978 -> 221017707978 471017707978 721017707978 971017707978
3517707978 ->
6017707978 ->
8517707978 ->
1318820881 -> 51318820881 551318820881
6318820881 ->
541713187 -> 480541713187 980541713187
5541713187 ->
508853989 ->
5508853989 -> 235508853989 735508853989
6: [21, 29, 61, 69, 84], #=48

264491146011 ->
764491146011 -> 36764491146011 86764491146011
19458286813 -> 44019458286813 94019458286813
519458286813 ->
448681179119 -> 7448681179119 57448681179119
948681179119 ->
28982292022 ->
278982292022 ->
528982292022 -> 23528982292022 48528982292022 73528982292022 98528982292022
778982292022 ->
111990104522 ->
361990104522 ->
611990104522 -> 8611990104522 33611990104522 58611990104522 83611990104522
861990104522 ->
317161759423 ->
817161759423 -> 21817161759423 71817161759423
190162459327 -> 48190162459327 98190162459327
690162459327 ->
332080539631 -> 30332080539631 80332080539631
832080539631 ->
330639369437 -> 2330639369437 52330639369437
830639369437 ->
194004947739 -> 33194004947739 83194004947739
694004947739 ->
305995052261 ->
805995052261 -> 16805995052261 66805995052261
169360630563 ->
669360630563 -> 47669360630563 97669360630563
167919460369 ->
667919460369 -> 19667919460369 69667919460369
309837540673 ->
809837540673 -> 1809837540673 51809837540673
182838240577 -> 28182838240577 78182838240577
682838240577 ->
138009895478 ->
388009895478 -> 16388009895478 41388009895478 66388009895478 91388009895478
638009895478 ->
888009895478 ->
221017707978 ->
471017707978 -> 1471017707978 26471017707978 51471017707978 76471017707978
721017707978 ->
971017707978 ->
51318820881 ->
551318820881 -> 42551318820881 92551318820881
480541713187 ->
980541713187 -> 5980541713187 55980541713187
235508853989 -> 13235508853989 63235508853989
735508853989 ->
7: [21, 29, 61, 69, 84], #=48

36764491146011 -> 3536764491146011 8536764491146011
86764491146011 ->
44019458286813 ->
94019458286813 -> 1294019458286813 6294019458286813
7448681179119 -> 1007448681179119 6007448681179119
57448681179119 ->
23528982292022 ->
48528982292022 ->
73528982292022 -> 2073528982292022 4573528982292022 7073528982292022 9573528982292022
98528982292022 ->
8611990104522 ->
33611990104522 -> 533611990104522 3033611990104522 5533611990104522 8033611990104522
58611990104522 ->
83611990104522 ->
21817161759423 ->
71817161759423 -> 371817161759423 5371817161759423
48190162459327 -> 2948190162459327 7948190162459327
98190162459327 ->
30332080539631 ->
80332080539631 -> 4280332080539631 9280332080539631
2330639369437 -> 902330639369437 5902330639369437
52330639369437 ->
33194004947739 -> 2233194004947739 7233194004947739
83194004947739 ->
16805995052261 ->
66805995052261 -> 2766805995052261 7766805995052261
47669360630563 ->
97669360630563 -> 4097669360630563 9097669360630563
19667919460369 -> 719667919460369 5719667919460369
69667919460369 ->
1809837540673 ->
51809837540673 -> 2051809837540673 7051809837540673
28182838240577 -> 4628182838240577 9628182838240577
78182838240577 ->
16388009895478 ->
41388009895478 ->
66388009895478 -> 1966388009895478 4466388009895478 6966388009895478 9466388009895478
91388009895478 ->
1471017707978 ->
26471017707978 -> 426471017707978 2926471017707978 5426471017707978 7926471017707978
51471017707978 ->
76471017707978 ->
42551318820881 ->
92551318820881 -> 3992551318820881 8992551318820881
5980541713187 -> 3705980541713187 8705980541713187
55980541713187 ->
13235508853989 ->
63235508853989 -> 1463235508853989 6463235508853989
8: [21, 29, 61, 69, 84], #=48

3536764491146011 ->
8536764491146011 -> 408536764491146011 908536764491146011
1294019458286813 -> 301294019458286813 801294019458286813
6294019458286813 ->
1007448681179119 ->
6007448681179119 -> 266007448681179119 766007448681179119
2073528982292022 ->
4573528982292022 ->
7073528982292022 -> 67073528982292022 317073528982292022 567073528982292022 817073528982292022
9573528982292022 ->
533611990104522 ->
3033611990104522 ->
5533611990104522 -> 35533611990104522 285533611990104522 535533611990104522 785533611990104522
8033611990104522 ->
371817161759423 -> 10371817161759423 510371817161759423
5371817161759423 ->
2948190162459327 -> 212948190162459327 712948190162459327
7948190162459327 ->
4280332080539631 ->
9280332080539631 -> 99280332080539631 599280332080539631
902330639369437 -> 160902330639369437 660902330639369437
5902330639369437 ->
2233194004947739 ->
7233194004947739 -> 357233194004947739 857233194004947739
2766805995052261 -> 142766805995052261 642766805995052261
7766805995052261 ->
4097669360630563 ->
9097669360630563 -> 339097669360630563 839097669360630563
719667919460369 -> 400719667919460369 900719667919460369
5719667919460369 ->
2051809837540673 ->
7051809837540673 -> 287051809837540673 787051809837540673
4628182838240577 ->
9628182838240577 -> 489628182838240577 989628182838240577
1966388009895478 ->
4466388009895478 -> 214466388009895478 464466388009895478 714466388009895478 964466388009895478
6966388009895478 ->
9466388009895478 ->
426471017707978 ->
2926471017707978 -> 182926471017707978 432926471017707978 682926471017707978 932926471017707978
5426471017707978 ->
7926471017707978 ->
3992551318820881 -> 233992551318820881 733992551318820881
8992551318820881 ->
3705980541713187 ->
8705980541713187 -> 198705980541713187 698705980541713187
1463235508853989 -> 91463235508853989 591463235508853989
6463235508853989 ->
9: [21, 29, 61, 69, 84], #=48

Видно что всегда есть 4 варианта по 4 наследника, в остальных случаях по 2 наследника. При этом в 28 вариантах (58.33%) наследников нет вообще, тупик. Но любое число всегда продолжается, так или иначе, нет такого чтобы какое-то число спустя сколько-то развилок вдруг уткнулось всеми ветвями в тупики. При этом общее количество 48 сохраняется, как и список возможных пар. Причём в четвёрках сумма крайних равна сумме средних. Очень похоже на систему вычетов по модулю.

[wrest]

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

Очень похоже на систему вычетов по модулю.

Да. Пара $ab$ повторенная $k$ раз (пусть этотбудет $AB$, например $AB=161616$ для пары 16 и 3 повторения) подходит для окончания в записи квадрата если система сравнений имеет решение $n$ такое что

$$ \begin{cases} n^2 = AB \pmod {5^{2k}}\\ n^2 = AB \pmod {2^{2k}} \\ \end{cases} $$

[wrest]

gris в сообщении #1692365 писал(а):

то видно, что второе и третье слагаемые оканчиваются на 2к нулей и последние 2к цифр квадрата любого члена прогрессии будут одинаковыми всегда.

Верно.
Теперь мы знаем, что если у нас уже есть какой-то квадрат который заканчивается нужным "хвостом", то есть и бесконечное количество квадратов заканчивающихся этим же "хвостом".

Следующий этап -- доказать, что у квадрата в хвосте пара 21 может повторяться любое количество раз.
Тут как раз и нужна КТО, которая позволяет рассмотреть систему сравнений вместо одного.
А именно, обозначив "хвост" длиной $2k$ за $AB$, гам надо показать, что существует такое $n$, что $n^2 = AB \pmod {10^{2k}}$
По КТО, это так если система сравнений имеет решение $n$ такое что

$$ \begin{cases} n^2 = AB \pmod {5^{2k}}\\ n^2 = AB \pmod {2^{2k}} \\ \end{cases} $$

То есть $AB$ является одновременно квадратичным вычетом по двум модулям $2^{2k}$ и $5^{2k}$

[gris]

wrest, вы будете смеяться, но я только слышал издалека слова "квадратичный вычет" без понимания, но вот он подкрался незаметно. Я хочу подробно познакомиться с теорией (уж не скажу — изучить). У нас не было теории чисел:( Посмотрел на форуме посты... Но хочу обстоятельно. Заглянул в Бухштаба. Но 172-я страница. (А до того тёмный лес. Так вот что это было! Это я о своём). Попробую!

[wrest]

wrest в сообщении #1692413 писал(а):

То есть $AB$ является одновременно квадратичным вычетом по двум модулям $2^{2k}$ и $5^{2k}$

Вот в общем-то и есть самая суть задачи.
С модулем $5^{2k}$ всё просто. Наше число должно давать остаток $0,1,4$ от деления на $5$.
В случае с парой 21 это всегда так: остаток от деления на 5 любого из чисел $AB$, т.е. 21, 2121, 212121 и так далее, равен 1.

А вот с модулем $2^{2k}$ надо возиться. И кстати это именно он "отвечает" за то, что список подходящих пар уменьшается с ростом количества их повторений. Из-за него 16 может повторяться три раза но не 4, и 64 может повторяться 4 раза но не 5.

-- 26.06.2025, 19:32 --

gris в сообщении #1692423 писал(а):

вы будете смеяться, но я только слышал издалека слова "квадратичный вычет" без понимания, но вот он подкрался незаметно.

Я примерно в вашем положении. Но если у вас есть Википедия, chatGPT и тому подобное, то ненадолго можно сойти и за умного
По сути записанное вами

gris в сообщении #1692238 писал(а):

формальное условие.

$$\exists m\in [1,99]:\quad \forall n \exists k:\quad k^2 \mod 100^n=(100^n-1)/99\cdot m$$

словами передаётся как:
-- [для любого целого числа $n>0$] существует такое целое число $m \in [1,99]$, что число $m\dfrac{100^n-1}{99}$ является квадратичным вычетом по модулю $100^n$

[gris]

Спасибо за внимание к теме. Я и правда решил подойти к своей неосновательности в ТЧ основательно. Вот выбрал учебник А.А. Бухштаба "Теория чисел" и стал читать его, как прилежный школьник с самого начала, подробно и практически усваивая теоретические положения.
И со второго абзаца введения наткнулся на пример:
"...среди натуральных чисел есть числа, которые нельзя представить в виде суммы двух квадратов натуральных чисел, и <можно> поставить вопрос о том, какие именно числа обладают этим свойством и как часто встречаются такие числа."
Я решил подробно ознакомиться с вопросом и сочинил программку

{n=70 001; nn=80 000; 
s=[]; k=0;
for(i=1,sqrtint(nn-1),
  if(2*i^2>=n-1, nj=i,nj=sqrtint(n-i^2));
  for(j=nj,sqrtint(nn-i^2),
    g=i^2+j^2; if(g<n,next);",i^2+j^2);
    s=setunion(s,Set(g)); k++; 
));
printf("%d - %d  %d %.2f %d\n",n,nn,#s,(#s+0.0)/(nn-n+1),k);
}
70001 - 80000  2311 0.23 3923
time = 296 ms.
1 - 1000000  215908 0.22 392547
time = 53min, 13,872 ms.

Выдаётся диапазон, количество чисел, которые представляются суммой квадратов, их доля в диапазоне, и общее количество случаев представления, так некоторые числа имеют несколько представлений.
Например: 85=4+81=49+36.
Для подробного анализа я ввёл вектор количества представлений числа в виде суммы квадратов.
vr=vector(nn-n+1); ...
g=i^2+j^2; ...
vr[g-n+1]++;
Конечно, для больших диапазонов иметь такой вектор расточительно, но по нему можно найти многие интересные подробности.
Наверное, Map был бы получше.
Пока изучаю предмет
Советы по теме приму с благодарностью.