0%

Problem 565


Problem 565


Divisibility of sum of divisors

Let $\sigma(n)$ be the sum of the divisors of n.
E.g. the divisors of 4 are 1, 2 and 4, so $\sigma(4)=7$.

The numbers n not exceeding 20 such that 7 divides $\sigma(n)$ are: 4, 12, 13 and 20, the sum of these numbers being 49.

Let S(n,d) be the sum of the numbers i not exceeding n such that d divides $\sigma(i)$.
So S(20,7)=49.

You are given: $S(10^6,2017) = 150850429$ and $S(10^9,2017) = 249652238344557$.

Find $S(10^{11},2017)$.


约数和的整除性

记$\sigma(n)$为n的约数的和。
例如4的约数为1,2和4,因此$\sigma(4)=7$。

在不超过20的数n中,$\sigma(n)$能被7整除的有4,12,13和20,这些数的和是49。

记S(n,d)是所有不超过n且$\sigma(i)$能被d整除的数i的和。
因此S(20,7)=49。

已知$S(10^6,2017) = 150850429$以及$S(10^9,2017) = 249652238344557$。

求$S(10^{11},2017)$。