### 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).  Comments (4)
 » Auto comment: topic has been updated by ChuVanKhanh (previous revision, new revision, compare).
 » 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.
•  » » 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 ?
•  » » » 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.