1
$\begingroup$

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)

  • 1
    You might find an explanation in the forum you get access to after you solve the problem. People usually write up their implementations, and this one is probably among them.2012-09-13

1 Answers 1

1

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.

  • 0
    Alright, that makes sense. I understand it now. Thank you for the answer.2012-09-13