## BdMO National 2021 Higher Secondary Problem 9

Anindya Biswas
Posts: 247
Joined: Fri Oct 02, 2020 8:51 pm
Contact:

### BdMO National 2021 Higher Secondary Problem 9

একটা ধনাত্মক পূর্ণসংখ্যা $$n$$-কে মনোরম বলা হবে যদি এটার কমপক্ষে $$3$$-টা প্রকৃত উৎপাদক থাকে এবং এটা তার সবচেয়ে বড় তিনটা প্রকৃত উৎপাদকের যোগফলের সমান হয়। যেমন $$6$$ একটা মনোরম সংখ্যা কারণ $$6$$-এর সবচেয়ে বড় তিনটা প্রকৃত উৎপাদক হলো $$3$$, $$2$$, $$1$$ এবং $$6=3+2+1$$। $$6000$$-এর চেয়ে বড় না, এমন কতগুলো মনোরম সংখ্যা আছে?

A positive integer $n$ is called nice if it has at least $3$ proper divisors and it is equal to the sum of its three largest proper divisors. For example, $6$ is nice because its largest proper divisors are $3,2,1$ and $6=3+2+1$. Find the number of nice integers not greater than $6000$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Anindya Biswas
Posts: 247
Joined: Fri Oct 02, 2020 8:51 pm
Contact:

### Solution :

Let me start with an exercise. Find three distinct positive integers $a,b,c$ where $a<b<c$ such that $\frac1a+\frac1b+\frac1c=1$ You may post the solution below.
Well, the only solution to this equation is $(a,b,c)=(2,3,6)$.

Let's assume, $n$ is a nice integer. Let $\frac{n}{x},\frac{n}{y},\frac{n}{z}$ be the largest three proper divisor of $n$ where $\frac{n}{x}>\frac{n}{y}>\frac{n}{z}$. Then we got,
$n=\frac{n}{x}+\frac{n}{y}+\frac{n}{z}\Longleftrightarrow \frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1$
$\therefore x=2,y=3,z=6$
So, $n$ is divisible by $2,3,6$. Also, $n$ is not divisible by $4,5$ since otherwise $\frac{n}{4}$ or $\frac{n}{5}$ would be one of the largest three proper divisors which is not the case. So, we can consider this system of linear congruences to solve for $n$:
$\begin{array} \ n\equiv0\pmod3 \\ n\equiv2\pmod{4} \\ n\equiv r\pmod{5} \end{array}$ Where $r\in\{1,2,3,4\}$
By Chinese Remainder Theorem, this congruences has unique solutions modulo $60$. So, for each value of $r$, we get a unique number between $1$ and $60$ which is nice. So, there are $4$ nice integers less than or equal to $60$.
So, there are $\boxed{400}$ nice integers not greater than $6000$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Pro_GRMR
Posts: 46
Joined: Wed Feb 03, 2021 1:58 pm

### Re: BdMO National 2021 Higher Secondary Problem 9

Anindya Biswas wrote:
Sun Apr 11, 2021 10:31 am
A positive integer $n$ is called nice if it has at least $3$ proper divisors and it is equal to the sum of its three largest proper divisors. For example, $6$ is nice because its largest proper divisors are $3,2,1$ and $6=3+2+1$. Find the number of nice integers not greater than $6000$.
This also came as Secondary Problem 10.
"When you change the way you look at things, the things you look at change." - Max Planck

Ohin01
Posts: 5
Joined: Sun Feb 14, 2021 10:04 pm

### Re: Solution :

Anindya Biswas wrote:
Sun Apr 11, 2021 11:11 am
Let me start with an exercise. Find three distinct positive integers $a,b,c$ where $a<b<c$ such that $\frac1a+\frac1b+\frac1c=1$ You may post the solution below.
Well, the only solution to this equation is $(a,b,c)=(2,3,6)$.

Let's assume, $n$ is a nice integer. Let $\frac{n}{x},\frac{n}{y},\frac{n}{z}$ be the largest three proper divisor of $n$ where $\frac{n}{x}>\frac{n}{y}>\frac{n}{z}$. Then we got,
$n=\frac{n}{x}+\frac{n}{y}+\frac{n}{z}\Longleftrightarrow \frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1$
$\therefore x=2,y=3,z=6$
So, $n$ is divisible by $2,3,6$. Also, $n$ is not divisible by $4,5$ since otherwise $\frac{n}{4}$ or $\frac{n}{5}$ would be one of the largest three proper divisors which is not the case. So, we can consider this system of linear congruences to solve for $n$:
$\begin{array} \ n\equiv0\pmod3 \\ n\equiv2\pmod{4} \\ n\equiv r\pmod{5} \end{array}$ Where $r\in\{1,2,3,4\}$
By Chinese Remainder Theorem, this congruences has unique solutions modulo $60$. So, for each value of $r$, we get a unique number between $1$ and $60$ which is nice. So, there are $4$ nice integers less than or equal to $60$.
So, there are $\boxed{400}$ nice integers not greater than $6000$.
I just realised something
I did a similar solution like this...
Every nice integer is of this format-
6*k where k is not a multiple of 2 and 5
Which results there is 400 nice integers inside 6000 range

But unfortunately I submitted the values of 'k' for which '6k' is "not" a nice integer.I gave 600 as the answer....now I realised I absolutely forgot to substract it from 1000(there are 6000/6=1000 total values of k) to get the real answer :"(

Online national cost me a P10(Secondary)