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

Nice script. Very compact.

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;

}
[/quote]}
print "$total \n";

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"

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.

I excluded 1 because 1 is not a prime number.

http://wiki.answers.com/Q/Why_is_1_not_a_prime_number

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

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

But the question asks for the largest such palindrome which is
913 * 993 = 906609
As my perl above finds.

Your code would be right if the iteration:
999*999, 998*999, 998*998, 997*999, 997*998, 997*997...
was in order of size of product, but it isn't. Iterating through pairs of numbers in strict order of their size of product seems to me to be extremely hard to do, which is why my perl prog iterates a bit further until it is guaranteed that subsequent pairs can not have a larger product than the largest palindrome found.