Re: Efficient enumeration of pandigital fractions

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.

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery
FootballPerl is like chess, only without the dice}

Comment on Re: Efficient enumeration of pandigital fractions Select or Download Code

Replies are listed 'Best First'.
Re^2: Efficient enumeration of pandigital fractions by LanX (Saint) on Jul 21, 2018 at 13:18 UTC
in hindsight, in an implementation I'd prepare multiplication tables of the chosen i with all remaining digits use sieves to find remaining digits, multiplication and summing results realize these different sieves as bit strings. like $remaining = vec(100100100) would represent only 3,6 and 9 as remaining possibilities obviously you must bound if $remaining is 0 sieves as bit strings allow effective filtering of sets by `and` operations. applying a sieve to a carry would just mean shifting the string ==== for instance if you decide to go from left to right left with $i=4 `i * efgh = abcd` the multiplication table would look like `DB<14> $i=4; for $x (1..9) { next if $x==$i; $p = $i$x; $C=int($p/1 +0); $S=$p%10; print "$i $x = $p \t$C $S\n" } 4 * 1 = 4 0 4 4 * 2 = 8 0 8 4 * 3 = 12 1 2 4 * 5 = 20 2 0 4 * 6 = 24 2 4 4 * 7 = 28 2 8 4 * 8 = 32 3 2 4 * 9 = 36 3 6` [download] `# 987654321 @carry0 = (1,2) , $carry0 = vec(11) @carry1 = (3) , $carry1 = vec(0100) @carry2 = (5,6,7) , $carry2 = vec(1110000) @carry3 = (8,9) , $carry3 = vec(110000000)` [download] ( update when going from left to right you have to also put 7 into @carry3, because 28 could add to a former carry. going from right to left is indeed easier ...) ==== after trying `$e=1` you know that `@remaing=(2,3,5,6,7,8,9)` => `$remaining = vec(111110110)` `$a = $i$e + carry(4f) = 4*1 + range(0..3)` the carry range filter for 0..3 is `vec(1111)` shifted accordingly for 4 is `$carryrange=vec(1111000)` `$remaining & $carryrange = vec(1110000)` => possible $a are in (5,6,7) => carry=0 is (obviously) forbidden `$remaining & ($carry1 \| $carry2 \| $carry3) = vec(111110100)` => possible $f are in (9,8,7,6,5,3) using this approach has several advantages set operations cut down possible branches before they happen (NB: sub calls are expensive in Perl) set operations as bit string operations are very fast after preparing the multiplication table, you'll practically never need to add or multiply any more, all operations happen as "shifts", "ands" and "ors" on bit-strings these operations happen in "parallel", they sieve on all set-members this scales well for higher bases, you can still handle a 33-base in a 32-bit integer (I doubt you want to go higher) you can generalize this approach for similar problems (integer fraction puzzles) this approach will lead to a very efficient branch and bound already, I'm confident you can find even more "filter rules" to bound more efficiently. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply] [d/l] [select]
Re^2: Efficient enumeration of pandigital fractions by kikuchiyo (Hermit) on Jul 21, 2018 at 20:35 UTC
Thanks! Nice ideas here and elsewhere! One nitpick: your rule 3 (that the last multiplication can't have a carry so that the numerator is base/2 - 1 digits long) doesn't mean that `i < n/2`, it's `e` (the first digit of the denominator) that has to be < n/2. `i` can't be 1, base/2, base-2 and base-1 (and possibly others are excluded for certain bases).	[reply] [d/l] [select]
Re^3: Efficient enumeration of pandigital fractions by LanX (Saint) on Jul 21, 2018 at 21:24 UTC
> doesn't mean that i < n/2, it's e yeah I noticed. :) > i can't be 1, base/2, base-2 and base-1 Why not base-2 ... could you elaborate? `8 * 12.. = 96..` base-10 ? Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply] [d/l]
Re^4: Efficient enumeration of pandigital fractions by kikuchiyo (Hermit) on Jul 22, 2018 at 06:20 UTC
Why not base-2 ... could you elaborate? 8 * 1234 (the smallest possible denominator) = 9872, which is just 4 away from the largest possible numerator, 9876, so there isn't much wiggle room there. But 8 is already taken, and the next possible combination 9765, is not divisible with 8, and the quotient is less than 1234. In general, `zyxw...(base/2-1) - (base-2) * 1234...(base/2-1) = base/2 - 1`.	[reply] [d/l]