Hi! :)
What is the best upper bound for number of divisors of some natural number n?
I can't find any bound better than 
:(
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 06.11.2024 00:05:06 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
n^1/3 are often used bound
As far as I remember, it's
. But you can use 
in practice.
UPD: link and discussion on Codeforces (Russian)
T0RRES and yeputons, thank you both!
Regarding the number of divisors, a useful thing for programming contests is to search OEIS for "1344 maximal divisors", or just memorize the sequence numbers for the maximal number of divisors and also the smallest and largest n-digit integers that have the appropriate number of divisors. The two latter sequences are sometimes useful in test cases.
The number is 1344 for integers up to 109 and 103 680 for integers up to 1018.
Well, an exact answer is always better than an approximation.
http://ideone.com/JNRMsQ
This calculates the maximum number of divisors of any positive integer less than n, given n as input. n <= 10^18.
Hope this helps.
.
Maximum number of divisors of any positive integer less than n. 72 indeed has 12 divisors
.
This calculates the maximum number of divisors of any positive integer less than n, given n as input. n <= 10^18.
What about this do you not understand?
.
Uhm... Basically everything. The code wasn't intended to answer your query. Before asking, why not google? The first answer I got was this
And here is a list of first few hundreds of highly composite numbers:)
Gassa, hashlife, I_love_Tanya_Romanova. Thank you guys! :)
I got exactly what i was looking for.
if n=(p1^a1)(p2^a2)..(pk^ak)where pi are different primes then n have exactly (a1+1)(a2+1)(ak+1)different divisors but p1>=2,p2>3 etc, so a1<=log2(n), a2<=log3(n/p1^a1)=log3(n)-a1*log3(2), a3<=log5(n)-a1*log5(2)-a2*log5(3),.. and O(n^eps)as result
I understood why $$$2\sqrt{n}$$$ is an upper bound. But can somebody explain the reasoning behind the upper bound being $$$\mathcal{O}(n^{\frac{1}{3}})$$$?
It's not really true in a way you would expect. That statement with $$$n^\frac{1}{3}$$$ should be taken with a grain of salt. It is a mere heuristic that tells you what is more or less the number you could expect if we are talking about numbers that appear within competitive programming, e.g. $$$\le 10^{18}$$$. There is no connection between $$$n^\frac{1}{3}$$$ and maxium number of divisors other than they are of similar order of magnitude for numbers of that size.