I first heard about Project Euler at vbCity. What is Project Euler?
To quote Project Euler, "
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just
mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a
computer and programming skills will be required to solve most problems."
|
Problem 2
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum
of all the even-valued terms in the sequence which do not exceed four million.
Show the code
This is what the worksheet looked like:
All Fibonacci Numbers Even Fibonacci Numbers
1
2 2
3
5
8 8
13
21
34 34
55
89
144 144
233
377
610 610
987
1,597
2,584 2,584
4,181
6,765
10,946 10,946
17,711
28,657
46,368 46,368
75,025
121,393
196,418 196,418
317,811
514,229
832,040 832,040
1,346,269
2,178,309
3,524,578 3,524,578
5,702,887
9,227,465
14,930,352 14,930,352
24,157,817
|
Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Preparation: How big is this number? I need to delimit it with commas to see.
600,851,475,143 - 600 billion!
To be prime, we know that the number cannot be larger than 600851475143/2 = 300,425,737,571.5 or 300,425,737,571.
If I am going to do this via brute force, this will help. A prime factor cannot be even, so I will have to process
about 150 billion values!
The first thing I did was write a VBA program that figured out prime numbers from 3 on up and I tried to see if
600,851,475,143 was evenly divisible by any of them. This was to reduce the size of the number I had to deal with in Excel.
It turns out that 71 (a prime) divides 600,851,475,143 evenly. The result is 8,462,696,833.
At this point vbCity Leader "great_llama" helped me out with some insight. He said that since we are only counting primes and not
keeping track of primes, we need to count primes up to the sqiare root of the number we are starting with. A good example to look at is
the square of an integer, say, 16.
1 divides 16 evenly. You don't care what the result is (16) because you're only counting divisors, not keeping track of the divisors' values.
So you count 2 (= 1 + some other divisor).
2 divides 16 easily. You don't care what the result is (8) because you're only counting divisors, not keeping track of the divisors' values.
So you count 2 (= 2 + some other divisor).
4 divides 16 easily. You don't care what the result is (4) because you're only counting divisors, not keeping track of the divisors' values.
So you count 1 because 4 x 4 = 16.
Stop counting because any number greater than 4 (8, 16) has been counted already.
Here is the VBA procedure that finds the largest prime factor of the number 600,851,475,143.
Show the code
This procedure did generate an overflow runtime error, but not before it calculated the largest prime factor.
|
Problem 4
Find the largest palindrome made from the product of two 3-digit numbers.
(A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91x99.)
I decided to solve this using the brute force method, that is, calculating every product of n x n where n ranges from 100 to 999, using Excel
& VBA.
This way also allowed me to write out every palindromic number and derive a few related statistics.
To prepare the VBA Sub procedure, I wanted to see what range of numbers would be calculated. The smallest number would be 100 x 100 = 10,000.
The largest number would be 999 x 999 = 998,001. I planned to do a digit-to-digit comparison, so I had two classes of numbers to process -
5-digit numbers and 6-digit numbers.
Show the code
This was wasteful because 100 x 101 = 101 x 100. Still, this program took just under 1 second to run.
Here are the smallest palindromes, sorted and after removing duplicates:
Values
10201
11211
12221
12321
13231
|
Problem 6
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
This was a pretty easy problem to solve and run. The only change I made was I assumed that I'd need a Double data type
being used to Problem 3 with enourmous numbers. It turns out I needed only a Long data type.
(An Integer data type produced an overflow at the 45th natural number.)
Show the code
Problem 7
What is the 10001st prime number? This was easy to solve while doing Problem 3.
|
Problem 8
Find the greatest product of five consecutive digits in the 1000-digit number (below).
This didn't take too long to code and run. The biggest challenge was making sure I didn't
lose a digit when I copied it from the web page to the VBA IDE.
Show the code
|
Problem 9
A Pythagorean triplet is a set of three natural numbers, a b c, a < b < c for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
I thought of solving this with algebra.
a + b + c = 1000 => a = 1000 - (b + c)
Substituting for a in a*a + b*b = c*c we get
1,000,000 -2,000*b -2,000*c + b*b = c*c
So I abandoned that idea.
Instead, I wrote a VBA procedure with 3 loops. This first one took 152 seconds to run.
Show the code
Then I realised I wasn't taking advantage of this constraint: a < b < c
So I ran the next program which took 120 seconds to run.
Show the code
Finally, I thought the expression
If CounterA + CounterB + CounterC = 1000 Then
might be resolved faster than this one
If CounterA ^ 2 + CounterB ^ 2 = CounterC ^ 2 Then
and if an easier expression ran as often as a more complex one, I'd get faster results. It took 5 seconds to run!
Show the code
Problem 10
Find the sum of all the primes below two million. This was easy to solve while doing Problem 3.
|
Problem 11
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 x 20 grid below?
This looked like a daunting task. I was not looking forward to looping through each cell to see if I could go right, left, up, down,
or diagonally. Then I thought, why solve this with VBA? It looked like simple worksheet formulas would work.
I screen-scraped the values from the Project Euler page, pasted them into a Notepad text file, opened Excel, did a File Open, txt file type,
delimited with spaces.
Over in cell V1 I entered the formula =A1*B1*C1*D1. This would be the start of the left/right direction. Taking advantage of
relative references I dragged the fill handle in cell V1 over to cell AL1 and let go.
Note that we could
generate only 20 - 3 = 17 products in a row. Then I selected cells V1:AL1 and dragged the fill handle in cell AL1 down to cell AL20 and let go.
This covered all possible
left & right directions. I entered the worksheet formula =MAX(V1:AL20) in cell AM20, copied and pasted special values from
AM20 to AN20, tried my luck and pasted the value in AN20 into the Project Euler answer box. No luck.
Encouraged by the speed at which I could generate 20 x 17 = 340 worksheet formulas, I started the up/down direction by
entering a worksheet formula =A1*A2*A3*A4 in cell A22. I dragged the cell A22 fill handle over to cell T22 and let go. I
selected cells A22:T22, dragged the cell T22 fill handle down to cell T38 and let go. This covered all possible
up & down directions. I entered the worksheet formula =MAX(A22:T38) in cell T39, copied and pasted special values from
T39 to T40, tried my luck and pasted the value in T40 into the Project Euler answer box. (It was bigger than the maximum value in cell AN20.)
Again, no luck.
Next, I tackled the diagonal direction. In cell V22, I entered the worksheet formula =A1*B2*C3*D4. To be sure, I did View, Toolbars,
Formula Auditing. This is one of my favorite toolbars. It is really useful if you want to check out a complex formula that perhaps someone has given you.
I selected cell V22, and clicked the Trace Precedents icon. The blue lines told me that I was using the right diagonal cells.
Relative cell referencing did the rest. I dragged the fill handle in cell V22 out to cell AL22. Then I selected cells V22:AL22 and
dragged the fill handle in cell AL22 down to cell AL38 and let go. I entered the formula =MAX(V22:AL38) into cell AM38. This maximum was
less than some of the other maximums, so I didn't bother going back to the Project Euler answer box. This covered all left-to-right diagonal cases.
Finally, the right-to-left diagonal cases. I entered formula =D1*C2*B3*A4 in cell V40, checked the formula with the Auditing Toolbar.
Dragged cell V40 fill handle over to cell AL40 and let go, selected cells V40:AL40, dragged cell AL40 fill handle down to cell AL56 and let go.
I entered formula =MAX(V40:AL56) in cell AM56, and bingo, there was the maximum of the maximums!
|
Problem 12
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.
The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
|