2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

This one needed some rambling thought before I settled down to an approach. I had thought that there should be a more effective method than simply counting upwards while testing each number in the range.

I settled on the simple approach when I realised that when checking the current highest number, you can skip all remaining items in the range should there be a single failure to evenly divide.

My brief, if inelegant solution – which I’ll hopefully refine in the next few days – is copied below (written in Ruby). I can’t help but think there are ways to:

• cut down the number of division checks
• increment the high number by greater degrees each time

So plenty still to examine with this one.

The latest in a series of paired-up problem workings with Greg Bowie. This week we’re looking at Problem 8:

Discover the largest product of five consecutive digits in a the [provided] 1000-digit number

Here’s my response, longhand:

1. I’ll need a variable to store the (current) value of the greatest product
2. I’ll need to iterate through the 1000-digit number, reading 5 digits at a time working out the product of each sequence, stepping one digit on with every iteration.
3. The routine will begin from the 1st digit. The process will stop 5 digits of the final digit
4. Using variables to store the length of the 1000-digit number and the number of digits we’re deriving the product of would make the solution more adaptable for other numbers and sequences
5. Each product retrieved from every sequence of 5 digits must be compared to the current greatest product. If this exceeds the current greatest product, we set this as the new greatest product

This should solve the problem, but why stop now?

Refinements

The presence of zeros in the 1000-digit number is notable – any zero encountered while examining the product of multiple digits will result in a zero product. So I’ll ignore them:

1. Create an array of smaller numbers by splitting the 1000-digit number by any zero digit – handling sequences of zeros so as to prevent empty array items
2. Iterate through each of these numbers, deriving the product of each set of 5 digits, and checking this against the current greatest product

Chances are this refinement will not improve the performance of this test on a single number, but as it reduces the number of product-derivation runs by 398 by it may scale well, depending on the language.

Refined version:

here’s Greg’s response, posted simultaneously today.

update 23/01/2012:

Revisiting this afresh I realise there’re other ways to skip those pesky zeros, rather than drop them into an array, better to simply skip past any such sequence:

Here’s the first of my responses to the Euler problems I’m working through in parallel with ex-colleague and fellow code-charmer Greg Bowie.

Each week we’ll tackle one of the problems (in isolation) and post our respective responses each Friday – workloads permitting – at around 3pm. This week Greg chose Problem 4
Continue reading →

Still firmly in the grip of that New Year fervour for fresh starts, new endeavours and personal development, I’m teaming up with ex-colleague Greg Bowie to tackle as many of the programming exercises to be found over at Project Euler as we can in 2012.
Continue reading →