Find all natural numbers $n$ for which the following $5$ conditions hold: $(1)$ $n$ is not divisible by any perfect square bigger than $1$. $(2)$ $n$ has exactly one prime divisor of the form $4k+3$, $k\in \mathbb{N}_0$. $(3)$ Denote by $S(n)$ the sum of digits of $n$ and $d(n)$ as the number of positive divisors of $n$. Then we have that $S(n)+2=d(n)$. $(4)$ $n+3$ is a perfect square. $(5)$ $n$ does not have a prime divisor which has $4$ or more digits.
Problem
Source: Serbia JBMO TST 2022 P3
Tags: number theory
01.06.2022 18:22
Not too bad. If $n$ is odd, then $n\equiv 3 \pmod 4$ (since it has only one prime divisor $3$ mod $4$) and $n+3\equiv 2 \pmod 4$ cannot be a square, contradiction. Hence $n = 2qp_1p_2\cdots p_s$ where $q\equiv 3 \pmod 4$ and all $p_i\equiv 1 \pmod 4$ are distinct primes. We have $S(n) = d(n) - 2 = 2^{s+2} - 2$. Since $n < 2 \cdot 10^{3(s+1)}$, the number of digits of $n$ is at most $3s+4$ - and if equality holds, then the leading digit is $1$ - so $S(n) \leq 27(s+1) + 1$. Hence necessarily $27s + 30 \geq 2^{s+2}$ and by proving the reverse inequality by induction we deduce that $s\leq 5$. Moreover, we have $n\equiv 6 \pmod 9$, so $2^{s+2} - 2 = S(n) \equiv n \equiv 6 \pmod 9$, which is violated by $s=2,3,4,5$. It remains to deal with $s=1$. Then $S(n) = 6$. Since $n \equiv S(n) \equiv 0 \pmod 3$, we get $q=3$ and $n = 6p_1$. With $n+3 = m^2$ we must have $m=3(2k+1)$ and so $p_1 = 6k^2 + 6k + 1$. This is less than $1000$ for $k\leq 12$ and these correspond to $13$, $37$, $73$, $121$ (not prime, divisible by $11$), $181$, $253$ (not prime, divisible by $11$), $337$, $433$, $541$, $661$, $793$ and $937$. If $p_1$ ends on $1$ or $3$, then $6p_1$ has last digit $6$ or $8$ and so the sum of digits exceeds $6$. On the other hand, $n=6 \cdot 37 = 222$ and $n = 6 \cdot 337$ work, while $n = 6 \cdot 937 = 5622$ does not. Therefore the only solutions are $222$ and $2022$.