ChuVanKhanh's blog

Numerical Analysis
By ChuVanKhanh, history, 20 months ago, In English

Hi everyone, I've encountered a rather difficult problem for me, I hope you guys can give me some suggestions. The problem is as follows for a positive integer S (S <= 1e9), find how many ways to decompose the number S into the sum of positive integers whose greatest common divisor is 1.(Two sets of numbers that are vin permutations are also counted as different).

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
20 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Find a formula for the number of ways to write S as sum of positive integers.

Then find the number of ways to write S as a set of positive integers whose gcd is a multiple of d. (Note every element will have to be a multiple of d.)

Then obtain the answer by inclusion-exclusion.

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

    Can you tell more about ( Then find the number of ways to write S as a set of positive integers whose gcd is a multiple of d. (Note every element will have to be a multiple of d.) ?; What is d ?

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

      d is any divisor of S.

      The idea is: suppose S = 36.

      Find the number of ways to write S as the sum of positive integers.

      Then find the number of ways to write S as the sum of multiples of 2, and then subtract that from the original count. (Because the gcd will be a multiple of 2 and we should not count it.)

      Do the same for multiples of 3.

      But then we have to add back the multiples of 6.

      → Reply