2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Подход к задаче "первые 100" без уравнения Пелля.
Сообщение06.05.2019, 20:13 


03/03/12
1380
 i  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)$ должно делиться на четыре. Если будут по формулам получатся только натуральные решения, то это и будет гипотетический фильтр.
Я не привела промежуточные вычисления, т.к. это громоздко (там простые преобразования: раскрытие скобок и т.д.). Проверила на примере. Формулы работают. Но перепроверка не помешает.

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение07.05.2019, 08:42 


16/08/05
1146
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$. В том и прелесть алгоритма решения уравнений Пелля, что он исключительно полиномиален по времени вычислительных затрат, даже для очень больших минимальных решений.

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение07.05.2019, 12:53 


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

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение07.05.2019, 15:49 


03/03/12
1380
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)$ числа из примитивной пифагоровой тройки.

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение08.05.2019, 15:32 


03/03/12
1380
TR63 в сообщении #1391471 писал(а):
при $k=41$ Вольфрам не даёт разложение на разность квадратов.


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

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

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение22.05.2019, 09:28 


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

Да, полученные формулы для нахождения полуцелых при больших $(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)$.

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

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение21.08.2019, 11:22 


03/03/12
1380
Замечание.
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)$ условиях, т.к. минимумов не может быть более одного.
Интересно, существует ли контрпример к такой задаче?

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение22.08.2019, 15:49 


03/03/12
1380
TR63 в сообщении #1411379 писал(а):
при указанных для $(m)$ условиях, т.к. минимумов не может быть более одного.

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

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение30.08.2019, 09:00 


03/03/12
1380
Формула $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$ в этом уравнении Пелля с параметром.

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение30.08.2019, 16:56 


16/08/05
1146
Минимальные решения уравнения $(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)
     ))))
    )
   )
  )
)

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение30.08.2019, 17:34 


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

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

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

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение30.08.2019, 17:45 


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

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение30.08.2019, 17:55 


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

 Профиль  
                  
 
 Re: Подход к задаче "первые 100" без уравнения Пелля.
Сообщение31.08.2019, 10:41 


03/03/12
1380
Замечание.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group