Hi! :)

What is the best upper bound for number of divisors of some natural number *n*?

I can't find any bound better than :(

Before contest

Codeforces Round 955 (Div. 2, with prizes from NEAR!)

08:11:20

Register now »

Codeforces Round 955 (Div. 2, with prizes from NEAR!)

08:11:20

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3845 |

2 | jiangly | 3707 |

3 | Benq | 3630 |

4 | orzdevinwang | 3573 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3532 |

8 | ecnerwala | 3501 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

3 | awoo | 161 |

4 | nor | 152 |

4 | maroonrk | 152 |

6 | -is-this-fft- | 151 |

7 | TheScrasse | 149 |

8 | atcoder_official | 145 |

8 | Petr | 145 |

10 | pajenegod | 144 |

Hi! :)

What is the best upper bound for number of divisors of some natural number *n*?

I can't find any bound better than :(

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2024 09:23:41 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 10

^{9}and 103 680 for integers up to 10^{18}.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.

.

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

This calculates themaximumnumber of divisors ofanypositive integerless 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.