# Project Euler

Kristaps
Posers and Puzzles 16 Sep '09 19:30
1. 16 Sep '09 19:30
Any math/programming geeks (like me) here? I recently stumbled upon this fun website http://projecteuler.net/. It has a lot of nice mathematical problems, ranging from very easy to very difficult, that usually require computer programming to solve. It's quite fun, been bothering me for the last few days.

An example problem:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.
2. StarValleyWy
BentnevolentDictater
17 Sep '09 20:55
995 * 583 = 580085

I didn't spend a lot of time on this, but it seems to work. Here is the VB code... It hits when tries = 4017

Dim V1, V2 As Double
Dim strPal As String
Dim s1, s2 As String
Dim Eureka As Boolean

Dim j As Integer
Dim tries As Long

V1 = 999
V2 = 999

Do While Eureka = False
tries = tries + 1

strPal = CStr(V1 * V2)
s1 = Left(strPal, 3)
s2 = ""

For j = Len(strPal) To Len(strPal) - 2 Step -1
s2 = s2 & Mid(strPal, j, 1)
Next j

If s1 = s2 Then
Eureka = True
Else

V2 = V2 - 1
If V2 < 100 Then
V1 = V1 - 1
V2 = 999
End If

End If

If V1 < 100 Then Exit Do

Loop

If Eureka Then MsgBox "Eureka! Answer = " & CStr(V1) & " * " & V2 & " = " & CStr(V1 * V2)
3. 17 Sep '09 22:281 edit
924 * 962 = 888888
913 * 993 = 906609

second is the largest combination

Got that with the following perl script which runs in about 0.5 secs (I love perl).
sorry about the lack of indentation, I can't for the life of me work out how to make this silly forum parser keep leading spaces!
It goes through the inner loop 3221 times, so it takes about 0.8% of the iterations that an exhaustive search would.

my (\$num1, \$largest) = (999, 0);
NUM1: while (\$num1 >= 100) {
last NUM1 if \$largest and \$largest > \$num1 * 999;
my \$num2 = 999;
NUM2: while (\$num2 >= \$num1) {
my \$ans = \$num2 * \$num1;
last NUM2 if \$largest and \$largest > \$ans;
my \$rev = reverse(\$ans);
if (\$rev eq \$ans) {
print "\$num1, \$num2, \$ans, \$rev \n";
\$largest = \$ans;
}
\$num2 = \$num2 - 1;;
}
\$num1 = \$num1 - 1;
}
4. Palynka
Upward Spiral
18 Sep '09 00:13
Originally posted by iamatiger
924 * 962 = 888888
913 * 993 = 906609

second is the largest combination

Got that with the following perl script which runs in about 0.5 secs (I love perl).
sorry about the lack of indentation, I can't for the life of me work out how to make this silly forum parser keep leading spaces!
It goes through the inner loop 3221 times, so it takes about 0. ...[text shortened]... \n";
\$largest = \$ans;
}
\$num2 = \$num2 - 1;;
}
\$num1 = \$num1 - 1;
}
Nice script. Very compact.
5. StarValleyWy
BentnevolentDictater
18 Sep '09 01:511 edit
yes. very nice. I like yours better than mine.

Here is a small revision in vb to get all items. It takes about 1 second to run on this machine. Kind of slow, but it gets there eventually.

Dim strPal As String
Dim s1, s2 As String
Dim biggest As Double
Dim smallest As Double
Dim intCount As Integer
Dim j As Integer
Dim v1 As Double
Dim v2 As Double
Dim strSmall, strLarge As String

smallest = 990000
intCount = 0

For v1 = 100 To 999
For v2 = 100 To 999

strPal = CStr(v1 * v2)
s1 = Left(strPal, 3)
s2 = ""

For j = Len(strPal) To Len(strPal) - 2 Step -1
s2 = s2 & Mid(strPal, j, 1)
Next j

If s1 = s2 Then

intCount = intCount + 1

If CDbl(strPal) > biggest Then
biggest = CDbl(strPal)
strLarge = "Largest = " & CStr(v1) & " * " & CStr(v2) & " = " & strPal
End If

If smallest > CDbl(strPal) Then
smallest = CDbl(strPal)
strSmall = "Smallest = " & CStr(v1) & " * " & CStr(v2) & " = " & strPal
End If

End If

Next v2
Next v1

Debug.Print "There are " & CStr(intCount) & " palindromes"
Debug.Print strLarge
Debug.Print strSmall

Results:
There are 2470 palindromes
Largest = 913 * 993 = 906609
Smallest = 101 * 101 = 10201
6. 18 Sep '09 23:461 edit
I like C.

The code:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int a, i, j;
char str[10];

for (i = 999; i > 900; i--)
{
for (j = i; j > 900; j--)
{
a = i*j;
sprintf(str, "%d", a);

if (str[0] == str[5] && str[1] == str[4] && str[3] == str[2])
{
printf("%s\n", str);

return 0;
}
}
}
}

Pretty much brute force, nothing fancy.

I agree about the indent spacing. Code here looks ugly.

One more problem:
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
7. 19 Sep '09 17:07
This perl script gets 142913828922 in about 10 seconds

my \$max = 2000000; #up to 2 million
my \$end = int(sqrt(\$max));
my @notaprime = (0) x \$max;
#Sieve of Eratosthenes
for (my \$num = 2; \$num <= \$end; \$num++) {
next if \$notaprime[\$num];
my \$total = \$num;
while (\$total <= \$max) {
\$total = \$total+\$num;
\$notaprime[\$total] = 1;
}
}

#finished sieving, compute total
my \$primetotal = 0;
foreach my \$this_num (2..\$max) {
\$primetotal += \$this_num unless \$notaprime[\$this_num];
}
print "\$primetotal \n";
8. 19 Sep '09 18:481 edit
Similar runtime, same answer, but a bit more concise:

use strict; use warnings;
my \$max = 2000000; #up to 2 million
my \$end = int(sqrt(\$max));
my @notaprime = (0) x \$max;
my \$total = 0;
#Sieve of Eratosthenes with prime summing inside
for (my \$num = 2; \$num <= \$max; \$num++) {
next if \$notaprime[\$num];
\$total += \$num;
next if \$num > \$end;
for (my \$this = \$num+\$num; \$this <= \$max; \$this+=\$num) {
\$notaprime[\$this] = 1;
}
}
print "\$total \n";
9. 19 Sep '09 20:354 edits
Seems to scale fairly close to linearly. 101 seconds for sum of primes to 20 million, which it says comes to 12272577818052
10. 20 Sep '09 16:129 edits
Managed a rudimentary form of indentation with [ quote ]:

use strict; use warnings;
my \$max = 2000000; #up to 2 million
my \$end = int(sqrt(\$max));
my @notaprime = (0) x \$max;
my \$total = 0;
#Sieve of Eratosthenes with prime summing inside
for (my \$num = 2; \$num <= \$max; \$num++) {
next if \$notaprime[\$num];
\$total += \$num;
next if \$num > \$end;
for (my \$this = \$num+\$num; \$this <= \$max; \$this+=\$num) {[quote]\$notaprime[\$this] = 1;
}
[/quote]}
print "\$total \n";
11. StarValleyWy
BentnevolentDictater
29 Sep '09 14:51
Originally posted by iamatiger
This perl script gets 142913828922 in about 10 seconds

my \$max = 2000000; #up to 2 million
my \$end = int(sqrt(\$max));
my @notaprime = (0) x \$max;
#Sieve of Eratosthenes
for (my \$num = 2; \$num <= \$end; \$num++) {
next if \$notaprime[\$num];
my \$total = \$num;
while (\$total <= \$max) {
\$total = \$total+\$num;
\$notaprime[\$total] = 1;
}
...[text shortened]... {
\$primetotal += \$this_num unless \$notaprime[\$this_num];
}
print "\$primetotal \n";
Interesting. Running the same thing in VB I get 142,913,828,923

Could the difference be the initial prime "1"? I started with that value then added all else to it.

btw... unless you have something besides the mod function and an extensive iteration from 2 to X.... don't use VB. It took about two hours!

Most of that could be helped though with a better "IsPrime" function, which I'm too lazy to research. Code below...

"Private Sub Command2_Click()

Dim max As Double
Dim j As Double
Dim dSum As Double

dSum = 1
max = 2000000

For j = 2 To max
Label2 = CStr(j)
If Prime(j) Then
dSum = dSum + j
Label2.Caption = CStr(j)
Debug.Print j
DoEvents

End If
Next j

MsgBox "Sum Of Primes < 2,000,000 = " & CStr(dSum)

End Sub
Private Function Prime(ByVal dblCheckValue As Double) As Boolean
Dim number As Double

For number = 2 To dblCheckValue - 1
If dblCheckValue Mod number = 0 Then
Prime = False
Exit Function
End If
Next number
Prime = True
End Function"
12. Palynka
Upward Spiral
29 Sep '09 16:154 edits
I love Matlab; ðŸ˜€

sum(primes(2000000))

Takes less than a second. (Elapsed time is 0.056295 seconds.)

Edit - SVW, yes I suspect it's because of adding 1. The original example excluded it...
13. Palynka
Upward Spiral
29 Sep '09 16:532 edits
Matlab code for the first problem:

start = 999;
num1 = start;
num2 = start;
finish = 0;

while finish == 0

if num2 < num1
num1 = num1-1;
num2=start;
end

temp = num2str(num1*num2);

if temp == temp(numel(temp):-1:1)
finish = 1;
display([num1;num2;num1*num2])
else
num2 = num2-1;
end

end

(as others, I get 924*962 = 888888 in 0.22 sec)
14. 29 Sep '09 19:18
Originally posted by StarValleyWy
Interesting. Running the same thing in VB I get 142,913,828,923

Could the difference be the initial prime "1"? I started with that value then added all else to it.

I excluded 1 because 1 is not a prime number.