Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
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. –  rschwieb Sep 13 '12 at 20:24
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
Yes there is symmetry so you can get rid off the 50% of the matrix (divide by the diagonal). I don't understand why can you rid of the 50% of that remaining matrix, and what is the reason to do a...(9999/a) still. –  l1x Sep 13 '12 at 21:29
    
@l1x: If $b \gt 9999/a,$ then $c$ will be too large. That was the point of showing that $c \le 9999$ –  Ross Millikan Sep 13 '12 at 21:31
    
Alright, that makes sense. I understand it now. Thank you for the answer. –  l1x Sep 13 '12 at 23:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.