I was working on the Euler project's problems and the 32nd problem is the following:
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
I have written the following code.
https://github.com/l1x/euler/blob/master/src/euler/core.clj#L134
This works fine and solved the problem but I found a huge performance increase in the implementation.
If I iterate from 1...9999 using the number for "a" and 1...9999 using the value for "b" I can obviously calculate "c = a * b" and investigate if "a b c" is pandigital. Now if I change the iteration from 1...9999 to 1...5000 and a...(9999 / a) I get the same results but significantly faster.
My question is why is that equal to have
a 1...5000 b a...(9999 / a)
instead of
a 1...9999 b 1...9999
Producing (a * b)
A few hints: there is symmetry between $a$ and $b$, so you can just define $a \le b$ (or the other way around). Can you show that $c \le 9999$? Since $b \ne 1$ (why?) you will get all the products by taking $a$ from $1 \text { to } 9999/2 \approx 5000$, then $b \le 9999/a$ or $c$ gets too large.