2014 dxdy logo

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

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




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


22/11/13
434
Пусть $\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
14175
Для прояснения задачи пришлось написать программку:
Код:
{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
434
Да, все верно. Можно даже проще:
Код:
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
14175
Спасибо!
Программка мне была нужна не для подсчёта произведения, а для вывода строки
Код:
$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
1261
Аязьма
Хммм в этих $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
1261
Аязьма
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
434
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
1261
Аязьма
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
434
waxtep в сообщении #1566890 писал(а):
kthxbye
Вам удалось найти замкнутую форму, либо алгоритм, считающий быстрее, чем за $\log_2n$ чего-то там?

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

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


22/11/13
434
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
1261
Аязьма
kthxbye в сообщении #1566915 писал(а):
P.S. Вычисления на PARI показывают, что множественное обращение к $\operatorname{tr}(k)$ не такое уж и дорогое, т.е. время сокращается, но, опять-таки, не очень сильно.
Наверное, так и должно быть, ведь для нее тоже очень простая рекурсивная формула. А как Вы делаете? Я попытался воспользоваться подсказкой про двоичное представление $n$, но как-то быстро запутался и ни к чему толковому не пришел

-- 17.10.2022, 23:07 --

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

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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