## Project Euler: Problem 4

If you been following me the last three times I've done this, then you really don't need any introductions.

Problem four is as follows:
`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.`

And my results in the usual three languages are:
Hasekell:

`module Main where import Data.List --Stole numberToList code from:--http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list-haskell.htmlnumberToList = reverse . unfoldr (\x -> if x == 0 then Nothing else let (a,b) = x `quotRem` 10 in Just (b,a)) is_palimdrome number = num_list == reverse num_list  where    num_list = numberToList number main :: IO ()main = print . maximum . filter is_palimdrome \$ zipWith (*) y z  where y = [1000,999..100]        z = [1000,999..100]`

Python:

`#!/usr/bin/python def int_to_list(number):  return map(int, str(number)) def is_palindrome(number):  local_list = int_to_list(number)  return local_list == list(reversed(local_list)) if __name__ == "__main__":  second_list = first_list = list(reversed(range(100,1000+1)))  prod_set = map(lambda i,j: i*j, first_list, second_list)   print "%s" % max(filter(is_palindrome,prod_set))`

And finally, Perl:

`#!/usr/bin/perl use strict;use warnings;use List::MoreUtils qw(pairwise); sub is_palimdrone{  my (\$number) = @_;   my @digits = split(//, \$number);  my @reversed_digits = reverse(@digits);   for (my \$i = 0; \$i < @digits; \$i++)  {    return 0 if \$digits[\$i] != \$reversed_digits[\$i];  }   return 1;} my @two = my @one = reverse((1..1000)); my @join = pairwise { \$a * \$b } @one, @two; foreach(@join){  if ( is_palimdrone(\$_))  {    print "\$_\n";    last;  }}`

Run Times
Python: 0m0.060s
Perl: 0m0.166s

For anyone that is not aware, haskell should win this statistic every time. Out of the three languages its the only one that is compiled. If anyone knows of a way to run haskell interpretively, and without using ghci, please let me know. I've tried looking on the internets for this piece of information, but have come up short.

I am still open to code suggestions or improvements. I have found these to be very helpful and useful. So thank you to everyone that has said something before.

UPDATE
So here is the new code that fixes the problem of my algo before. I'm leaving the old up just to future readers aren't confused.

Thanks goes out to Jeremiah, Tom.B, Juster, and Guillaume for the code ideas used to fix the mistakes in the code above. Thanks guys!

`module Main where import Data.List --Stole numberToList code from:--http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list-haskell.htmlnumberToList = reverse . unfoldr (\x -> if x == 0 then Nothing else let (a,b) = x `quotRem` 10 in Just (b,a)) is_palimdrome number = num_list == reverse num_list  where    num_list = numberToList number main :: IO ()main = print . maximum \$ [ x * y | x <- nums, y <- nums, is_palimdrome (x * y)]   where nums = [1000,999..100]`

Python:
`#!/usr/bin/python def int_to_list(number):  return map(int, str(number)) def is_palindrome(number):  local_list = int_to_list(number)  return local_list == list(reversed(local_list)) if __name__ == "__main__":  print "%s" % max([x * y for x in range(1000,100, -1) \                          for  y  in range(1000,100,-1) \                          if is_palindrome(x * y)])`

Perl:
`#!/usr/bin/perl use strict;use warnings;use List::Util qw(max); sub is_palimdrone{  my (\$number) = @_;   my @digits = split(//, \$number);  my @reversed_digits = reverse(@digits);   for (my \$i = 0; \$i < @digits; \$i++)  {    return 0 if \$digits[\$i] != \$reversed_digits[\$i];  }   return 1;} my @two = my @one = reverse((100..999));my @three; for my \$one (@one){  for my \$two (@two)  {    my \$three = \$two * \$one;    next unless is_palimdrone(\$three);    push @three, \$three;  }} print max(@three);`

## Project Euler: Problem 3

OK, next installment of this. :)

The problem is stated as such:
`The prime factors of 13195 are 5, 7, 13 and 29.`

What is the largest prime factor of the number 600851475143 ?

`module Main where factors count top_number  | count >= top_number = []  | zero_mod count = count : new_top: factors (count + 2) new_top  | otherwise = factors (count + 2) top_number  where new_top = round . fromIntegral \$ top_number `div` count zero_mod divisor  | divide == 0 = True   | otherwise = False  where divide = mod 600851475143 divisor --prime :: Integer -> Integral -> Boolprime divisor divided  | divided == 1 = True  | divisor >= sqrt_divided = True  | mod divided divisor == 0 = False  | otherwise = next_prime  where next_prime = prime (divisor + 2) divided        sqrt_divided = round . sqrt . fromIntegral \$ divided is_prime :: Integer -> Boolis_prime input = prime 3 input main :: IO ()main = do       let x = factors 3 600851475143       let y = map is_prime x       putStrLn \$ show \$ snd \$  maximum ( zip y x)`

Getting that sqrt function to work took me longer to figure out than I want to admit. I was having the hardest time getting the numeric types to play nice. I finally broke down and asked the haskell-beginners email list to get the answer.

Python:

`#!/usr/bin/python import math top_number = 600851475143 def zero_mod(divisor):  if top_number % divisor == 0:    return True  else:    return False def is_prime(divided):  divisor = 3  sqrt_divided = math.sqrt(divided)  if divided == 1:    return True  else:    while divisor <= sqrt_divided:      if divided == divisor:        return True      elif divided % divisor == 0:        return False      else:        divisor += 2    return True def main():  count = 3  go_to = top_number   first_list =[]   while count <= go_to:    if zero_mod(count):      first_list.append(count)      go_to = top_number / count      first_list.append(go_to)     count += 2   second_list = map(is_prime, first_list)  print "%s" % max(zip(second_list, first_list))[-1]   if __name__ == "__main__":  main()`

And finally Perl:

`#!/usr/bin/perl use strict;use warnings; my \$top_number = 600851475143; sub is_prime{  my (\$divided) = @_;  return 1 if (\$divided == 1);   my \$divisor = 3;  my \$sqrt_divided = sqrt(\$divided);   while(\$divisor <= \$sqrt_divided)  {    return 0 unless (\$divided % \$divisor);    \$divisor += 2;  }   1;} my @f;my \$new_top = \$top_number; for(my \$i = 3; \$i <= \$new_top; \$i += 2){  unless (\$top_number % \$i)  {    if (is_prime(\$i))    {      push @f, \$i;    }  }    \$new_top = \$top_number / \$i;} print \$f[-1];`

Props goes out to zloyrusski who helped me figure out a major hang up with Perl on this one. The for loop idea was his,though I really diverted from his answer. Goes to show you how much two people really can think differently. Hey Zloyrusski, is this Perl code looking better? ;) As always, I'm open to constructive criticism.

1) Code has been redone to fix the error talked about by agf. I find it a little amusing that I still get the same answer though.
2) I gotta start using less languages to do this in. If I make a mistake I've gotta change & test three different versions.
3) Times ( as requested by Caleb):
Python: 0.205s
Perl : 0.136s
4) More props for zloyrusski for the division algorithm.

## Project Euler, Problem 2

I've got problem #2 in the bag.

Problem #2 goes like this:
`Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:`

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

And my code goes as follows:

`--fibinaci :: (Num a) => a -> a -> [a]fibinaci a b  | sum' > 4000000 = []  | otherwise = sum' : fibinaci b sum'  where sum' = a + b problem2 = sum \$ filter (even) (fibinaci 0 1)`

Python:
`#!/usr/bin/python def fibinaci_list( in_list, input1, input2):  flip = True  while ( input1 + input2 < 4000000):    if( flip == True):      input1 = input1 + input2      in_list.append(input1)      flip = False    else:      input2 = input1 + input2      in_list.append(input2)      flip = True  def even(n):  if n % 2 == 0:    return True  else:    return False  def main():  first_list = []  fibinaci_list(first_list, 0, 1)  second_list = filter(even, first_list)  print "%s" % (sum(second_list)) if __name__ == "__main__":  main()`

And finally, Perl:
`#!/usr/bin/perl my \$total = 0;my \$count1 = 0;my \$count2 = 1;my \$flip = 1; while( \$count2 + \$count1 < 4000000){  if ( \$flip == 1)  {    \$count1 += \$count2;    if ( \$count1 % 2 == 0)    {      \$total += \$count1;    }    \$flip = 0;  }  else  {    \$count2 += \$count1;    if ( \$count2 % 2 == 0)    {      \$total += \$count2;    }    \$flip = 1;  }} print \$total;`

Originally, I tried to copy the Python algorithm to Perl, using an array instead of a list. That didn't work. The program would always fail due to out of memory errors. To solve this problem I changed the program to work without using arrays and just took the whole fibinaci function out and put it into main.

As always, constructive comments for the code are welcomed.

## Project Euler: Problem 1

So I'll admit it, I'm more than acceptably late to this party. OJ started working on these problems years ago, while I was still coding away on other stuff at school. Now that I'm not in school and needing a challenge I'm doing the best I can to tackle the problems at Project Euler. Since I'm also trying to pick up Haskell, this makes for a good way to learn the language. This isn't my first time using a Functional Programming language. But the last time I tried, it was forced upon me at school with inadequate assistance and the whole experience left a bad taste in my mouth. I'm glad that getting over the bad experience and learning something new at the same time.

I've started keeping a github repo with my solutions for the various problems. If anyone is interested in commenting on my code please do so. I welcome all constructive criticism.

To start this thing off; problem one reads,
“If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.”

Being this one was simple. I coded it up in Haskell, Python, and Perl.

`problem1 = sum \$ filter (\x -> mod x 3 == 0 || mod x 5 == 0) [1..1000]problem1' = sum \$ filter (\x -> mod x 3 == 0 || mod x 5 == 0) [1..999]`

Python:
`#!/usr/bin/python def threeorfive(n):  if ( n % 3 == 0 or n % 5 == 0):    return True  else:    return False def main():  first_list = range(1,1000)  second_list = filter(threeorfive, first_list)  print "%s" % (sum(second_list)) if __name__ == "__main__":  main()`

Perl:
`#!/usr/bin/perl my \$count = 0;my \$total = 0; while ( \$count < 1000){  if ( \$count % 3 == 0 or \$count % 5 == 0)  {    \$total += \$count;  }   \$count++;} print \$total;`

One thing that is nice about doing this in different languages, is that you get to become aware of the differences between some of those languages. For instance in Python the range function works a little differently than I expected. I was expecting an inclusive range function, one in which the 10 is included in the list. But that is now how Python's range works. It gives me 10 numbers, starting with 1, the end result is a list ending in 9. It's not a big deal and easily fixable, but just not something I was expecting. That is why the Haskell code has to functions in it. Just to verify that the Python code was correct.

I'll be posting more answers as I complete them. So expect to see some random posts with Euler solutions in them.