Find all four-digit numbers such that when decomposed into prime factors, each number has the sum of its prime factors equal to the sum of the exponents.
Problem
Source:
Tags: number theory proposed, number theory
sumanguha
30.10.2010 21:28
let the four digit no is $ \ k=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{k}^{\alpha_{k}} $ then see as $ \ 2^{14}=16384$ so $ \alpha_{1}+\alpha_{2}+...+\alpha_{k} \leq 13 $ so $ \ p_{1}+...+p_{k} \leq 13 $ from there we see the only possibility are following $ \ (2,3,5) ,(2,3,7),(2,3),(2,5),(2,7),(2,11),(3,5),(3,7),(5,7),2,3,5,7,11,13 $ from there we can see the only solutions are $ \ 5^{5},2^{3}5^{4},2^{4}5^{3},2^{7}7^{2},2^{8}7,2^{8}35,2^{7}3^{2}5,2^{7}35^{2},2^{6}3^{3}5 $
Binomial-theorem
28.04.2012 23:36
Remark that the maximum sum of the exponents is obviously $13$ from $2^{13}$ (as anything else will have less exponents as it increases faster than $2^n$).
$2^x$ giving $x=2$ which isn't four digits.
$3^x$ gives $x=3$ which isn't four digits.
$5^x$ gives $x=5$ which is $3125$ so it works.
$7^x$ gives $x=7$ but $7^5$ is greater than $10^5$ so $7^7$ is also.
The same holds for $11^x$ and $13^x$.
Next, $2^x*3^y$ gives $x+y=5$ for a maximum of $y=4, x=1$ giving $162$ which isn't four digits.
$2^x*5^y$ gives $x+y=7$ for a maximum of $y=6, x=1$ giving a number larger than $4$ digits, $y=5, x=2$ gives $3125*4$ giving a number larger than $4$ digits, $y=4, x=3$ gives $625*8=5000$ which works, $y=3, x=4$ gives $125*16=2000$ which works, $y=2, x=5$ gives $25*32=800<1000$ so we are done for this case.
$2^x*7^y$ gives $x+y=9$. $(x,y)=(8,1)$ gives $1792$ which works, $(x,y)=(7,2)$ gives $6272$, $(x,y)=(6,3)$ gives $21952$ which is too large.
$2^x*11^y$ gives $x+y=13$. The minimum is therefore $x=12, y=1$ which gives $45056$ which is already too large.
$3^x*5^y$ gives $x+y=8$. $x=7, y=1$ is the minimum giving $2187*5=10935$ which is already too large.
The same holds for all other powers having no $2$'s in them.
$2^x*3^y*5^z$ gives $x+y+z=10$. The minimum is $x=8, y=1, z=1$ giving $3840$. The next case is $x=7, y=2, z=1$ giving $5760$ and $x=7, y=1, z=2$ giving $9600$. The next case is $x=6, y=3, z=1$ giving $8640$ and $x=6, y=2, z=2$ giving $14400$ which is too large. The next possible value that might work is $x=5, y=4, z=1$ giving $12960$ therefore there are no more solutions for this.
$2^x*3^y*7^z$ gives $x+y+z=12$. The minimum is $x=10, y=1, z=1$ giving $21504$ which is too large.
All other cases give $x+y+z>13$ for an obvious contradiction (see the first line of the solution).
$2^x*3^y*5^z*7^a$ gives $x+y+z+a>17$ for an obvious contradiction (see the first line of the solution).
In conclusion, the answers are $\boxed{1792, 2000, 3125, 3840, 5000, 5760, 6272, 8640, 9600}$.