Блог пользователя M.Mahdi

Автор M.Mahdi, 10 лет назад, По-английски

Hi! :)
What is the best upper bound for number of divisors of some natural number n?
I can't find any bound better than :(

  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

n^1/3 are often used bound

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится +43 Проголосовать: не нравится

As far as I remember, it's . But you can use in practice.

UPD: link and discussion on Codeforces (Russian)

»
10 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

T0RRES and yeputons, thank you both!

»
10 лет назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

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.

»
10 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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.

»
10 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Gassa, hashlife, I_love_Tanya_Romanova. Thank you guys! :)
I got exactly what i was looking for.

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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}})$$$?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится

    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.