Подход к задаче "первые 100" без уравнения Пелля.

[TR63]

Modest: Отделено от темы «Первые 100». Причина: слишком альтернативный подход.

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

проблема вот в чем будет: при любом $d$ есть решения в целых числах (например, $(a,b)=(0,-1)$), но вот в натуральных числах --- отнюдь не при любом. Как отфильтровывать такие случаи?

Можно попробовать другой алгоритм нахождения натуральных решений (без Пелля), используя лишь пифагоровы тройки и условия на них налагаемые. Идея заключается в следующем.

$$ \frac{(a+(a+\alpha)+1)^2}{a(a+\alpha)}=\frac{k}{2}$$

В результате получим, что

$k=4+\frac{q+4}{a}$

$a=-1+\frac{\sqrt{q^2-p^2}}{4}$

$\alpha=\frac{-4a+(q+p)}{4}$

Здесь $(q;p)$ числа из примитивной (этот момент, примитивность, следует обосновать; пока его пропустила) пифагоровой тройки. И видно, каким условиям они должны удовлетворять, чтобы решения были натуральными. Только при $(q;p)=(5;3)$ $a=0$ и метод не срабатывает. При $(q;p)=(73;55)$ получаем $a=11$, $\alpha=21$, $k=11$. Но фильтр пока не просматривается. Сделаем обозначение:

$m=\frac{q+4}{a}$

Тогда получим, что

$a={\frac{1}{32}}\{-(32-qm+pm)+\sqrt{[(32-qm+pm)^2-64(16-qp+4q+p^2-4p)]}\}$

Получаем ещё одно условие на элементы пифагоровой тройки $(q;p)$: форма ею порождаемая $\{-64(16-qp+4q+p^2-4p)\}$ должна быть представима разностью квадратов. (Проверяем для $(q;p)=(73;55)$; всё сходится.)
Остаётся сделать численную проверку для остальных пар $(q;p)$ (возможно их число бесконечно), удовлетворяющих этому условию плюс $(q+p)$ должно делиться на четыре. Если будут по формулам получатся только натуральные решения, то это и будет гипотетический фильтр.
Я не привела промежуточные вычисления, т.к. это громоздко (там простые преобразования: раскрытие скобок и т.д.). Проверила на примере. Формулы работают. Но перепроверка не помешает.

[dmd]

TR63
Ну, $k=11$ не интересно. Повторите свои рассуждения для $k=41$, $k=2025$ и $k=1689$.

(минимальные решения k=41, k=2025, k=1689)

k = 41
a = 282449
b = 5209992

k = 2025
a = 44531997802090968110207001909255304366066384401
b = 44999539709699302763081486345495779014689601386888

k = 1689
a = 2081206593680346721844560800745851787195185777128346815103318108538868305083001759802510492002103524774681425476994283073262591300496131465902474694209844435272359007410616167381791451453976807976637368573397048079188488628200937122936226070468419133781078107904866333734164436562306255776037980868837924225104699958519381932143294621496129239847137507733272758705332973602992596563486898982374087225049266297321955699437152109987613086854899856166169
b = 1753414084897323251875067748824345525916702388394116953765305193372582031326868102667798321823688668754699223891155836880666479106354137164143052037964287569220644899878975308716672804520045399347242456465869250715627502632253877676780927773111756945344758815325805046310834798979418282328416284994062882192992586429388997580241113842783291925087694684834527968301161983344899005823459306069960137372731169699114639211521558062347910306278581630490469768

где $b=a+\alpha$.

Если для $k=41$ перебор пифагоровых троек ещё осуществим, то для $k=2025$ не хватит времени жизни Вселенной, даже если в перебор запрячь все компьютеры всего мира. Не говоря уж про $k=1689$. В том и прелесть алгоритма решения уравнений Пелля, что он исключительно полиномиален по времени вычислительных затрат, даже для очень больших минимальных решений.

[TR63]

dmd, при $k=41$ Вольфрам не даёт разложение на разность квадратов. То ли он не может этого сделать, что сомнительно (справляется и с большими числами), то ли разложения не существует.
Возможно, если разложение на разность квадратов тривиальное $p=0$, $q=q$, то вычисления упрощаются, то ли фильтр в тривиальном случае не работает. Позже попробую.

[TR63]

dmd в сообщении #1391446 писал(а):

Повторите свои рассуждения для $k=41$

Переформулируем задачу. При $k=41$, $a=282449$. Вопрос: может ли $a=282449$ претендовать на роль кандидата для получения натурального $(k)$. $(4(a+1))^2=q^2-p^2$. Разложение только тривиальное: $p=0$, $q=4(a+1)$. $(q+p)$$ делится на четыре. Т.е. первое условие выполнено. Проверяем второе: форма $\{-64(16-qp+4q+p^2-4p)\}$ должна представляться разностью квадратов. Это условие выполняется. Т.е. необходимый фильтр пройден. Но не достаточный (он неизвестен). Поэтому мы не можем утверждать, что $k=4+\frac{q+4}{a}$, $\alpha=1$. Это плохо: надо подставлять кандидата в уравнение и искать, есть ли решение.
Но можно сформулировать другую задачу на основе исходной: когда форма $\{-64(16-qp+4q+p^2-4p)\}$ представима разностью квадратов и бесконечно ли количество таких форм при условии, что $(p+q)$ делится на четыре и $(q;p)$ числа из примитивной пифагоровой тройки.

[TR63]

TR63 в сообщении #1391471 писал(а):

при $k=41$ Вольфрам не даёт разложение на разность квадратов.

Сегодня Вольфрам выдал $270$ разложений.

Значит найденный фильтр не только необходимый, но, возможно, и достаточный. Надо подробнее расписать выкладки, чтобы это выяснить. Но поскольку мощности компа для этой задачи в такой постановке ограничены, то не стоит париться.
Стоит заметить, что проще фильтр быть не может, т.к. он выводился на основе логических рассуждений, а не гипотез.

[TR63]

Оставим в стороне большие числа.
Займёмся малыми. Они
Имеют также долю смысла,
Хоть и находятся в тени.

Да, полученные формулы для нахождения полуцелых при больших $(a_i)$ пока мало перспективны, если их использовать в лоб. Но возникла гипотеза (об этом позже).

Из моего алгоритма можно получить следующую задачу:
Сам алгоритм перепишем в виде

$$ \frac{(a+(a+\alpha)+1)^2}{a(a+\alpha)}=\frac{k}{2}$$

1). $[(a+1)4]^2=q^2-p^2$
2). $k=4+\frac{q+4}{a}=4+m$
3). $\alpha=-a+\frac{q+p}{4}$
4). $[(a+1)4]^2+p^2=(ma-4)^2$

Будем искать минимальное решение. Оно находится с помощью примитивных пифагоровых троек (ППТ), и, если существует, то единственно.

1). $4(a+1)=2l_1l_2$
2). $p=l_1^2-l_2^2$
3). $ma-4=l_1^2+l_2^2$

$2(l_1^2+l_2^2+4+m)=ml_1l_2$
Не ограничивая общности можно считать, что $(l_2)$ чётное. Тогда получим, что должно выполняться условие

$(m^2-16)l_2^2-16(m+4)=d^2$
$(m+4)d_1^2-(m-4)l_2^2=-16$

$$(m+4)d_2^2-(m-4)l_3^2=-4$$

Экспериментально $\min\{m\}$ известен и равен $7$. Значит, если рассматривать только уравнения Пелля (обобщённые), то решение гипотетически существует только при $m=7$.

Вопрос 1.
Как это доказать, не опираясь на приведённые рассуждения. (Между прочим, на одном форуме за подобную задачу был обещан студентам бонус. В Олимпиадном разделе парочка подобных уже решена.)

Вопрос 2.
Существует ли ППТ $(q;p)\neq(5;3)$ такая, что для неё не существует коэффициент $(r)$, при котором ${r(q;p)}$ порождает $(a)$, дающее полуцелое $(k)$. (Известно, что существуют $(a_i)$, не порождающие полуцелые.)

Итак, что мы имеем.

1). ППТ $(q;p)=(73;55)$ порождает минимальное полуцелое $(a_1;k_1)=(11;11)$.
2). Существуют не примитивные ПТ, порождающие $(a_i)$, дающие полуцелые. Например:

1. $(q;p)=(260;240)$, $a=24$, $k=15$, $r=20$, $20(13;12)=(260;240)$, $N=2$.
2). $(q;p)=(8996;8960)$, $a=200$, $k=49$.
3). $a=1000$ (здесь тоже вычисления простые; надо запрограммировать технологию; по номеру ППТ можно определять номер полуцелого и обратно, если известно полуцелое $(a;k)$, можно определить гипотетически его номер; но нумерация отлична от нумерации ТС.)

Гипотеза:

Для любой ППТ $(q;p)\neq(5;3)$ существует коэффициент $(r)$ такой, что$\{r(q;p)\}$ порождает $(a_i)$, дающее полуцелое $(k)$.

Из этой гипотезы следует существование бесконечного количества полуцелых. Найти контрпример к такой гипотезе не хватит ресурсов любого компа (мощности всей Вселенной).

[TR63]

Замечание.

TR63 в сообщении #1394487 писал(а):

Не ограничивая общности можно считать, что $(l_2)$ чётное. Тогда получим, что должно выполняться условие

$(m^2-16)l_2^2-16(m+4)=d^2$
$(m+4)d_1^2-(m-4)l_2^2=-16$

Поясню дальнейший переход.
Для того, чтобы у нас была последовательность уравнений, у которой $\min(m)$, при котором начинают существовать решения, равнялся $7$, необходимо и достаточно (? надо уточнить) выполнения условий: $(m)$ должно быть нечётным; $m-4>0$; $m-4\neq k^2$. Иначе $\min(m)\neq7$.

TR63 в сообщении #1394487 писал(а):

$$(m+4)d_2^2-(m-4)l_3^2=-4$$

Значит, если рассматривать только уравнения Пелля (обобщённые), то решение гипотетически существует только при $m=7$

при указанных для $(m)$ условиях, т.к. минимумов не может быть более одного.
Интересно, существует ли контрпример к такой задаче?

[TR63]

TR63 в сообщении #1411379 писал(а):

при указанных для $(m)$ условиях, т.к. минимумов не может быть более одного.

Это ошибочное рассуждение, т.к. возможны просто посторонние корни. Контрпример нашёлся к этой задаче уже при $m=15$ (при первом счёте его не было; может, невнимательно смотрела).
Но, тем не менее задача получилась полезная тем, что в ней нет экстраполяции (дальнейшего отсутствия решений). А, почему? Идея есть. Но надо подумать.

[TR63]

Формула $m-4\neq k^2$, с помощью которой было исключено значение $m=5$, не является непрерывной. А, исключить это значение необходимо, т.к. иначе при $m=5$ уже имеется решение $9x^2-y^2=-4$ $(x;y)=(0;\pm2)$ (возможны посторонние корни). Подойдёт формула $m=5k+2$, где $(k)$ нечётное $k=2k_1+1$, $k_1>0$.

Тогда уравнение Пелля с параметром

$$(5k+6)x^2-(5k-2)y^2=-4$$

не имеет решений при нечётном $k>1$, т.к. возможен только единственный минимум при $m=7$ (установлен экспериментально).
Если такое утверждение не достаточно корректно, то его можно принять в качестве гипотезы, которую следует проверить. В первых ста значениях $(m)$ решений нет. Проверила на Вольфраме. Но следует проверить на более приличном промежутке или доказать иным способом (наличие; отсутствие) решений при $k>1$ в этом уравнении Пелля с параметром.

[dmd]

Минимальные решения уравнения $(m+4)x^2-(m-4)y^2=-4$ для $m$ в диапазоне 6..100:
m = 7 (x, y) = (2, 4)
m = 8 (x, y) = (0, 1)
m = 13 (x, y) = (16, 22)
m = 15 (x, y) = (70, 92)
m = 23 (x, y) = (1010, 1204)
m = 37 (x, y) = (1448, 1614)
m = 47 (x, y) = (33978, 37004)
m = 55 (x, y) = (204590, 220052)
m = 63 (x, y) = (498570314, 531297548)
m = 77 (x, y) = (1082833096, 1140624250)
m = 85 (x, y) = (106000424000318000, 111111777778777778)
m = 93 (x, y) = (119293840, 124540006)

(gp-код)

 for(m=6, 100,
  m4= m+4; A= m^2-16; B= -4*m4;
  Q= bnfinit('x^2-A, 1);
  if(bnfcertify(Q),
   fu= Q.fu[1];
   N= bnfisintnorm(Q, B);
   for(i=1, #N, n= N[i];
    for(j=0, 100,
     s= lift(n*fu^j);
     y= abs(polcoeff(s, 1)); x= abs(polcoeff(s, 0));
     if(q, if(x==floor(x)&&y==floor(y), if(x^2-A*y^2==B, if(x%m4==0,
      print("m = "m"    (x, y) = ("x/m4", "y")");
      break(1)
     ))))
    )
   )
  )
 )

Минимальные решения уравнения $(5k+6)x^2-(5k-2)y^2=-4$ для $k$ в диапазоне 1..100:
k = 1 (x, y) = (2, 4)
k = 7 (x, y) = (1448, 1614)
k = 9 (x, y) = (33978, 37004)
k = 15 (x, y) = (1082833096, 1140624250)
k = 23 (x, y) = (818590689897712, 847071879116434)
k = 25 (x, y) = (1712613322, 1767430764)
k = 33 (x, y) = (1265158590626, 1295833555460)
k = 47 (x, y) = (82510649152, 83915186614)
k = 49 (x, y) = (30594675027056114, 31094212946736100)
k = 71 (x, y) = (1277462376904301174798671517208673408001505856, 1291856773508340707358718870367357872922647970)
k = 79 (x, y) = (544484274798013543588408966197749366848, 549998180257063159443801701603635377366)
k = 89 (x, y) = (804879312350124413618298262, 812114328066004380990145756)

(gp-код)

 for(k=1, 100,
  k5= 5*k+6; A= k5*(5*k-2); B= -4*k5;
  Q= bnfinit('x^2-A, 1);
  if(bnfcertify(Q),
   fu= Q.fu[1];
   N= bnfisintnorm(Q, B);
   for(i=1, #N, n= N[i];
    for(j=0, 100,
     s= lift(n*fu^j);
     y= abs(polcoeff(s, 1)); x= abs(polcoeff(s, 0));
     if(q, if(x==floor(x)&&y==floor(y), if(x^2-A*y^2==B, if(x%k5==0,
      print("k = "k"    (x, y) = ("x/k5", "y")");
      break(1)
     ))))
    )
   )
  )
 )

[TR63]

dmd, большое спасибо. Проверила при $m=7$. Точно, есть решение.
У меня Вольфрам не показывает решения. Странно. Раньше показывал всегда, если они существовали.

Просьба, если не трудно, проверить наличие решений у уравнения

$$(5k+6)x_1^2-(5k-2)y_1^2=-1$$

[dmd]

Поскольку все решения уравнения $(5k+6)x^2-(5k-2)y^2=-4$ четные, то они же уполовиненные будут решениями уравнения $(5k+6)x^2-(5k-2)y^2=-1$.

[TR63]

Да, понятно. Спасибо. (То, что чётные, можно доказать логически.)
Значит мои рассуждения были не корректны.

[TR63]

Замечание.

Но оба эти уравнения Пелля с параметром интересны мне тем, что они имеют отношение к гипотезе из темы в "Олимпиадном разделе" "По мотивам произведений последовательных натуральных чисел", и, не противореча ей, тем самым её иллюстрируют. Т.е. отсутствие экстраполяции гипотетически следовало ожидать. И численный эксперимент для этих двух уравнений оное подтвердил.