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

[Dmitriy40]

Нашлась ещё шестёрка:

H=-1160117659, m=185, Q=184, n=6: (1312,34111) (-131,-34061) (0,-1) (1,-34061) (1,34060) (130,-34061)

Досчитано до 1.2млрд.
До миллиарда найдено 282 пятёрки, последняя:

H=-992281499, m=178, Q=176, n=5: (-126,-31501) (0,-1) (1,-31501) (1,31500) (125,-31501)

Покажу "непарные" пятёрки, которые выбиваются из условия $-m \leqslant x \leqslant m$ (фильтровал руками, мог промахнуться):

Первые и так известны.
H=-1055, m=6, Q=5, n=5: (-24,47) (22,-45) (0,-1) (1,-33) (1,32)
H=-2447, m=8, Q=6, n=5: (-36,71) (34,-69) (-1,50) (-1,-49) (0,-1)
H=-4229, m=9, Q=7, n=5: (25,74) (-47,93) (45,-91) (0,-1) (3,65)
H=-4419, m=9, Q=7, n=5: (-46,-93) (48,95) (-1,67) (-1,-66) (0,-1)
H=-8189, m=10, Q=9, n=5: (-65,129) (63,-127) (0,-1) (1,-91) (1,90)
H=-11553, m=11, Q=9, n=5: (-75,-151) (77,153) (-1,108) (-1,-107) (0,-1)
H=-22051, m=13, Q=11, n=5: (-104,-209) (106,211) (0,-1) (1,-149) (1,148)
H=-35909, m=14, Q=13, n=5: (-135,269) (133,-267) (0,-1) (1,-190) (1,189)
H=-64083, m=16, Q=15, n=5: (53,264) (-178,-357) (180,359) (0,-1) (15,254)
H=-83229, m=17, Q=17, n=5: (-205,409) (203,-407) (-1,289) (-1,-288) (0,-1)
H=-150153, m=20, Q=19, n=5: (-273,-547) (275,549) (-1,388) (-1,-387) (0,-1)
H=-278255, m=23, Q=23, n=5: (-374,747) (372,-745) (0,-1) (1,-528) (1,527)
H=-392499, m=26, Q=24, n=5: (-442,-885) (444,887) (-1,627) (-1,-626) (0,-1)
H=-749089, m=30, Q=28, n=5: (-611,-1223) (613,1225) (0,-1) (1,-866) (1,865)
H=-2827439, m=42, Q=40, n=5: (-1190,2379) (1188,-2377) (-1,1682) (-1,-1681) (0,-1)
H=-5100819, m=48, Q=47, n=5: (-1596,-3193) (1598,3195) (-1,2259) (-1,-2258) (0,-1)
H=-9452549, m=56, Q=54, n=5: (-2175,4349) (2173,-4347) (0,-1) (1,-3075) (1,3074)
H=-13333449, m=61, Q=59, n=5: (-2581,-5163) (2583,5165) (-1,3652) (-1,-3651) (0,-1)
H=-25446979, m=72, Q=70, n=5: (-3566,-7133) (3568,7135) (0,-1) (1,-5045) (1,5044)
H=-41441405, m=81, Q=79, n=5: (-4553,9105) (4551,-9103) (0,-1) (1,-6438) (1,6437)
H=-96049797, m=99, Q=99, n=5: (-6931,13861) (6929,-13859) (-1,9801) (-1,-9800) (0,-1)
H=-173277729, m=115, Q=114, n=5: (-9307,-18615) (9309,18617) (-1,13164) (-1,-13163) (0,-1)
H=-218535503, m=122, Q=121, n=5: (5587,-16762) (-21,14783) (-11,14783) (0,-1) (32,14783)
H=-321108479, m=134, Q=133, n=5: (-12672,25343) (12670,-25341) (0,-1) (1,-17920) (1,17919)
H=-344583203, m=137, Q=135, n=5: (1243,-18646) (-21,18563) (-13,18563) (0,-1) (34,18563)
H=-452944803, m=146, Q=145, n=5: (-15048,-30097) (15050,30099) (-1,21283) (-1,-21282) (0,-1)
H=-864448201, m=172, Q=170, n=5: (-20789,-41579) (20791,41581) (0,-1) (1,-29402) (1,29401)

-- 14.04.2020, 15:31 --

Ещё наблюдение, собственно это и из графика $Q(m)$ видно: для $m>3$ выполняется $Q \leqslant m$, т.е. нет необходимости считать $Q$, можно вместо него брать просто $m$ (при большом желании увеличив на 1 ради большего спокойствия, на скорость это практически не повлияет).

[dmd]

del

[kotenok gav]

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

H = -175481375 [[0, -1], [-9, 13247], [-23, 13247], [32, 13247], [9366, -18733], [-9368, 18735]]

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

H=-175481375, m=116, Q=114, n=6: (-9368,18735) (9366,-18733) (-23,13247) (-9,13247) (0,-1) (32,13247)

[Dmitriy40]

Эта шестёрка была найдена ещё утром.
Спасибо кстати, удалил шестёрки из списка пятёрок, до этого таки пропустил.

[nnosipov]

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

т.е. нет необходимости считать $Q$

Да, так и есть. Вчера еще хотел написать, но отвлекся и забыл В принципе, алгоритм будет корректно работать при любом $m$ и соответствующем ему $Q(m)$, но нам выгодно минимизировать сумму $2m+2Q(m)$ (это тотальное количество решаемых квадратных уравнений). В данном случае этот минимум будет при $m \sim |H|^{1/4}$, при этом значении $m$ имеем $Q(m) \sim |H|^{1/4}$.

[Dmitriy40]

nnosipov
Ещё интересное наблюдение, вплоть до $H<10^8$ нет ни одного решения длиной 4 (или более) с чётным $H$. Может имеет смысл проверять лишь нечётные $H$? Это ведь вдвое быстрее.
Я надеялся и ещё на какие-нибудь закономерности в $H$.
$H=-2t^2+3$ надёжной не кажется (хотя бы потому что не все шестёрки находит), тоже проверил далеко и ничего интересного не нашёл.

Вычисление $Q$ на скорость не влияет, лишь на код программы. Увеличение величины перебора тоже совсем незначительно, тем более для больших $H$.

[nnosipov]

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

Нашлась ещё шестёрка

Да, негусто. Итого имеем 4 шестерки.

С пятерками: есть такие, для которых $H \neq -2t^2+3$. Из указанных Вами это

{-864448201, -452944803, -344583203, -218535503, -173277729, -25446979, -13333449, -5100819, -749089, -392499, -150153, -64083, -22051, -11553, -4419}

[Dmitriy40]

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

С пятерками: есть такие, для которых $H \neq -2t^2+3$.

Это есть даже и с шестёрками, для $H=-649;-854699;-1160117659$.

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

Итого имеем 4 шестерки.

Простите, пять:

H=-69, m=3, Q=3, n=6: (-7,13) (5,-11) (-1,9) (-1,-8) (0,-1) (2,-9)
H=-649, m=6, Q=4, n=6: (-17,-35) (19,37) (-3,26) (0,-1) (1,-26) (1,25)
H=-854699, m=31, Q=29, n=6: (349,-1048) (-22,-925) (0,-1) (1,-925) (1,924) (21,-925)
H=-175481375, m=116, Q=114, n=6: (-9368,18735) (9366,-18733) (-23,13247) (-9,13247) (0,-1) (32,13247)
H=-1160117659, m=185, Q=184, n=6: (1312,34111) (-131,-34061) (0,-1) (1,-34061) (1,34060) (130,-34061)

[nnosipov]

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

Ещё интересное наблюдение, вплоть до $H<10^8$ нет ни одного решения длиной 4 (или более) с чётным $H$. Может имеет смысл проверять лишь нечётные $H$? Это ведь вдвое быстрее.
Я надеялся и ещё на какие-нибудь закономерности в $H$.
$H=-2t^2+3$ надёжной не кажется (хотя бы потому что не все шестёрки находит), тоже проверил далеко и ничего интересного не нашёл.

Честно говоря, я не знаю, что дальше делать. Какой-то хаос, хотя и ожидаемый, но все равно неприятный. Насчет смотреть только нечетные $H$ --- можно, конечно, попробовать, но гарантий успеха никаких. Наука в моем лице может только развести руками.

Я бы зафиксировал то, что уже имеем: статистику чисел решений до $10^9$ (или до того момента, пока Вам не надоест). Статистика типа той, что у моих школьников была до $10^7$. Вы не могли бы такую таблицу предоставить?

-- Вт апр 14, 2020 21:39:16 --

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

Простите, пять:

Окей, пять.

-- Вт апр 14, 2020 21:42:30 --

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

Это есть даже и с шестёрками, для $H=-649;-854699;-1160117659$.

Пока я понял, как генерировать бесконечно много четверок. Пятерки и, тем более, шестерки --- темное дело.

[Dmitriy40]

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

Вы не могли бы такую таблицу предоставить?

Я в файл вывожу только решения длиной 5 и более, четвёрки и менее никак не учитываются и теряются. Будет ли Вам полезна такая обрезанная таблица? Ну или могу добавить накопление лишь количества решений каждой длины и за сутки досчитать пропущенные данные. Пока досчиталось до полутора миллиардов, файл 26К текста. К ночи (часов через 5) досчитается до двух миллиардов, тогда наверное прикреплю его сюда в тему, сейчас предел какой-то некрасивый.

[nnosipov]

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

-- Вт апр 14, 2020 21:56:42 --

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

К ночи (часов через 5) досчитается до двух миллиардов

Да, давайте остановимся здесь, чтобы не гонять попусту.

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

Будет ли Вам полезна такая обрезанная таблица?

Любая будет, конечно, не хочу Вас обременять лишней работой. Но программку пока не удаляйте, вдруг потом как-нибудь поделитесь опытом.

[Dmitriy40]

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

Dmitriy40
круто!

Ну, вообще-то 2/3 работы сделали Вы, предоставив практически готовый алгоритм счёта, я лишь реализовал его на ассемблере. И кстати на С/С++ скорость была лишь незначительно меньше (может в полтора-два раза), как и на почти любом компилируемом языке, даже на PARI/GP если его скомпилить. Вот если б задействовать векторное AVX (придётся перейти к плавающей точке), то да, был бы и мой вклад. Пока же поделимся крутизной честно.

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

Да, давайте остановимся здесь, чтобы не гонять попусту.

Да в общем не жалко, это годами жалко, а на недельку запустить проблемы нет, по идее дней за 4-6 должно досчитаться до 10млрд. Я подумываю запустить в 4 потока, тогда за разумное время можно наверное досчитать до 100млрд. А если получится прикрутить AVX (это уже чисто ради интереса, как такие вещи делать векторно в плавающей точке), то и до триллиона, за пару-тройку недель, правда если точность вычислений не пострадает, это вопрос.

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

Любая будет, конечно,

Да я спрашивал надо ли доделывать программу до выдачи полной статистики по всем решениям и досчитывать пропущенные данные или Вам хватит и лишь решений длиной 5 и более, вроде четвёрки и сами можете генерировать или хотя бы оценивать статистику. Мне просто эта статистика не кажется интересной, но как Вам не знаю. Это доделать собственно несложно, самое трудное придумать куда и как её выдавать.
PS. Программы, писанные более пары часов, не удаляю никогда. Как и результаты если они считались часы.

[dmd]

Большинство решений это либо $y=\pm1\pm\left\lfloor{\sqrt{|H|}\right\rfloor$, либо $x=\pm1\pm\left\lfloor\sqrt{\dfrac{|H|+3}{2}}\right\rfloor$.

Но для H=-854699 есть (349,-1048), которое в эту схему не укладывается.

[nnosipov]

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

Мне просто эта статистика не кажется интересной, но как Вам не знаю.

Да бог с ней, ограничимся тем, что есть. В любом случае большое спасибо! Всегда приятно посмотреть на профессиональную работу. (Вот бы мои студенты так: вечером попросил что-то сделать, утром уже готово --- мечта ).

По поводу вычислений с плавающей точкой: это очень стоящая идея, с разных точек зрения. Квадратные уравнения --- это еще ерунда, тут хотя бы с математикой все ясно. А как быстро решать кубические и далее уравнения в целых числах? Можем мы быстро (и доказательно!) решить миллиард кубических уравнений с не очень большими коэффициентами в целых числах? Вот интересный вопрос. Но об этом я попозже Вам напишу в ЛС, как созрею. Там, думается, большой простор в программистких решениях, возможно Вам будет интересно.

-- Вт апр 14, 2020 23:06:42 --

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

Большинство решений это либо $y=\pm1\pm\sqrt{|H|}$, либо $x=\pm1\pm\sqrt{\dfrac{|H|+3}{2}}$.

Про второе более-менее понятно, а вот первое надо обдумать, спасибо.

Внезапно вспомнил, что у меня завтра 2 лекции, а теперь к лекциям надо готовиться :) Так что на время пропаду.

[Dmitriy40]

(Про уравнения большей степени)

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

А как быстро решать кубические и далее уравнения в целых числах? Можем мы быстро (и доказательно!) решить миллиард кубических уравнений с не очень большими коэффициентами в целых числах? Вот интересный вопрос.

Кубический корень извлечь точно можем. У меня написана процедура извлечения кубического корня из 64 битного числа, т.е. до $2^{64} \approx 1.8\cdot10^{19}$, работает ровно так же как и квадратный корень, поразрядное взвешивание, причём скорость должна быть чуть выше квадратного т.к. меньше битов надо взвесить (21 против 32).
А вот с плавающей точкой будет беда, стандартной процессорной команды извлечения кубического корня нет, как и больших степеней, а делать через логарифм это страшный гемор и тормоза и не реализовано векторно в AVX. Скорее всего будет быстрее тем же методом Ньютона корень найти, там ведь хватит 5-6 итераций.
Решить же уравнение ... Если без математики, перебором, то всё зависит от величины возможных решений, если миллиард уравнений да по сотне значений аргумента ... В принципе можно, но как-то грустно. Уж лучше вспомнить математику, что кубическая парабола всегда идёт из минус бесконечности в плюс бесконечность и искать локальные максимумы и минимумы (про производной), а уж потом между ними методом Ньютона корни, которые уже проверять на целочисленность. Тут главное не забыть про выделенные случаи (корней меньше трёх). И про точность вычислений.
Как-то аналогично можно и четвёртую степень решить: вычисление нулей второй производной, потом методом Ньютона нули первой производной, а потом между ними и нули самой функции. Ну или сразу методом Ньютона искать нули функции, правда что там со сходимостью надо следить, или сменить метод на секущих или ещё что.
Про ещё большие степени быстрых методов не вижу, только общие.
В итоге тут везде больше математики, чем программирования.