Не более пяти решений

[Dmitriy40]

nnosipov
Досчиталось до 2млрд. Файл прикрепляю (см. UPD). Всего найдено 330 пятёрок. Шестёрки и семёрка все были здесь выше, новых нет.
UPD. Обновлено.

[nnosipov]

Dmitriy40
Спасибо. Интересный эксперимент, подобных результатов еще не было.

[kotenok gav]

Хм, очень неравномерно оно идет. До миллиарда 282 пятерки, 4 шестерки, 1 семерка, а от миллиарда до двух - 48 пятерок, 1 шестерка, 0 семерок.

[Dmitriy40]

Количество решений длиной 5 вполне хорошо ложится на кривую $N_5(H)=2.78788974 H^{0.2228374}$, средняя ошибка $4.2\%$.
Запустил в 4 потока, без переделок, надеюсь завтра к вечеру досчитает до 10млрд.

[nnosipov]

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

Запустил в 4 потока, без переделок, надеюсь завтра к вечеру досчитает до 10млрд.

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

Вообще, вот такие 1-параметрические семейства диофантовых уравнений, как в этой теме, иногда удается полностью исследовать. Вот реальный пример: topic134089.html Родился он абсолютно случайно: мне захотелось опробовать один алгоритм на быстродействие, и я от балды написал этот тестовый пример. Мой студент запрограммировал алгоритм и начал считать. Через некоторое время он мне сообщил, что, наверное, в программе ошибка, поскольку она перестала выдавать нетривиальные решения. К счастью, удалось доказать, что все в порядке, просто уравнение таким случайно оказалось. Вот это уравнение:

$$xy^2+(Hx^2+1)y+x^4+1=0.$$

Но стоит здесь чуть-чуть изменить левую часть и написать, например, так

$$xy^2+(Hx+1)y+x^4+1=0$$

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

[Dmitriy40]

(Мой интерес)

Надо наверное пояснить, мне интересна не математическая сторона задачи, а программисткая: как реализовать решение уравнений, как корни быстро вычислять, как воспользоваться векторными возможностями, и как всё это уложить в процессорные команды (на языках высокого уровня не интересно, там всё относительно просто и давно известно).
Математику же я понимаю откровенно плохо, на уровне средней школы, здесь её хватает лишь чтобы решать уравнение относительно разных переменных и подстановок и пытаться получить вменяемые ограничения на перебор. Что Вы уже за меня сделали. Общие методы решения диофантовых уравнений за гранью понимания. И как-то не особо тянет разбираться.

Я тут думаю как бы прикрутить вычисление квадратного корня из плавающего числа, ведь это можно делать очень быстро (500млн/с для double и 1000млн/с для single, только корня, сопутствующие операции замедлят вычисления раза в 3), но вот точность аргумента лишь 53/23 бита и в этом засада, получаются лишь 27/12 старших битов результата из 31, а запустить метод Герона мешает отсутствие векторных команд деления целых чисел. Вот и думаю как досчитывать младшие биты, снова поразрядным взвешиванием (одновременно 8 корней) или ещё как ... И стоит ли тогда вообще заморачиваться аппаратным корнем или делать поразрядное взвешивание с самого начала, всех 32 битов результата. Или вычислять в плавающей точке младшие биты через производную и потом комбинировать два числа в один результат (и будет ли здесь нужная точность) ... Или в ряд разложить (если это отличается от предыдущего пункта) ... И во что всё это выльется по скорости. Интересно, и где-нибудь потом ещё пригодится, но задачка на хорошо подумать, несколько дней.

[nnosipov]

(Оффтоп)

Если считать те же 10 миллиардов, то можно попробовать аналитически поточнее оценить дискриминант и надеяться, что 53 бит все же хватит. Грубая оценка: $2^{53} \approx 10^{16} \approx H^{3/2}$ при $H=10^{10}$.

[Dmitriy40]

nnosipov
Не, 10млрд не интересно, они и так за пару суток точно посчитаются в 4-х доступных потоках (сейчас завершено на 71%, досчитается часам к двум ночи мск). Программу писать дольше. Надеюсь Вам не нужно много раз это дело пересчитывать.

[nnosipov]

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

Надеюсь Вам не нужно много раз это дело пересчитывать.

Нет, это я просто так заметил.

[dmd]

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

$$xy^2+(Hx+1)y+x^4+1=0$$

(Оффтоп)

Это уравнение можно переписать в гипереллиптическую форму

$((2 y + H) x + 1)^2 = 1 + 2 (H - 2) x + H^2 x^2 - 4 x^5$

и получить решения в пределах некоторой "высоты" при помощи hyperellratpoints в pari/gp.

Решения для H=-10000..10000:
H = -9844 [[0, -1], [206, 8857]]
H = -9260 [[0, -1], [-21, -1]]
H = -8866 [[0, -1], [43, 8857]]
H = -8848 [[0, -1], [-43, 8857]]
H = -7999 [[0, -1], [-20, -1]]
H = -7870 [[0, -1], [-206, 8857]]
H = -6858 [[0, -1], [-19, -1]]
H = -6473 [[0, -1], [-216, -1297]]
H = -5831 [[0, -1], [-18, -1]]
H = -4912 [[0, -1], [-17, -1]]
H = -4095 [[0, -1], [-16, -1]]
H = -3374 [[0, -1], [-15, -1]]
H = -2743 [[0, -1], [-14, -1]]
H = -2494 [[0, -1], [-125, -626]]
H = -2196 [[0, -1], [-13, -1]]
H = -1727 [[0, -1], [-12, -1]]
H = -1330 [[0, -1], [-11, -1]]
H = -1258 [[0, -1], [67, 937]]
H = -999 [[0, -1], [-10, -1]]
H = -940 [[0, -1], [14, 937]]
H = -934 [[0, -1], [-14, 937]]
H = -763 [[0, -1], [-64, -257]]
H = -728 [[0, -1], [-9, -1]]
H = -616 [[0, -1], [-67, 937]]
H = -592 [[0, -1], [43, 386]]
H = -511 [[0, -1], [-8, -1]]
H = -388 [[0, -1], [9, 386]]
H = -384 [[0, -1], [-9, 386]]
H = -342 [[0, -1], [-7, -1]]
H = -215 [[0, -1], [-6, -1]]
H = -180 [[0, -1], [-43, 386]]
H = -158 [[0, -1], [-27, -82]]
H = -124 [[0, -1], [-5, -1]]
H = -108 [[0, -1], [14, 41]]
H = -63 [[0, -1], [-4, -1]]
H = -60 [[0, -1], [9, 17]]
H = -42 [[0, -1], [3, 41]]
H = -40 [[0, -1], [-3, 41]]
H = -26 [[0, -1], [-3, -1]]
H = -18 [[0, -1], [2, 17]]
H = -16 [[0, -1], [-2, 17], [3, 2]]
H = -13 [[0, -1], [-8, -17]]
H = -10 [[0, -1], [2, 1]]
H = -7 [[0, -1], [-2, -1]]
H = -4 [[0, -1], [1, 2], [1, 1]]
H = 0 [[0, -1], [-1, -1], [-1, 2]]
H = 2 [[0, -1], [-1, -2], [-1, 1], [1, -1], [1, -2]]
H = 8 [[0, -1], [-2, 1]]
H = 9 [[0, -1], [2, -1]]
H = 12 [[0, -1], [-3, 2]]
H = 17 [[0, -1], [-2, -17], [2, -17]]
H = 26 [[0, -1], [-14, 41], [-9, 17]]
H = 28 [[0, -1], [3, -1]]
H = 47 [[0, -1], [8, -17]]
H = 65 [[0, -1], [4, -1]]
H = 82 [[0, -1], [-3, -82], [3, -82]]
H = 126 [[0, -1], [5, -1]]
H = 129 [[0, -1], [-30, -241]]
H = 217 [[0, -1], [6, -1]]
H = 239 [[0, -1], [-8, -241]]
H = 243 [[0, -1], [8, -241]]
H = 257 [[0, -1], [-4, -257], [4, -257]]
H = 322 [[0, -1], [27, -82]]
H = 344 [[0, -1], [7, -1]]
H = 353 [[0, -1], [30, -241]]
H = 513 [[0, -1], [8, -1]]
H = 626 [[0, -1], [-5, -626], [5, -626]]
H = 730 [[0, -1], [9, -1]]
H = 1001 [[0, -1], [10, -1]]
H = 1277 [[0, -1], [64, -257]]
H = 1297 [[0, -1], [-6, -1297], [6, -1297]]
H = 1332 [[0, -1], [11, -1]]
H = 1729 [[0, -1], [12, -1]]
H = 2198 [[0, -1], [13, -1]]
H = 2402 [[0, -1], [-7, -2402], [7, -2402]]
H = 2745 [[0, -1], [14, -1]]
H = 2943 [[0, -1], [-112, -3361]]
H = 3353 [[0, -1], [-30, -3361]]
H = 3369 [[0, -1], [30, -3361]]
H = 3376 [[0, -1], [15, -1]]
H = 3746 [[0, -1], [125, -626]]
H = 3779 [[0, -1], [112, -3361]]
H = 4097 [[0, -1], [-8, -4097], [8, -4097], [16, -1]]
H = 4348 [[0, -1], [-240, -6481]]
H = 4914 [[0, -1], [17, -1]]
H = 5833 [[0, -1], [18, -1]]
H = 6478 [[0, -1], [-27, -6481]]
H = 6484 [[0, -1], [27, -6481]]
H = 6562 [[0, -1], [-9, -6562], [9, -6562]]
H = 6860 [[0, -1], [19, -1]]
H = 8001 [[0, -1], [20, -1]]
H = 8614 [[0, -1], [240, -6481]]
H = 9067 [[0, -1], [216, -1297]]
H = 9262 [[0, -1], [21, -1]]
time = 1h, 19min, 7,111 ms.

gp-код:

hyph()=
{
 forstep(H=-10^4, 10^4, 1,
  V= [[0,-1]];
  S= hyperellratpoints(1 + 2*(H - 2)*'x + H^2*'x^2 - 4*'x^5, 10^6);
  for(i=1, #S,
   x= S[i][1];
   if(x&x==floor(x),
    z= S[i][2]; 
    y= ((z-1)/x-H)/2;
    if(y==floor(y),
     V= concat(V, [[x,y]])
    )
   )
  );
  if(#V>1, print("H = "H"    "V))
 )
};

[nnosipov]

dmd
Это уравнение в некотором смысле решается: можно описать все тройки $(x,y,H)$ целых чисел, ему удовлетворяющих. Но описание не слишком удобное для того, чтобы потом анализировать, какие пары $(x,y)$ бывают при заданном $H$ (в частности, непросто выяснить, сколько таких пар).

За опыты с гиперэллиптическими кривыми спасибо, можно будет заодно проверить, все ли решения на самом деле находит pari/gp (здесь опять тот случай, когда есть элементарный алгоритм решения, который при фиксированном $H$ находит все решения).

[Dmitriy40]

nnosipov
Досчиталось до 10млрд. Файл в архиве выложил в облако (сюда прикреплять архивы не дают). UPD. Обновлено.
Новых шестёрок и длиннее не найдено.
Замечено что почти все решения имеют в своём составе значения $x=\pm 1$, не имеющие таких $x$ отфильтрованы в отдельный файл. Туда попала одна из пяти известных шестёрок.
Был запущен поиск только таких решений, с $x=\pm 1$ и нечётными $H$, до 1.7трлн (дальше я не уверен в точности вычислений, лень добавлять runtime проверки), всё найденное в отдельном файле. Новых ни шестёрок ни семёрок ни длиннее всё равно не обнаружено (а была надежда, была).
В отдельный файл отфильтрованы решения с $|x|>m=1+\lfloor\sqrt[4]{|H|}\rfloor$ (т.е. найденные лишь циклом по $k$).

[nnosipov]

Dmitriy40
Большое спасибо за интересный статистический материал! Если соберусь про это где-нибудь написать, обязательно упомяну Ваш вклад. Надо подумать вообще о смысле подобных статистических экспериментов, может быть, они ценны сами по себе.

[kotenok gav]

kotenok gav в сообщении #1454637 писал(а):

Хм, очень неравномерно оно идет. До миллиарда 282 пятерки, 4 шестерки, 1 семерка, а от миллиарда до двух - 48 пятерок, 1 шестерка, 0 семерок.

От двух миллиардов до десяти - 110 пятерок, 0 шестрок, 0 семерок.

[Dmitriy40]

Интересны три вопроса:
1. Будут ли ещё встречаться решения без $x=\pm 1$. Последнее было на 344млн из 10млрд, по статистике должны были и ещё появиться, однако нету. Посчитать ещё 10млрд нечётных $H$, что ли ...
Тут ещё странное наблюдение, правда лишь для $|H|>10^7$, насколько оно адекватно далее 10млрд тоже вопрос: три корня из всех имеют одинаковый $y=\lceil\sqrt{|H|}\rceil$, а сумма двух $x$ в них даёт третий $x$. Подставив условие на $y$ в исходное уравнение получим кубическое уравнение по $x$, которое должно иметь ровно три корня, может это можно как-то аналитически использовать для получения таких $H$, позволяющих это ... Например производная должна иметь ровно два корня, т.е. строго положительный дискриминант.

2. Каково распределение по $H$ решений с большими $x$. Точнее какие $H$ для них перебирать. Все при решения $|H|>210$ имеют корни формы $y=\pm 2x \pm 1$, но вот как из этого получить $H$ пока не придумал, квадраты не точные выходят. Похоже точной формулы и нет, проверять надо интервал $x=t-1 \ldots t+1, \; H=-2(t-1)^2 \ldots -2(t+1)^2, \; t \in \mathbb{N}$. Но это условие (на $H$) бессмысленно так как слишком широко и перекрывает вообще все $H$ и можно пользоваться лишь обратным, проверять не все $x$, а лишь $x=\sqrt{|H|/2}-1 \ldots \sqrt{|H|/2}+1$, что уже легче, можно попробовать.
И вопрос бесконечна ли серия таких решений.

3. Ну и конечно почему больше нет решений длиннее 5. Ведь для пятёрок есть минимум одна бесконечная серия.

-- 16.04.2020, 15:50 --

kotenok gav
С довольно большой вероятностью найдены все пятёрки и до 1.7трлн, не думаю что там встретятся пятёрки без корней $x=\pm 1$. Но как это проверить пока думаю (см. выше вопрос 1).

-- 16.04.2020, 15:53 --

nnosipov
ИМХО статистика полезна чтобы посмотреть на поведение решений и попытаться оформить это аналитически, не сама по себе. Не всегда аппроксимацию видно по младшим/первым решениям, даже до десятков и сотен миллионов, вон например первый вопрос.

-- 16.04.2020, 16:18 --

Похоже много решений можно искать решая кубическое по $x$ уравнение при известных $H,y$. Аналитически лень, можно как-то искать корень между двумя экстремумами (нулями производной), потом делить многочлен на найденный корень и решать уже квадратное уравнение. Тут похоже перебора ни по $x$ ни по $y$ вообще не нужно, за исключением решения кубического уравнения, которое решать видимо лучше методом Ньютона или аналогичным или банальным делением отрезка по $x$ пополам.