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

[gris]

тихо ползёт червячок
по дороге в Киото
горбуша
Попалась тут задача, которую сочинил наш gipokrat:
представить некоторое число в виде суммы непрерывного куска последовательности квадратов натуральных чисел. Например:
$86=3^2+4^2+5^2+6^2$. Не все числа поддаются. Ну можно находить приближения. Самые близкие.
for 300 dmin=2: SQ[9,11] = 302
for 2025 dmin=0: SQ[45,45] = 2025
for 5455 dmin=0: SQ[31,35] = 5455
for 200025 dmin=15: SQ[198,202] = 200010
for 20000025 dmin=4: SQ[487,559] = 20000029
for 200000025 dmin=194: SQ[5771,5776] = 199999831
for 1234589012345 dmin=5170: SQ[10886,17092] = 1234589007175
На ночь глядя запросил у ИИ программку на любимом ПАРИ.

{
foreach([300,2025,5455,200025,20000025,200000025,1234589012345],k, \\числа для приближения
  n=floor((k*3)^(1/3))-1; kn=n*(n+1)*(2*n+1)\6; \\оценка суммы кв от 1 до  n превышающей число
  while(kn<k, n++;kn+=n^2); \\уточнение суммы
  mt=1; 
  nt=n;
  kt=kn; 
  dl= k-kt+nt^2; ml=mt; nl=nt-1; \\левое приближение
  dr= kt-k; mr=mt; nr=nt; \\правое приближение

  nmax=floor(sqrt(k));  \\оценка максимально далёкой цепочки
  for( n=nt,nmax,  \\перебор цепочек
     while(kt > k, kt+=-mt ^2; mt++);\\подтягивание хвоста
     dlt=k-kt; if(dlt<dl,dl=dlt; ml=mt; nl=n);\\соревнование приближений
     mt=mt-1; kt+=mt^2;    
     drt=kt-k; if(drt<dr,dr=drt; mr=mt; nr=n);
     kt+=(n+1)^2; \\шаг цепочки вперёд
  );
  kr=k-dl;\\выбор приближений если оставляем одно
  if(dr<dl,dl=dr; ml=mr; nl=nr;kr=k+dr); 
  printf("for %d dmin=%d: SQ[%d,%d] = %d\n",k,dl,ml,nl,kr);
)}
   

Выползает червячок на бесконечный ряд квадратов, поджимает хвост, потом вперёд толкает голову, потом снова поджимает хвост... Так и доползёт. Мне понравилось. Но надо совершенствовать. А спать хочу.

[mathpath]

Дипсик говорит, что число 1234589012345 не представимо как минимум с помощью тысячи подряд идущих квадратов

[gris]

mathpath, у этого числа гэпофрения, как и было сказано. Ближайшее представимое число 1234589007175 = SQ[10886,17092] находится на расстоянии dmin=5170 Вообще, даже для небольших чисел порядка $10^{20}$ в множестве представимых чисел встречаются трёхсоттысячные гэпы.
for 2000000000000000025 dmin=178105:
2163153^2+ ... +2526224^2 = 1999999999999821920
Конечно, хочется вместо квадратов взять простяшки, но там уже скорее всего побывали исследователи. Хотя стоило бы взяться за прилежное изучение вопроса.

+++Dmitriy40, спасибо. Поизучаю.

[Dmitriy40]

x=1234589012345;

F()=my(); if(abs(s-x)<err, err=abs(s-x); print(a,"^2...",b,"^2=",s,", len=",b-a+1,", err=",s-x));

{print("x=",x); t0=getwalltime();
a=0; if(issquare(x,&a), print(a,"^2=",x,", len=1, err=0"); quit;);
err=a=b=x;
for(n=2,oo,
   t=a; a=ceil(sqrt(x/n)); if(a>t, a=t; b++; s+=b^2; F(); break);
   b=a+n-1; s=b*(b+1)*(2*b+1)/6-a*(a+1)*(2*a+1)/6+a^2; F();
   while(s>x && a>1 && err>0, s-=b^2; b--; F(); a--; s+=a^2; F(); );
);
while(a>1 && err>0,
   while(s>x && b>a, s-=b^2; b--; F(); );
   while(s<x && a>1, a--; s+=a^2; F(); );
);
print("Time: ",strtime(getwalltime()-t0)); quit;}

x=1234589012345
785681^2...785682^2=1234590838885, len=2, err=1826540
785680^2...785681^2=1234587696161, len=2, err=-1316184
641505^2...641507^2=1234589844110, len=3, err=831765
419961^2...419967^2=1234588329100, len=7, err=-683245
392837^2...392844^2=1234589267564, len=8, err=255219
296953^2...296966^2=1234589225191, len=14, err=212846
155563^2...155613^2=1234588923994, len=51, err=-88351
66382^2...66660^2=1234588929819, len=279, err=-82526
41049^2...41768^2=1234589091960, len=720, err=79615
27856^2...29363^2=1234589037214, len=1508, err=24869
25617^2...27374^2=1234589020079, len=1758, err=7734
10886^2...17092^2=1234589007175, len=6207, err=-5170
Time: 808 ms

[Dmitriy40]

Более быстрый вариант:

x=1234589012345;

F()=my(); if(abs(s-x)<err, err=abs(s-x); print(a,"^2...",b,"^2=",s,", len=",b-a+1,", err=",s-x); );

{print("x=",x); t0=getwalltime();
a=0; if(issquare(x,&a), print(a,"^2=",x,", len=1, err=0"); quit;);
nmax=sqrtnint(x*3,3); s=nmax*(nmax+1)*(2*nmax+1)\6; while(s>x, s-=nmax^2; nmax--); while(s<x, nmax++; s+=nmax^2);
err=x; a=1; b=nmax; F();
for(n=2,max(2,nmax\10),
   if(err==0, break);
   t=floor(sqrt(x/n)-n/2); if(t<1, break); a=t; b=a+n-1;
   s=b*(b+1)*(2*b+1)/6-a*(a+1)*(2*a+1)/6+a^2;
   while(s<x,        s-=a^2; a++; b++; s+=b^2; );
   while(s>x && a>1, s-=b^2; b--; a--; s+=a^2; );
   F(); s-=a^2; a++; b++; s+=b^2; F();
);
while(a>1 && err>0,
   while(s<x && a>1, a--; s+=a^2; ); F(); s-=a^2; a++; F(); a--; s+=a^2;
   while(s>x && b>a, s-=b^2; b--; ); F(); b++; s+=b^2; F(); s-=b^2; b--;
);
print("Time: ",strtime(getwalltime()-t0)); quit;}

-- 20.12.2025, 17:51 --

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

Вообще, даже для небольших чисел порядка $10^{20}$ в множестве представимых чисел встречаются трёхсоттысячные гэпы.

И что в этом удивительного? Вот Вам трёхмиллионный гэп: $x=\prod\limits_{t=1}^{3000000} t^2=9000004500000500000$.
Вычитая из него квадраты первых натуральных чисел получим ещё сотни тысяч почти столь же длинных гэпов.
А исходя из формулы для суммы первых квадратов можно сразу сказать что до числа $x$ встретятся гэпы примерно до $\sqrt[3]{3x}$. Т.е. до $10^{20}$ будут гэпы почти до 6.7млн.

[wrest]

Вот вам функция которая вычисляет сумму

s(a,n)=n*a*a+a*n*(n-1)+n*(n-1)*(2*n-1)/6

a - первое число
n - количество чисел

? s(31,5)
%1= 5455
?

? s(3,4)
%2 = 86
?

[Dmitriy40]

Интересно что решений может быть не одно, например:
$365=10^2+11^2+12^2=13^2+14^2$
$35645=108^2+109^2+110^2=133^2+134^2$
$28561=119^2+120^2=169^2$

[nnosipov]

Dmitriy40
Вы забыли самое первое и самое известное $3^2+4^2=5^2$ (это все частные случаи однопараметрического тождества).

Upd. Здесь на самом деле два тождества: одно с пифагоровыми тройками, а другое --- то, что я имел в виду.

[wrest]

Это, кстати, A034705

[gris]

Спасибо. Я и формулу применял, и различные представления искал от $25= 5^2= 3^2+4^2$ до чистого трёхкратного $3198550= 1 ^2+ ... +212^2=127 ^2 + ... + 226^2=225 ^2 + ... +275^2$

{N=10000000;
km=floor(sqrt(N));
a=vector(N);
for(m=1,km,
for(n=m,km,
d2=(n*(n+1)*(2*n+1)-m*(m-1)*(2*m-1))\6;
if( d2>N, break,a[d2]++ );
));
for(i=1,N, if(a[i]>2, print(a[i]," ",i)));
}
*** vector: Warning: increasing stack size to 64000000
3 20449
3 147441
3 910805
3 1026745
3 2403800
3 2513434
3 3198550
3 8116801
time = 1,577 ms
.
Потом переключился на простяшки. Там и пять вариантов получается пока памяти хватает
14369= [53, 409]
14369= [173, 443]
14369= [491, 647]
14369= [4787, 4793]
14369= [14369]
А в энциклопедии всё есть. Но мне интересно программку накидать

[wrest]

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

Конечно, хочется вместо квадратов взять простяшки,

Это A034707

-- 20.12.2025, 20:15 --

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

А в энциклопедии всё есть. Но мне интересно программку накидать,

Там бывают идейки и по программам, чем она и хороша, среди прочего.
Ну тут дилемма: посчитать все комбинации параметров (параметры - начало цепочки и длина) и потом сортировать, выявлять повторы, либо пытаться раскладывать каждое натуральное.

[gris]

Конечно, я внимательно читаю OEIS и по ссылкам прохожу, и скрипты разбираю, но стараюсь вначале самому какие-то результаты получить. вот пример:
A234304 Numbers with at least 3 representations as a sum of consecutive square numbers. Сейчас зашёл по поиску по найденным вчера результатам.

Перейдя на кубы вдруг увидел $2025= 1 ^3 + ... + 9^3$
было, конечно, год назад

[Dmitriy40]

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

+++Dmitriy40, спасибо. Поизучаю.

Там смысл лишь в первом цикле for - для каждой длины n мы знаем где будет последовательность квадратов, около $\sqrt{x/n}$, причём это скорее центр цепочки, вот и проверяем лишь там и лишь длиной n. Для малых n это быстрее чем перебирать все числа. Опытным путём прикинул что скорости сравниваются примерно при 10% от максимально возможного n (это когда квадраты с 1 и по n).
Второй цикл, while, практически как и у ИИ.

[nnosipov]

Если речь идет просто о выяснении, можно ли данное $N$ представить суммой последовательных квадратов, то не проще ли будет факторизовать $N$ и затем перебирать все его делители?

[wrest]

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

то не проще ли будет факторизовать $N$ и затем перебирать все его делители?

Поясните мысль пож-ста. Допустим, факторизовали например так $N=163\cdot 4557043$ - что тут перебирать?