6
$\begingroup$

For integer $k\geq 0$ written $d_jd_{j-1}\dots d_1$, where $d_i$ are single-digit integers, define $$R(k) := \begin{cases} d_j^{d_1}d_{j-1}^{d_2} \dots d_{j/2}^{{d_{j/2 + 1}}}, & j \text{ is even.}\\ d_j^{d_1}d_{j-1}^{d_2} \dots d_{(j+1)/2 -1}^{d_{(j+1)/2+1}} d_{(j+1)/2}, & j \text{ is odd.} \end{cases} $$ Which is a bit of an eyesore, though some examples may help: $R(1392) = 1^2 * 3^9$, $R(793) = 7^3*9$, $R(12345678) = 1^8 * 2^7*3^6 * 4^5$.

Now, say an integer $n \geq 0$ is rock-hard if $R(n) =n$. $0, 1, 2, 3 \dots 9$ are rock-hard. There are no rock-hard two-digit integers. This can be verified in about five seconds with the question: is there a power of $n$ between $10n$ and $10(n+1)$ for $0 < n < 10$? I do not believe there are any three-digit rock hard integers.

My question: is there a more efficient way to search for rock-hard numbers than just checking all numbers? Certainly, we can omit $111$, $121 \dots 191$, $11111,$ $11211,$ etc., but can we further narrow down what numbers we check for rock-hardness?

Motivation: John Conway did something similar to this, though I can't remember what he did nor find a reference. I believe N.J.A. Sloane chipped in as well.

Various comments: $256$ is almost rock-hard but not quite! $256 = 2^6*4$.

$\endgroup$
  • $\begingroup$ I would just write a program and search through eight digits, which should run quickly. I suspect there are very few. After that there are so many ways to miss I am sure there are no more. Of course, this is just a hand wave. $\endgroup$ – Ross Millikan Jan 14 at 3:17
18
$\begingroup$

You can do much better than checking all numbers... note that any rock-hard integer is equal to a product of powers of $1,2,\ldots,9$; indeed, all rock-hard integers must be $7$-smooth. There aren't that many $7$-smooth numbers... below $N$, there can't be more than $$(\log_2 N + 1)(\log_3 N + 1)(\log_5 N + 1)(\log_7 N + 1)$$ of them. A simple script verifies that there are only $2867708$ candidates below $10^{48}$, and checking them all turns up only one rock-hard integer with more than one digit ($117649$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.