1
$\begingroup$

Generalizing One-digit products in a row of numbers to base-N:

For which bases N does there exist at least one solution to the following: "The digits from 1 to N can be arranged in a row, such that any two neighbouring digits in this row is the product of two one-digit numbers"?

Examples:

base-10: 728163549
...
base-16: D24E1879A5B6C3F

$\endgroup$
  • $\begingroup$ Do you know the answer to this? $\endgroup$ – Don Thousand Sep 23 at 21:31
  • $\begingroup$ @DonThousand: obviously people can come up with heuristic solutions; I don't see an obvious constructive approach, although there might be one. There seems a pretty obvious generalization of ArnaudMortier's heuristic to "products starting with digit (N-1)" $\endgroup$ – smci Sep 23 at 21:40
  • $\begingroup$ Did I accidentally use the word 'obvious' three times... doh $\endgroup$ – smci Sep 24 at 1:15
2
$\begingroup$

The problem is not really about products, more about finding an arrangement of digits 1 to N-1 (for base N, since digit N does not exist in base N), that conforms to the criterion that any pair in the arrangement is part of the set of single digit products.

There could be a better way to solve this, but I wrote a small program that creates a table of possible digit combinations and uses that to try to find a valid arrangement.

It's not optimal in terms of performance (essentially a depth-first-search), but finding a pattern for base-N takes N times longer than for base-N-1.

this My program was able to show that bases 3, 4, 5, and 6 do not have such an arrangement (due to digits that do not exist in a product).

Interestingly, for base-2 (binary) it thinks that "1" is a valid combination due to the only non-zero digit being 1, so the row has no neighbouring digits.

Otherwise it shows that bases 7 to 21 have possible arrangements of digits.

base-2:  1 (questionable)
base-3:  -
base-4:  -
base-5:  -
base-6:  -
base-7:  513426
base-8:  5243617
base-9:  46271538
base-10: 728163549
base-11: 739158264a
base-12: 384765a192b
base-13: 35786a294b1c
base-14: 385b27a496c1d
base-15: 375d1b4a698c2e
base-16: 375b6e19c4d2a8f
base-17: 35b8e2ac6f17d49g
base-18: 397af2d6bc5e48g1h
base-19: 37bca59g2d8h1f4e6i
base-20: 35h28be97cf6dag4i1j

Here's a link to a program you can run in your browser.

$\endgroup$
  • $\begingroup$ "The problem is not really about products, more about finding an arrangement of digits 1 to N-1" I know that, I already hinted so above. I merely reused the phrasing of @ThomasL's original question for obvious reasons. $\endgroup$ – smci Sep 24 at 0:48
  • $\begingroup$ The base-2 solution is trivially true, since there's only one non-zero digit. $\endgroup$ – smci Sep 24 at 0:50
  • $\begingroup$ Sorry, never posted here before, took a while to figure out how to put code in spoiler tags. $\endgroup$ – Matthew Jensen Sep 24 at 1:07

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.