### ChuVanKhanh's blog

By ChuVanKhanh, history, 9 days ago,

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).

• -5

 » 9 days ago, # |   0 Auto comment: topic has been updated by ChuVanKhanh (previous revision, new revision, compare).
 » 9 days ago, # |   +11 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.
•  » » 8 days ago, # ^ |   0 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 ?
•  » » » 8 days ago, # ^ |   0 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.