12
$\begingroup$

The digits from 1 to 9 can be arranged in a row, such that any two neighbouring digits in this row is the product of two one-digit numbers. Arrangement:

$$728163549$$

Is it possible to do such an arrangement using hexadecimal digits 1-9 and A-F? Here the row has 15 digits and all numbers are treated as hexadecimal numbers. Example: 123456789ABCDEF 12=2*9, 23=5*7, 34=4*D, 45 does not work, etc.

Improve this question
$\endgroup$
3
  • $\begingroup$ Neat! You could generalize to an OEIS entry of such numbers from base-3 upwards... in case of ambiguity, taking the numerically smallest. I wonder if there's a constructive proof that such a number exists for every base N. $\endgroup$
    – smci
    Commented Sep 23, 2019 at 16:59
  • 1
    $\begingroup$ @smci The first base which has a solution is base $7$, with a single solution. Base $8$ also has a single solution while base $9$ oddly has three. $\endgroup$
    – Jens
    Commented Sep 23, 2019 at 18:09
  • $\begingroup$ I posted a Generalization to base-N $\endgroup$
    – smci
    Commented Sep 23, 2019 at 20:20

2 Answers 2

Reset to default
13
$\begingroup$

One solution is

$$D2379A5B6C4E18F$$ enter image description here

Thought process:

No product starts with $F$, so $F$ must be at the end, and the only options are $3F$ and $8F$.
The only $2$-digit numbers that are products of $1$-digit number and start with digits $A, B, C, D, E$ are $$A5, A8, A9, B4, B6, C3, C4, D2, E1.$$
Therefore we must have subsequences $E1$ and $D2$. From this, you quickly get an answer by looking at the above table. I don't know if I was lucky, but apart from the observations above, I guessed all the rest right. Just for the sake of it, here is another one: $$D24E1879A5B6C3F$$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ It would be interesting to see if this can be generalized to all number bases. You can obviously play around with it like you did here, but proving it mathematically for all bases without having to test them individually might be an interesting challenge... $\endgroup$
    – Darrel Hoffman
    Commented Sep 23, 2019 at 13:52
7
$\begingroup$

As an addendum to the answer from @Arnaud:

The smallest such number is 375B6E19C4D2A8F. According to the brute-force program I made, there are just $787$ solutions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting result, I did not expect so many possibilities (787), especially there seems to be only one solution for base 10. $\endgroup$
    – ThomasL
    Commented Sep 23, 2019 at 17:18
  • 2
    $\begingroup$ @ThomasL That's because as the amount of digits increases from 10 to 16, the amount of acceptable pairs increases roughly from $\frac{10^2}{2}$ to $\frac{16^2}{2}$ which is a huge increase in comparison. Statistically, there has to be a larger and larger number of solutions as the base increases. $\endgroup$
    – Arnaud Mortier
    Commented Sep 23, 2019 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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