What is the upper bound of total number of divisors of divisors of a number ?

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

1 | tourist | 3556 |

2 | wxhtxdy | 3520 |

3 | Radewoosh | 3409 |

4 | Benq | 3368 |

5 | mnbvmar | 3280 |

6 | ecnerwala | 3278 |

7 | LHiC | 3276 |

8 | sunset | 3264 |

9 | maroonrk | 3159 |

10 | TLE | 3145 |

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

1 | Errichto | 189 |

2 | Radewoosh | 177 |

3 | tourist | 173 |

4 | antontrygubO_o | 172 |

5 | Vovuh | 166 |

5 | PikMike | 166 |

7 | rng_58 | 157 |

8 | majk | 156 |

9 | farmersrice | 154 |

10 | Um_nik | 153 |

What is the upper bound of total number of divisors of divisors of a number ?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2019 10:04:44 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

If

ais divisor ofxandyand bothxandyare divisors ofz, do you countatwice?yes

then you may consider the upper bound to be , as the upper bound on number of divisors is (verified upto n = 10

^{18})But where does come from? Do you assume that divisors of

nare 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 ofn. If we are going to use a bound ford(n), we may use the identity:where

rad(n) and ω(n) are the product and the number of distinct prime divisors ofn, respectively. That formula can be obtained by noting thatfis multiplicative (being the Dirichlet convolution ofdand 1, or the triple Dirichlet convolution of 1), and multiplying everything after getting .Now, using the simple estimate

(which comes from the fact that

d(n) = (α_{1}+ 1)·...·(α_{ω(n)}+ 1)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)