Непрерывные куски ряда натуральных квадратов.

[nnosipov]

wrest
Имеем

$$N=m^2+(m+1)^2+\ldots+(m+n-1)^2=\frac{n(6m^2+6mn+2n^2-6m-3n+1)}{6},$$

откуда число квадратов $n$ является делителем числа $6N$. Если $n$ известно, то $m$ можно найти, решая квадратное уравнение.

[wrest]

nnosipov в сообщении #1713174 писал(а):

откуда число квадратов $n$ является делителем числа $6N$. Если $n$ известно, то $m$ можно найти, решая квадратное уравнение.

Это да, но факторизация $N$ тут, как мне кажется, не нужна. Факторизация довольно затратная операция.
Для каждого допустимого $n<\sqrt[3]{3N}$ (или для первого которое подошло) находим дискриминант
$D=\dfrac{12Nn - n^4 + n^2}{3}$ и проверяем является ли он полным квадратом (перед этим проверяем целое ли он число). Если да, то решаем квадратное уравнение (и получили ли целое $m$).

[Dmitriy40]

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

Для каждого допустимого $n<\sqrt[3]{3N}$

Так это и есть факторизация, в момент определения допустимости $n$. И чтобы не перебирать все $n$ проще разложить $6N$ и перебирать только $n$ являющиеся делителями, их на порядки меньше. Для небольших чисел то же на то же и получится, но вот для больших факторизация проще.

[gris]

Решил немного посчитать не для проверки, а для демонстрации наизусть
20449= 7 ^2 + ..< 33 >.. + 39^2
20449= 38 ^2 + ..< 11 >.. + 48^2
20449= 143 ^2 + ..< 1 >.. + 143^2

divisors(20449*6)= [1, 2, 3, 6, 11, 13, 22, 26, 33, 39, ...]
Да, 1, 11, 33 есть в делителях
Кстати, как одной командой получить вектор (сет) с элементами меньшими заданного числа?
И отличается ли по времени получение делителей от числа или его же ушестерённого?
gp > #divisors((13^73+237)*1)
time = 41,341 ms.
%7 = 128
(10:23) gp > #divisors((13^73+237)*6)
time = 41,294 ms.
%8 = 384
Не отличается, что естественно.

[wrest]

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

И чтобы не перебирать все $n$ проще разложить $6N$ и перебирать только $n$ являющиеся делителями

Вот это технически непонятно. Давайте на двух примерах, вот факторизовали пару чисел:
$6N_1=2^1 \cdot 3^1 \cdot 163\cdot 4557043$
$6N_2=2^3\cdot 3^2 \cdot 5^2 \cdot 7^1 \cdot 31^1 \cdot 61^1 \cdot 251^1$
Что именно делаем дальше для

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

перебирать только $n$ являющиеся делителями

[Dmitriy40]

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

Вот это технически непонятно. Давайте на двух примерах, вот факторизовали пару чисел:
$6N_1=2^1 \cdot 3^1 \cdot 163\cdot 4557043$

? divisors(742798009*6)
%2 = [1, 2, 3, 6, 163, 326, 489, 978, 4557043, 9114086, 13671129, 27342258, 742798009, 1485596018, 2228394027, 4456788054]
? sqrtnint(3*742798009,3)
%3 = 1306
? select(t->t>1&&t<=%3,%2)
%4 = [2, 3, 6, 163, 326, 489, 978]

Вот только такие $n$ и надо проверить. $n=978$ подходит и даёт решение.

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

$6N_2=2^3\cdot 3^2 \cdot 5^2 \cdot 7^1 \cdot 31^1 \cdot 61^1 \cdot 251^1$

? 2^3*3^2*5^2*7^1*31^1*61^1*251^1/6
%1 = 996746100
? sqrtnint(3*%1,3)
%2 = 1440
? select(t->t>1&&t<=%2,divisors(6*%1))
%3 = [2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 21, 24, 25, 28, 30, 31, 35, 36, 40, 42, 45, 50, 56, 60, 61, 62, 63, 70, 72, 75, 84, 90, 93, 100, 105, 120, 122, 124, 126, 140, 150, 155, 168, 175, 180, 183, 186, 200, 210, 217, 225, 244, 248, 251, 252, 279, 280, 300, 305, 310, 315, 350, 360, 366, 372, 420, 427, 434, 450, 465, 488, 502, 504, 525, 549, 558, 600, 610, 620, 630, 651, 700, 732, 744, 753, 775, 840, 854, 868, 900, 915, 930, 1004, 1050, 1085, 1098, 1116, 1220, 1240, 1255, 1260, 1281, 1302, 1395, 1400]

Вот такие $n$ и надо проверить. $n=248$ даёт решение.

-- 23.12.2025, 10:51 --

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

Что именно делаем дальше для $n$

Да что угодно, можно $m$ поискать по формуле, можно разместить цепочку на место $\sqrt{N/n}$ и попытаться подвинуть до суммы равной $N$ (например как у меня выше в коде внутри первого цикла for).

-- 23.12.2025, 11:08 --

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

Кстати, как одной командой получить вектор (сет) с элементами меньшими заданного числа?

Только что как раз применил эту команду:
nmax=sqrtnint(3*N, 3); select(t -> t>1 && t<=nmax, divisors(6*N))

[gris]

по рекомендациям:
{N=3568718559346306;
dmax=floor((3*N)^(1/3))+1;; print(dmax);
d=divisors(N*6);
for(i=1,#d,
if(d[i]>dmax, break);
n=d[i];
d3=12*N*n-n^4+n^2;
if(d3%3==0&& issquare(d3\3),print(d[i]));
)}
N=3568718559346306
29621 количество слагаемых
106012
204131
gp >

Да, очень похоже на три решения. Теперь надо решить кв.ур. А где оно?

[wrest]

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

Вот только такие $n$ и надо проверить. $n=978$ подходит и даёт решение.

Да, теперь понятно, супер!
Ускорение на два порядка примерно

[Dmitriy40]

Получается примерно так:

x=3568718559346306;
{print("x=",x); t0=getwalltime();
nmax=sqrtnint(x*3,3); print("n<=",nmax);
foreach(select(t->t<=nmax,divisors(6*x)),n,
   a=4*x/n-(n^2-1)/3; if(!issquare(a,&a), next); a=(a-n+1)/2; b=a+n-1;
   s=b*(b+1)*(2*b+1)/6-a*(a+1)*(2*a+1)/6+a^2;\\Можно и упростить
   if(s==x, print(a,"^2...",b,"^2=",s,", len=",b-a+1); );
);
print("Time: ",strtime(getwalltime()-t0));

x=3568718559346306
n<=220399
332186^2...361806^2=3568718559346306, len=29621
127900^2...233911^2=3568718559346306, len=106012
16299^2...220429^2=3568718559346306, len=204131
Time: 1 ms

[wrest]

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

Ускорение на два порядка примерно

Тут надо уточнить что ускоряется. Я генерирую случайные числа в диапазоне $0 \dots 10^9$ и пытаюсь их представить суммой последовательных квадратов (причём всеми способоми а не только первым попавшимся). И считаю до ста удач. Вот это и ускоряется, в 80 раз примерно.

[gris]

Вот заметил такую фичу:
1026745= 716^2 + ..< 2 >.. + 717^2
1026745= 51^2 + ..< 97 >.. + 147^2
1026745= 1^2 + ..< 145 >.. + 145^2
1026745= 0^2 + ..< 146 >.. + 145^2
Если считать натуральные решения, то стоит ли засчитывать решение с нулём? Оно получается понятно когда. Но уж очень оно ненатуральное

нашлось четыре чистых решения
1 554503705= 7442^2 + ..< 10 >.. + 7451^2
2 554503705= 3613^2 + ..< 42 >.. + 3654^2
3 554503705= 3570^2 + ..< 43 >.. + 3612^2
4 554503705= 480^2 + ..< 731 >.. + 1210^2

[wrest]

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

Если считать натуральные решения, то стоит ли засчитывать решение с нулём?

Ноль это как-то неспортивно