Define as the sum of the positive divisors of a natural number
How many three-digit natural numbers satisfy the inequality below?
Clarification: Numbers like 048 or 004 are not considered as a three-digit number.
This problem is a part of <Christmas Streak 2017> series .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Firstly, let's prove a lemma.
Lemma: S ( x y ) ≤ S ( x ) S ( y ) , and the equality holds when x and y are coprime.
Since it is clear that the equality holds when x and y are coprime, all we need to prove is S ( x y ) < S ( x ) S ( y ) when x and y have common prime factors of p 1 , p 2 , ⋯ , p n .
Let x = p 1 a 1 ⋯ p n a n X and y = p 1 b 1 ⋯ p n b n Y , where gcd ( X , Y ) = 1 , and you see that
S ( x ) S ( y ) = ( 1 + p 1 + p 1 2 + ⋯ + p 1 a 1 ) ⋯ ( 1 + p n + p n 2 + ⋯ + p n a n ) S ( X ) × ( 1 + p 1 + p 1 2 + ⋯ + p 1 b 1 ) ⋯ ( 1 + p n + p n 2 + ⋯ + p n b n ) S ( Y ) ;
S ( x y ) = ( 1 + p 1 + p 1 2 + ⋯ + p 1 a 1 + b 1 ) ⋯ ( 1 + p n + p n 2 + ⋯ + p n a n + b n ) S ( X ) S ( Y ) .
Then, all we need to prove is ( 1 + p + p 2 + ⋯ + p a ) ( 1 + p + p 2 + ⋯ + p b ) > ( 1 + p + p 2 + ⋯ + p a + b ) .
Are we sure that p ( p a − 1 ) ( p b − 1 ) > 0 ? Good, let's start.
p a + b + 1 − p a + 1 − p b + 1 + p p a + b + 2 − p a + 1 − p b + 1 + 1 ( p a + 1 − 1 ) ( p b + 1 − 1 ) p − 1 p a + 1 − 1 ⋅ p − 1 p b + 1 − 1 ( 1 + p + p 2 + ⋯ + p a ) ( 1 + p + p 2 + ⋯ + p b ) > 0 > p a + b + 2 − p a + b + 1 − p + 1 > ( p a + b + 1 − 1 ) ( p − 1 ) > p − 1 p a + b + 1 − 1 > ( 1 + p + p 2 + ⋯ + p a + b )
And therefore the lemma is proved. □
S ( 6 x ) ≤ S ( 6 ) S ( x ) = 1 2 S ( x ) , and therefore, S ( 6 x ) ≥ 1 2 S ( x ) is only satisfied when the equality holds, which means x and 6 are coprime.
Since three-digit numbers range from 1 0 0 to 9 9 9 , there are 9 0 0 of them.
And from that there are 2 numbers that are relatively prime to 6 among 1 , 2 , 3 , 4 , 5 , 6 ,
3 1 of the numbers are relatively prime to 6 .
∴ 9 0 0 × 3 1 = 3 0 0 .