Обсуждение и разбор марафонских задач

[VAL]

Yadryara в сообщении #910054 писал(а):

VAL в сообщении #909787 писал(а):

Надеюсь, что Антон Никонов дополнит соответствующие статьи явными формулами.
Почему именно Антон? Потому что только он нашел соответствующие явные формулы.

Прошу Вас побыстрее сообщить, какие именно формулы нужны. Ибо с момента их вывода прошло уже два месяца и восстановить ход решения мне сейчас затруднительно. А позже будет ещё сложнее.

Дпя количества целочисленных остроугольных треугольников с большей стороной, равной $n$ (не превосходящей $n$). И то же для тупоугольных.

Цитата:

VAL в сообщении #909787 писал(а):

Я их и добавил. Но при этом вычел такое число баллов за традиционное нежелание приводить пояснения и обоснования.

Видимо, пропущено "же". Такое же. Миллиард начислил, биллион вычел

Конечно (же)!

Цитата:

Мне, например, не нравится, что шаг $s$ равен 5-ти, а не единице. Одна попытка перенормировать мне не понравилась, а другие я не удосужился осуществить.

Конечно, лучше перейти к единичному шагу.

Цитата:

Помнится, смотрел на диапазоны возможных значений $a$ и $b$, и кое-что понял...

А вдруг у меня ноу-хау есть

Срочно проверьте эту гипотезу!

[kknop]

Что-то я про формулу недопонял. В последовательности OEIS, отвечающей за число пифагоровых троек, нет никаких точных формул, и мое общее понимание структуры этой задачи говорит, что их и не должно быть, ибо результат зависит от числа представлений гипотенузы в виде k(m^2+n^2) с натуральными kmn. Если бы у нас волшебным образом были формулы для остро (О) и тупо (Т) угольных треугольников у которых большая сторона не превосходит n, то из предыдущей задачи и очевидного равенства (О)+(Т)+(Пифагоровы)=(Все) мы немедленно бы нашли число пифагоровых троек. Да, пусть не в замкнутом виде, а через суммы и целые части, но все равно это как-то сомнительно. Это все равно что сказать, что такой же техникой мы научились число на множители раскладывать...

[Deggial]

kknop в сообщении #910062 писал(а):

k(m^2+n^2) с натуральными kmn

kknop, замечание за неоформление формул $\TeX$ом.

[Yadryara]

kknop

Да, в том-то и дело, что я не помню, выводил ли я "волшебные" формулы для $O$ и $T$ отдельно или сразу ухитрился найти $T-O$. Теперь сложно будет разобраться. У меня аж 70 вариантов программы и куча всякой статистики.

Что мы сейчас имеем. Обозначения:

$O$ — количество остроугольных, большая сторона которых не превышает $n$.
$P$ — количество прямоугольных, большая сторона которых не превышает $n$.
$T$ — количество тупоугольных, большая сторона которых не превышает $n$.
$V$ — общее количество треугольников, большая сторона которых не превышает $n$.
$r$ — разность между $T$ и $O$, которую можно вычислить по моей формуле.

$$O + P + T = V}$$

Адаптированная формула Cecilia Rossiter:

$$V(n) = \frac{4n^3 + 18 n^2 + 20n + 3 - 3(-1) ^ n}{48}$$

$$r = T - O$$

откуда

$$V - r = 2O + P$$

и

$$V + r = 2T + P$$

Видимо, придётся разбираться подольше, чтобы понять, что ещё полезного можно найти.

[VAL]

kknop в сообщении #910062 писал(а):

Что-то я про формулу недопонял. В последовательности OEIS, отвечающей за число пифагоровых троек, нет никаких точных формул

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

Цитата:

и мое общее понимание структуры этой задачи говорит, что их и не должно быть, ибо результат зависит от числа представлений гипотенузы в виде k(m^2+n^2) с натуральными kmn. Если бы у нас волшебным образом были формулы для остро (О) и тупо (Т) угольных треугольников у которых большая сторона не превосходит n, то из предыдущей задачи и очевидного равенства (О)+(Т)+(Пифагоровы)=(Все) мы немедленно бы нашли число пифагоровых троек. Да, пусть не в замкнутом виде, а через суммы и целые части, но все равно это как-то сомнительно. Это все равно что сказать, что такой же техникой мы научились число на множители раскладывать...

Ну... пол (в смысле, целая часть) - это сила! Что подтверждвается, например, известной формулой простого числа:

$$p_{n+1}=\left[1-log_2\left(\frac12+\sum_{r=1}^n \ \sum_{1\le i_1 < \dots < i_r \le n}\frac{(-1)^r}{2^{p_{i_1}\cdots p_{i_r}}-1}\right)\right]$$

.

Но, вообще-то, у меня тоже возникли сомнения. Но ведь работает!
Вначале я проверил ее только на участке, приведенном Антоном. Сейчас распространил на все $n$ до 500 (пока перебор тормозить не начал).
Ни одного расхождения!

[Yadryara]

VAL в сообщении #910058 писал(а):

Дпя количества целочисленных остроугольных треугольников с большей стороной, равной $n$ (не превосходящей $n$). И то же для тупоугольных.

Ну вот пока для тупоугольных:

$$T(n) = \sum_{c=1}^n \left( k(k + \frac{1+(-1)^c}2) + \sum_{j=1}^{(1 - \frac{\sqrt2}2)c} \lfloor\sqrt{2jc - j^2 - 1} - j\rfloor\right)$$

, где

$$k =\lfloor\frac{2c(\sqrt{2} - 1) + 1-(-1)^c}4\rfloor $$

и

$c$ — по-прежнему наибольшая сторона треугольника.

Если $c=n$, то нужно просто взять ту часть формулы, которая в огромных скобках.

[VAL]

Yadryara в сообщении #910457 писал(а):

Ну вот пока для тупоугольных:

$$T(n) = \sum_{c=1}^n \left( k(k + \frac{1+(-1)^c}2) + \sum_{j=1}^{(1 - \frac{\sqrt2}2)c} \lfloor\sqrt{2jc - j^2 - 1} - j\rfloor\right)$$

, где

$$k =\lfloor\frac{2c(\sqrt{2} - 1) + 1-(-1)^c}4\rfloor $$

и

$c$ — по-прежнему наибольшая сторона треугольника.

Если $c=n$, то нужно просто взять ту часть формулы, которая в огромных скобках.

У меня получилось (по этой формуле), что для $c=4$ нет треугольников.
А на самом деле, $(2,3,4)$ подходит.

[Yadryara]

VAL в сообщении #910532 писал(а):

У меня получилось (по этой формуле), что для $c=4$ нет треугольников.
А на самом деле, $(2,3,4)$ подходит.

Так это непосредственной подстановкой можно проверить:

$$k =\lfloor\frac{2\cdot4(\sqrt{2} - 1) + 1-(-1)^4}4\rfloor = 0$$

$$T(4) = 0\cdot(0 + \frac{1+(-1)^4}2) + \sum_{j=1}^{(1 - \frac{\sqrt2}2)\cdot4} \lfloor\sqrt{2j\cdot4 - j^2 - 1} - j\rfloor\right)$$

$$T(4) = \sum_{j=1}^{1} \lfloor\sqrt{2j\cdot4 - j^2 - 1} - j\rfloor\right)$$

$$T(4) = \sum_{j=1}^{1} \lfloor\sqrt{2\cdot1\cdot4 - 1^2 - 1} - 1\rfloor\right)$$

$$T(4) = \sum_{j=1}^{1} \lfloor\sqrt6 - 1\rfloor\right) = 1$$

Вот он, единственный тупоугольный треугольник при $c=4$.

Что-нибудь ещё не сошлось? Я проверял до $n=100$.

[VAL]

Yadryara в сообщении #910558 писал(а):

VAL в сообщении #910532 писал(а):

У меня получилось (по этой формуле), что для $c=4$ нет треугольников.
А на самом деле, $(2,3,4)$ подходит.

Так это непосредственной подстановкой можно проверить:
[...]
Что-нибудь ещё не сошлось? Я проверял до $n=100$.

Нашел ошибку у себя в реализации формулы.
Теперь всё сходится.
Проверял до 600.

[Yadryara]

И для остроугольных:

$$O(n) = \sum_{c=1}^n \sum_{j=0}^{(1 - \frac{\sqrt2}2)c} \left(c - j - \lfloor\sqrt{2jc - j^2}\rfloor\right)$$

$c$ — по-прежнему наибольшая сторона треугольника.

Если $c=n$, то нужно просто взять только правую сумму.

[VAL]

Yadryara в сообщении #910705 писал(а):

И для остроугольных:

$$O(n) = \sum_{c=1}^n \sum_{j=0}^{(1 - \frac{\sqrt2}2)c} \left(c - j - \lfloor\sqrt{2jc - j^2}\rfloor\right)$$

$c$ — по-прежнему наибольшая сторона треугольника.

Если $c=n$, то нужно просто взять только правую сумму.

А эта даже вполне компактная!

Кстати, тем временем в OEIS уже опубликовали соответствующие последовательности: A247586, A247587, A247588, A247589.

[Yadryara]

kknop в сообщении #910062 писал(а):

В последовательности OEIS, отвечающей за число пифагоровых троек, нет никаких точных формул, и мое общее понимание структуры этой задачи говорит, что их и не должно быть, ибо результат зависит от числа представлений гипотенузы в виде k(m^2+n^2) с натуральными kmn.

A046080 — более ранняя последовательность пифагоровых троек для $c=n$. И приведены 5 формул.

[Yadryara]

Ну и для прямоугольных. Если гипотенуза равна $n$, то можно посчитать количество пифагоровых троек $P(n)$ по формуле:

$$P(n) = \frac{2n^2 + 4n + 1 - (-1) ^ n} 8 - ( k(k + \frac{1+(-1)^n}2) +(w + 1)(w - n) - \sum_{j=1}^w(\left \lfloor\sqrt{x - 1}\rfloor-\lfloor\sqrt{x}\rfloor\right)$$

Где

$k =\lfloor\frac{2n(\sqrt{2} - 1) + 1-(-1)^n}4\rfloor$

$w= \lfloor(1 - \frac{\sqrt2}2)n\rfloor$

$x=2jn - j^2$


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

Возможно, формулу можно будет упростить и она совпадёт с уже известными.

Кроме того, с недавних пор стало многое известно ещё и про эйлеровы четвёрки. Но это здесь оффтоп.

[Yadryara]

Да. Очень многое сократилось.

$$P(n) = \sum_{j=1}^{(1 - \frac{\sqrt2}2)n}(\left \lfloor\sqrt{x}\rfloor-\lfloor\sqrt{x - 1}\rfloor\right)$$

Где

$x=2jn - j^2$

Сколько раз $x$ равен точному квадрату, столько и пифагоровых троек.

[VAL]

Yadryara в сообщении #911286 писал(а):

Да. Очень многое сократилось.

$$P(n) = \sum_{j=1}^{(1 - \frac{\sqrt2}2)n}(\left \lfloor\sqrt{x}\rfloor-\lfloor\sqrt{x - 1}\rfloor\right)$$

Где

$x=2jn - j^2$

Сколько раз $x$ равен точному квадрату, столько и пифагоровых троек.

Ну да. В таком все стало прозрачным.
Даже обидно, что таинство пропало

Так, как насчет размещения формул в OEIS?