I'd try a branch and bound, starting with i and trying out values for the digits of the other multiplicand from right to left.

Each digit to the right determines another one to the left.

Whenever a digit gets repeated you bound.

Taking your decimal case:

> abcd = efgh * i

• Starting with i=1 and h=1 is obviously impossible.
• i * efgh = abcd
• 2 * efg3 = abc6
• 2 * ef13 = ab26 2 repeated bound °
• 2 * ef43 = ab86
• 2 * e543 = (1)086 0 forbidden bound! ²
• 2 * e743 = (1)486 4 repeated bound!
• 2 * e943 = (1)886 8 repeated bound!
• 2 * ef53 = a(1)06 0 forbidden bound! ²
• 2 * ef73 = a(1)46
• 2 * e173 = a346 3 repeated bound
• 2 * e573 = (1)146
• 2 * 8573 = (1)6146 too many digits bound ³
• 2 * 9573 = (1)8146 too many digits bound ³
• 2 * ef83 = a(1)66 6 repeated bound!
• 2 * ef93 = a(1)86
• and so on

°) obviously you can only use 1 when the last multiplication had a carry digit (denoted in brackets) ²) multiplying an even number with 5 will always lead to 0 and multiplying an even number with 6 will always repeat that number ³) the last multiplication in a system with even numbered digits can't have a carry digit

I did this by hand to find some rules to effectively cut down the possibilities of a branch and bound.

Rule 2 means you'll can eliminate all n * (n-1) possibilities where the product repeats one of the factors or lead to 0. For instance in a decimal system i can't possibly ever be 5 or 6.

(just prepare a multiplication table for an n-system to eliminate these cases)

Footnote °) is just a special case of rule 2

Rule 3 means anything i must be < n/2 for n even like the decimal with n=10) and i >= n/2 for n odd.

That is in the decimal case i can only be 2, 3 or 4

These are massive reductions of all possibilities, far more efficient than calculating all k-permutations.

I'm only wondering if it's more efficient to start trying from right to left starting with h or even from left to right starting with e or even combining both possibilities.

for instance these are the only possible combinations of i and e for n=10

  DB<4> for $i (2,3,4) { for $e (1..9) { next if $e == $i or $e*$i >9 
+; print "$i * $e = ", $i *$e,"\n" }}
2 * 1 = 2   #
2 * 3 = 6
2 * 4 = 8  
3 * 1 = 3   #
3 * 2 = 6
4 * 1 = 4   #
4 * 2 = 8
[download]

And the cases I marked with a # mean that the value for f must lead to a carry digit to alter a.

This seems to reduce possible branches very quickly!!!

I hope I gave you some good ideas for the case n=10 which can be generalized for bigger n.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.