2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Определите степень двойки
Сообщение16.10.2022, 09:49 
Аватара пользователя


22/11/13
496
Пусть $\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$.

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение16.10.2022, 13:43 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Для прояснения задачи пришлось написать программку:
Код:
{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 какой-нибудь.
Извините за оффтопик-с.

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение16.10.2022, 15:02 
Аватара пользователя


22/11/13
496
Да, все верно. Можно даже проще:
Код:
a(n)=prod(k=1, n, prod(j=1, k, j^2 + k^2))
tr(n)=valuation(n, 2)

Округление есть:
Код:
floor(3/2)

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

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение16.10.2022, 18:22 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Спасибо!
Программка мне была нужна не для подсчёта произведения, а для вывода строки
Код:
$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$, но символ косая черта не печатается:(
Это шалость, конечно, но надеюсь знатоки подтянутся к интересной теме. Теперь же наглядно всё!

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение16.10.2022, 19:04 
Аватара пользователя


07/01/16
1426
Аязьма
Хммм в этих $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)$ ммм видимо, этим путем будет трудновато до результата дойти...

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение16.10.2022, 20:25 
Аватара пользователя


07/01/16
1426
Аязьма
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$ ещё предстоит просуммировать...

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение16.10.2022, 20:50 
Аватара пользователя


22/11/13
496
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). В последней (увы) нет красивой формулы без рекурсии (а значит мое решение заодно разрешает и эту проблему).

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение17.10.2022, 00:15 
Аватара пользователя


07/01/16
1426
Аязьма
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

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение17.10.2022, 10:02 
Аватара пользователя


22/11/13
496
waxtep в сообщении #1566890 писал(а):
kthxbye
Вам удалось найти замкнутую форму, либо алгоритм, считающий быстрее, чем за $\log_2n$ чего-то там?

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

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение17.10.2022, 12:38 
Аватара пользователя


22/11/13
496
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)$ не такое уж и дорогое, т.е. время сокращается, но, опять-таки, не очень сильно.

 Профиль  
                  
 
 Re: Определите степень двойки
Сообщение17.10.2022, 23:04 
Аватара пользователя


07/01/16
1426
Аязьма
kthxbye в сообщении #1566915 писал(а):
P.S. Вычисления на PARI показывают, что множественное обращение к $\operatorname{tr}(k)$ не такое уж и дорогое, т.е. время сокращается, но, опять-таки, не очень сильно.
Наверное, так и должно быть, ведь для нее тоже очень простая рекурсивная формула. А как Вы делаете? Я попытался воспользоваться подсказкой про двоичное представление $n$, но как-то быстро запутался и ни к чему толковому не пришел

-- 17.10.2022, 23:07 --

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

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

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



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

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


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

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