Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  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. Standard member 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:28 / 1 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. Standard member 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. Standard member StarValleyWy
    BentnevolentDictater
    18 Sep '09 01:51 / 1 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:46 / 1 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:48 / 1 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:35 / 4 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:12 / 9 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. Standard member 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. Standard member Palynka
    Upward Spiral
    29 Sep '09 16:15 / 4 edits
    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...
  13. Standard member Palynka
    Upward Spiral
    29 Sep '09 16:53 / 2 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.

    http://wiki.answers.com/Q/Why_is_1_not_a_prime_number
  15. 29 Sep '09 19:27 / 1 edit
    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.