What is the upper bound of total number of divisors of divisors of a number ?
# | User | Rating |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 157 |
4 | maroonrk | 154 |
5 | -is-this-fft- | 148 |
5 | atcoder_official | 148 |
5 | SecondThread | 148 |
8 | Petr | 147 |
9 | TheScrasse | 145 |
9 | nor | 145 |
What is the upper bound of total number of divisors of divisors of a number ?
Name |
---|
If a is divisor of x and y and both x and y are divisors of z, do you count a twice?
yes
then you may consider the upper bound to be
, as the upper bound on number of divisors is
(verified upto n = 1018)
But where does
come from? Do you assume that divisors of n are of magnitude
? That isn't true.
I don't know if I was high writing that... My bad :(
Let f(n) be the number of divisors of divisors of n. If we are going to use a bound for d(n), we may use the identity:
where rad(n) and ω(n) are the product and the number of distinct prime divisors of n, respectively. That formula can be obtained by noting that f is multiplicative (being the Dirichlet convolution of d and 1, or the triple Dirichlet convolution of 1), and multiplying everything after getting
.
Now, using the simple estimate
(which comes from the fact that
and increasing each term by 1 multiplies each bracket by at most 3/2)
we get
According to the last column of this table, talking only "competitive programming numbers" into account: this bound is better than the trivial
bound by ~ an order of magnitude, but should also not be very far from the truth - the worst cases have several prime factors, with only the exponent on the prime number $2$ being significant.
Of course, the asymptotic behaviour of d(n) has already been well-explained here, and even better on What's New. I couldn't obtain a real-world bound using this kind of approach, though.
Also,
Unable to parse markup [type=CF_TEX]
is buggy here. I think there is a problem with parsing the comments.if your purpose is not mathematical , you can approximately find by using brute force (I mean , you don't have a time limit in your computer)