Christmas Streak 06/88: Sum Of The Divisors!

Define S ( n ) S(n) as the sum of the positive divisors of a natural number n . n.

How many three-digit natural numbers n n satisfy the inequality below?

S ( 6 n ) 12 S ( n ) \large S(6n)\ge 12S(n)


Clarification: Numbers like 048 or 004 are not considered as a three-digit number.

This problem is a part of <Christmas Streak 2017> series .


The answer is 300.

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.

1 solution

Boi (보이)
Oct 4, 2017

Firstly, let's prove a lemma.


Lemma: S ( x y ) S ( x ) S ( y ) , S(xy)\le S(x)S(y), and the equality holds when x x and y y are coprime.

Since it is clear that the equality holds when x x and y y are coprime, all we need to prove is S ( x y ) < S ( x ) S ( y ) S(xy)<S(x)S(y) when x x and y y have common prime factors of p 1 , p 2 , , p n . p_1,~p_2,~\cdots,~p_n.

Let x = p 1 a 1 p n a n X x={p_1}^{a_1}\cdots{p_n}^{a_n}X and y = p 1 b 1 p n b n Y , y={p_1}^{b_1}\cdots{p_n}^{b_n}Y, where gcd ( X , Y ) = 1 , \text{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)S(y)=(1+p_1+{p_1}^2+\cdots+{p_1}^{a_1})\cdots(1+p_n+{p_n}^2+\cdots+{p_n}^{a_n})S(X)\times(1+p_1+{p_1}^2+\cdots+{p_1}^{b_1})\cdots(1+p_n+{p_n}^2+\cdots+{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 ) . S(xy)=(1+p_1+{p_1}^2+\cdots+{p_1}^{a_1+b_1})\cdots(1+p_n+{p_n}^2+\cdots+{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 ) . (1+p+p^2+\cdots+p^a)(1+p+p^2+\cdots+p^b)>(1+p+p^2+\cdots+p^{a+b}).

Are we sure that p ( p a 1 ) ( p b 1 ) > 0 p(p^a-1)(p^b-1)>0 ? Good, let's start.

p a + b + 1 p a + 1 p b + 1 + p > 0 p a + b + 2 p a + 1 p b + 1 + 1 > p a + b + 2 p a + b + 1 p + 1 ( p a + 1 1 ) ( p b + 1 1 ) > ( p a + b + 1 1 ) ( p 1 ) p a + 1 1 p 1 p b + 1 1 p 1 > p a + b + 1 1 p 1 ( 1 + p + p 2 + + p a ) ( 1 + p + p 2 + + p b ) > ( 1 + p + p 2 + + p a + b ) \begin{aligned} p^{a+b+1}-p^{a+1}-p^{b+1}+p & > 0 \\\\ p^{a+b+2}-p^{a+1}-p^{b+1}+1 &> p^{a+b+2}-p^{a+b+1}-p+1 \\\\ (p^{a+1}-1)(p^{b+1}-1) &> (p^{a+b+1}-1)(p-1) \\\\ \frac{p^{a+1}-1}{p-1}\cdot\frac{p^{b+1}-1}{p-1} &> \dfrac{p^{a+b+1}-1}{p-1} \\\\ (1+p+p^2+\cdots+p^a)(1+p+p^2+\cdots+p^b) &>(1+p+p^2+\cdots+p^{a+b}) \end{aligned}

And therefore the lemma is proved. \square


S ( 6 x ) S ( 6 ) S ( x ) = 12 S ( x ) , S(6x)\le S(6)S(x)=12S(x), and therefore, S ( 6 x ) 12 S ( x ) S(6x)\ge12S(x) is only satisfied when the equality holds, which means x x and 6 6 are coprime.

Since three-digit numbers range from 100 100 to 999 , 999, there are 900 900 of them.

And from that there are 2 2 numbers that are relatively prime to 6 6 among 1 , 2 , 3 , 4 , 5 , 6 , 1,~2,~3,~4,~5,~6,

1 3 \dfrac{1}{3} of the numbers are relatively prime to 6. 6.

900 × 1 3 = 300 . \therefore~900\times\dfrac{1}{3}=\boxed{300}.

Did you mean to write gcd ( X , Y ) = 1 \text{gcd}(X,Y)=1 , not lcm ( X , Y ) = 1 \text{lcm}(X,Y)=1 in the third line of the proof of your lemma?

Miles Koumouris - 3 years, 8 months ago

Log in to reply

Oh, whoops! Thank you for pointing out! x'D

Boi (보이) - 3 years, 8 months ago

Log in to reply

No problem! Also, (still nitpicking) in the fifth line of the proof of your lemma, did you mean to write a 1 + b 1 a_1+b_1 in the power, and not a 2 + b 1 a_2+b_1 ? Great problem by the way...

Miles Koumouris - 3 years, 8 months ago

Log in to reply

@Miles Koumouris Eyyy! You have some keen eyes!

And... thanks! ^^;

Boi (보이) - 3 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...