kalimm's blog

Sum Of Number Of Divisors Of Divisors Of A Number
By kalimm, history, 9 years ago, In English

What is the sum of number of divisors of divisors of number which is smaller than n, such that sum of number of divisors of divisors of this number is maximum?

For example,

g(n) = number of divisors of n

f(12) = g(1) + g(2) + g(3) + g(4) + g(6) + g(12)

f(12) = (1) + (2) + (2) + (3) + (4) + (6) = 18

Can you help about it?

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

»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

What is the problem source?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

What's the source of your problem?

Edit: perfect timing :)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

If given x then f(x) would be product of (αi + 1)(αi + 2) where αi is degree of ith prime which divides x. It is possible to make DP for small values of x, but I don't see how to solve problem for large x > 107. Ups typo.product of (αi + 1)(αi + 2) / 2. Anyway, how to solve easier problem: find maximum g(x) where x < n for 0 < n < 109.

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

Auto comment: topic has been updated by kalimm (previous revision, new revision, compare).

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

Almost a palindromic topic :P

→ Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it +34 Vote: I do not like it

Let's factorize your number x. For example, x = x1α1 * x2α2 * ... * xnαn

Let's take one of it's divisors. For example, it's y = x1λ1 * x2λ2 * ... * xnλn where λi <  = αi.

It's obvious that divisors of number y is (λ1 + 1) * (λ2 + 1) * ... * (λn + 1). Than total sum is . To found it's sum, you can run all possible λ, e.g. all divisors of x, it's not too much, something like log(x). I don't sure that you really need to count sum really fast, because factorization seems longer than sum.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 36   Vote: I like it +24 Vote: I do not like it

    Edit: you can count this sum quickly, it's easy.

    Let

    .

    It means that

    Than

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ACM-ICPC Asia Regional contest dhaka site ........... Problem-(E) needs this concept. Problem link : http://www.northsouth.edu/acm-icpc-2015/Problem_Set_2015.pdf

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope. That is simply the sum of divisors. Not sum of sum of divisors :P

    → Reply