- 16 Sep '09 19:30Any 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. - 17 Sep '09 20:55995 * 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) - 17 Sep '09 22:28 / 1 edit924 * 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;

} - 18 Sep '09 00:13

Nice script. Very compact.*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;

} - 18 Sep '09 01:51 / 1 edityes. 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 - 18 Sep '09 23:46 / 1 editI 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. - 19 Sep '09 17:07This 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"; - 19 Sep '09 18:48 / 1 editSimilar 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"; - 20 Sep '09 16:12 / 9 editsManaged 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"; - 29 Sep '09 14:51

Interesting. Running the same thing in VB I get 142,913,828,923*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";

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" - 29 Sep '09 16:53 / 2 editsMatlab 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) - 29 Sep '09 19:18

I excluded 1 because 1 is not a prime number.*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.

http://wiki.answers.com/Q/Why_is_1_not_a_prime_number - 29 Sep '09 19:27 / 1 edit

But the question asks for the largest such palindrome which is*Originally posted by Palynka***Matlab code for the first problem:**

.....

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

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.