Определите степень двойки

[kthxbye]

Пусть $\operatorname{tr}(n)$ это A007814, число конечных нулей в двоичной записи $n$ или же максимальная степень двойки, на которую делится $n$.

Пусть также

$$a(n)=\prod\limits_{1 \leqslant j \leqslant k \leqslant n}^{} j^2+k^2$$

Определите $\operatorname{tr}(a(n))$. Например нам задано какое-нибудь большее число, скажем $n=10^{1000}$ и требуется за небольшое время вычислить результат. Произведение получается гигантское и это не выход. Но он есть.

Подсказка: используйте двоичное представление $n$.

[gris]

Для прояснения задачи пришлось написать программку:

{for(n=1,3,k=1;print1("$a(",n,")=");
for(i=1,n,for(j=i,n,print1("(",i,"^2+",j,"^2)");k=k*(i^2+j^2)));
print1("=",k,"$"));}

Правильно ли?
$a(1)=(1^2+1^2)=2$

$a(2)=(1^2+1^2)(1^2+2^2)(2^2+2^2)=80$

$a(3)=(1^2+1^2)(1^2+2^2)(1^2+3^2)(2^2+2^2)(2^2+3^2)(3^2+3^2)=187200$
Кстати, как в ПАРИ печатать символ "\" и как делать округление до целого, типа FLOOR какой-нибудь.
Извините за оффтопик-с.

[kthxbye]

Да, все верно. Можно даже проще:

a(n)=prod(k=1, n, prod(j=1, k, j^2 + k^2))
tr(n)=valuation(n, 2)

Округление есть:

floor(3/2)

Для косой палки есть клавиша прямо над Enter, которую нажимаем мы с зажатым Shift.

[gris]

Спасибо!
Программка мне была нужна не для подсчёта произведения, а для вывода строки

$a(6)=(1^2+1^2)(1^2+2^2)(1^2+3^2)(1^2+4^2)(1^2+5^2)(1^2+6^2)(2^2+2^2)(2^2+3^2)(2^2+4^2)(2^2+5^2)(2^2+6^2)(3^2+3^2)(3^2+4^2)(3^2+5^2)(3^2+6^2)(4^2+4^2)(4^2+5^2)(4^2+6^2)(5^2+5^2)(5^2+6^2)(6^2+6^2)=40702283662588674048000000000$

которая в сообщении форума выглядит как

$a(6)=(1^2+1^2)(1^2+2^2)(1^2+3^2)(1^2+4^2)(1^2+5^2)(1^2+6^2)(2^2+2^2)(2^2+3^2)(2^2+4^2)(2^2+5^2)(2^2+6^2)(3^2+3^2)(3^2+4^2)(3^2+5^2)(3^2+6^2)(4^2+4^2)(4^2+5^2)(4^2+6^2)(5^2+5^2)(5^2+6^2)(6^2+6^2)=40702283662588674048000000000$
ибо вручную печатать раскрытый текст произведения утомительно. Вот я хотел вставить нечто вроде

{print("$2\cdot 3$")}

для отображения как $2\cdot 3$, но символ косая черта не печатается:(
Это шалость, конечно, но надеюсь знатоки подтянутся к интересной теме. Теперь же наглядно всё!

[waxtep]

Хммм в этих $j^2+k^2$ много коварства... Можно подметить, что

$$\operatorname{tr}(a(n))-\operatorname{tr}(a(n-1))=\sum\limits_{m=0}^{\lceil{n/2}\rceil-1}\operatorname{tr}(n^2+(n-2m)^2)$$

Для нечетного $n=2p+1$ эта суммочка равна $p+1$, поскольку каждое слагаемое в ней единица; для немножко четного $n=2(2p+1)$ тоже можно посчитать, это будет $5p+3$, т.к. под знаком суммы чередуются двойки и тройки; для ещё более чётного $n=4(2p+1)$ ммм видимо, этим путем будет трудновато до результата дойти...

[waxtep]

waxtep в сообщении #1566870 писал(а):

для ещё более чётного $n=4(2p+1)$ ммм видимо

Не проверял аккуратно, но похоже на $13p+7$; и тогда для $n$, делящегося на все большие степени двойки, $8(2p+1),16(2p+1),32(2p+1)\ldots$ можно предположить значение суммы $29p+15, 61p+31,125p+63\ldots$ и т.д. А потом всю эту гадость красоту, похожую на $2n-3p-1$ ещё предстоит просуммировать...

[kthxbye]

waxtep в сообщении #1566873 писал(а):

waxtep в сообщении #1566870 писал(а):

для ещё более чётного $n=4(2p+1)$ ммм видимо

Не проверял аккуратно, но похоже на $13p+7$; и тогда для $n$, делящегося на все большие степени двойки, $8(2p+1),16(2p+1),32(2p+1)\ldots$ можно предположить значение суммы $29p+15, 61p+31,125p+63\ldots$ и т.д. А потом всю эту гадость красоту, похожую на $2n-3p-1$ ещё предстоит просуммировать...

Похоже, что все действительно так. Существование паттерна - это уже что-то красивое. Раз нам предстоит суммировать $p$, то можно, например увеличить его на единичку (A003602), а потом уже суммировать (A174989). В последней (увы) нет красивой формулы без рекурсии (а значит мое решение заодно разрешает и эту проблему).

[waxtep]

kthxbye
Вам удалось найти замкнутую форму, либо алгоритм, считающий быстрее, чем за $\log_2n$ чего-то там? Так-то получается такая загогулина:

$$\operatorname{tr}(a(n))=n^2+3n-3f(n), f(n)=\frac{\lceil{n/2}\rceil\left(\lceil{n/2}\rceil+1\right)}2+f(\lfloor{n/2}\rfloor),f(1)=1$$

т.е. $f$ - это та самая A174989

[kthxbye]

waxtep в сообщении #1566890 писал(а):

kthxbye
Вам удалось найти замкнутую форму, либо алгоритм, считающий быстрее, чем за $\log_2n$ чего-то там?

Если ничего не напутал, то получается, что мой алгоритм считает за $\operatorname{wt}(n)$ (A000120) чего-то там.

[kthxbye]

waxtep, а вообще-то я много раз обращаюсь к различным $k$ и вычисляю $\operatorname{tr}(k)$. Каждое из таких вычислений стоит соответственно $\operatorname{tr}(k)$ чего-то там.

Можно сказать, что у меня тоже $\left\lfloor\log_2 n\right\rfloor$ чего-то там, но я работаю не с $f(n)$, а с $g(n)=3f(n)-\frac{n(n+3)}{2}$ (A264596). На страничке последовательности приведена удобная формула, а также гипотеза, которая и стала причиной создания этой темы.

Однако $g(n)$ я вычисляю чуть-чуть похитрее. Разница в скорости, правда, совсем небольшая.

P.S. Вычисления на PARI показывают, что множественное обращение к $\operatorname{tr}(k)$ не такое уж и дорогое, т.е. время сокращается, но, опять-таки, не очень сильно.

[waxtep]

kthxbye в сообщении #1566915 писал(а):

P.S. Вычисления на PARI показывают, что множественное обращение к $\operatorname{tr}(k)$ не такое уж и дорогое, т.е. время сокращается, но, опять-таки, не очень сильно.

Наверное, так и должно быть, ведь для нее тоже очень простая рекурсивная формула. А как Вы делаете? Я попытался воспользоваться подсказкой про двоичное представление $n$, но как-то быстро запутался и ни к чему толковому не пришел

-- 17.10.2022, 23:07 --

А, впрочем, вчитался и кажется понял