M.Mahdi's blog

Upper bound for number of divisors
By M.Mahdi, 10 years ago, In English

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

  • Vote: I like it
  • +43
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

n^1/3 are often used bound

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +43 Vote: I do not like it

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

UPD: link and discussion on Codeforces (Russian)

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

T0RRES and yeputons, thank you both!

→ Reply
»
10 years ago, # |
  Vote: I like it +60 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it -18 Vote: I do not like it

    .

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Maximum number of divisors of any positive integer less than n. 72 indeed has 12 divisors

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -13 Vote: I do not like it

        .

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it -13 Vote: I do not like it

            .

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              Uhm... Basically everything. The code wasn't intended to answer your query. Before asking, why not google? The first answer I got was this

              → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

And here is a list of first few hundreds of highly composite numbers:)

→ Reply
»
10 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    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.

    → Reply