Project Euler

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.

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)

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;
}

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;
}

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

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.

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";

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";

Seems to scale fairly close to linearly. 101 seconds for sum of primes to 20 million, which it says comes to 12272577818052

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;

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";

I love Matlab; 😀

sum(primes(2000000))

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

Answer is 142913828922

Edit - SVW, yes I suspect it's because of adding 1. The original example excluded it...

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)

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.

Originally posted by Palynka
Matlab code for the first problem:
.....

(as others, I get 924*962 = 888888 in 0.22 sec)