2 explain why this is so slow

(EDIT: I checked the Brachylog source for the reason. It turns out that if you use p on two known integers, the algorithm used generates all possible permutations of the integer in question until it finds one that's equal to the output integer, as the algorithm is "input → indigits, permute indigits → outdigits, outdigits → output". A more efficient algorithm would be to set up the outdigits/output relationship first, so that the backtracking within the permutation could take into account which digits were available.)

(EDIT: I checked the Brachylog source for the reason. It turns out that if you use p on two known integers, the algorithm used generates all possible permutations of the integer in question until it finds one that's equal to the output integer, as the algorithm is "input → indigits, permute indigits → outdigits, outdigits → output". A more efficient algorithm would be to set up the outdigits/output relationship first, so that the backtracking within the permutation could take into account which digits were available.)

1

# Brachylog v2, 15 bytes

t<.g,?kA/p.∧A×p


Try it online!

Takes input in the form [x,y].

## Explanation

t<.g,?kA/p.∧A×p
t                  Tail (extract y from the input)
<                 Brute-force search for a number > y, such that:
.                  it's the output to the user (called ".");
g                 forming it into a list,
,?               appending both inputs (to form [.,x,y]),
k              and removing the last (to form [.,x])
A             gives a value called A, such that:
/              first ÷ second element of {A}
p             is a permutation of
.            .
∧         and
A×         first × second element of {A}
p        is a permutation of {.}


## Commentary

Brachylog's weakness at reusing multiple values multiple times shows up here; this program is almost all plumbing and very little algorithm.

As such, it might seem more convenient to simply hardcode the value of y (there's a comment on this question hypothesising that 2 is the only possible value). However, there are in fact solutions for y=3, meaning that unfortunately, the plumbing has to handle the value of y as well. The smallest that I'm aware of is the following:

                         315789473684210526
315789473684210526 × 3 = 947368421052631578
315789473684210526 ÷ 3 = 105263157894736842


(The technique I used to find this number isn't fully general, so it's possible that there's a smaller solution using some other approach.)

You're unlikely to verify that with this program, though. Brachylog's p is written in a very general way that doesn't have optimisations for special cases (such as the case where both the input and output are already known, meaning that you can do the verification in O(n log n) via sorting, rather than the O(n!) for the brute-force approach that I suspect it's using). As a consequence, it takes a very long time to verify that 105263157894736842 is a permutation of 315789473684210526 (I've been leaving it running for several minutes now with no obvious progress).

Post Made Community Wiki by ais523