No Permission

Ah, Problem 7, the one we knew was coming.

“What is the 10001st prime number?”

The basics are simple enough. Brute force a primality test via trial division and use the test to find 10001 prime number. So I did that, got the answer.

But it took 2:24 on my netbook, and the rule of Project Euler is that it should take less than 1:00.

So it was time to optimize! I started with the simplest optimization, limiting the upper bound of the trial division in the square root of the number being tested. If you’ve made it that far without finding a factor, you’re not going to (other than the number itself, of course), so it’s prime.

Once I added that, the time dropped to under 4 seconds, which surprised me. I didn’t expect that dramatic a drop from such a basic optimization. Lesson learned there. Sometimes it’s worth just a little more effort to make things much, much faster.

It’s also worth noting, however, that there a number of other simple optimizations I’m not adding in since I’m already well under the goal.

Called by “euler7:nthprime(10001,2)” I’m seeding it with the first prime there. In most of these I could eliminate one of my seed parameters by having alternate versions of the functions for the base case, but I do it this way to simplify the code itself.

Prime Grade A Code-

 -module(euler7).
 -import(math).
 -export([nthprime/2]).

nthprime(N,Prevprime) ->
   if N >= 2 ->
        NthPrime = findprime(Prevprime+1),
        nthprime(N-1,NthPrime);
   true ->
       Prevprime
   end.     

findprime(Start) ->
   Max = math:sqrt(Start),
   Prime = isprime(Start,2,Max),
   if Prime == true ->
      Start;
   true ->
          findprime(Start+1)
   end.

isprime(N,PFactor,Max)->
   if PFactor =< Max ->
          if  N rem PFactor == 0 ->
              false;
          true ->
              isprime(N,PFactor+1,Max)
          end;
    true ->
          true
    end.

Problem 4 is an interesting one. “A palindromic number reads the same both ways. Find the largest palindrome made from the product of two 3-digit numbers.”

I thought about this for a few minutes and decided the best way to approach it would be to build candidate palindromic numbers and and then test them to see if they were the product of two 3 digit numbers.

It’s easy to see that the product of two 3 digit numbers could at most be 6 digits, so I decided that I would start building my candidate palindromes by counting down from 999 and adding the mirror of the number as a suffix. Example – take 998 and add 899 to the end for 998899. Then I would test each candidate by dividing by all possible three digit numbers and seeing if I could find a three digit cofactor for any even divisions. For example, if a candidate was evenly divisible by 123, was the cofactor also a three digit number?

So this problem was mostly centered in the approach. Once I’d settled on that, the Erlang code came easily. A little more work than I’d like building the palindromes due to single assignment, but nothing too bad. I can see how single assignment will be a pain in some situations though.

The code – - edoc ehT

 -module(euler4).
 -import(lists).
 -export([greatestpalindrome/1]).

 greatestpalindrome(N) ->
     Greatest = palindrome(N),
     io:format("Greatest is ~w", [Greatest]).

 palindrome(N) ->
    if N >= 100 ->
      Candidate = buildpalindrome(N),
      Success = testpalindrome(Candidate,999),
      if Success == true ->
         Candidate;
      true ->
         palindrome(N-1)
      end;
    true ->
      io:format("no match found~n")
    end.  

 buildpalindrome(N) ->
    Nstring = integer_to_list(N),
    ReverseN = lists:reverse(Nstring),
    Palindrome = Nstring ++ ReverseN,
    Npalindrome = list_to_integer(Palindrome),
    Npalindrome.

testpalindrome(N,Testfactor) ->
    if Testfactor >= 100 ->
       if N rem Testfactor == 0 ->
          Cofactor = round(N / Testfactor),
            if Cofactor >= 100, Cofactor =< 999 ->
                true;
            true ->
                false
            end;
       true ->
            testpalindrome(N,Testfactor - 1)
       end;
     true ->
       false
    end.

When I first read Problem 3 I thought it was going to be more involved than it turned out to be.

“What is the largest prime factor of the number 600851475143 ?”

And I started thinking I’ll need to list the factors and test them for primality, or find primes first and test only those for being factors, etc.

But after thinking about how to actually factor the number, I remembered factor trees and how they’d lead me to prime factors by default. And as an added bonus, factor trees are inherently recursive! This wasn’t going to be so bad after all.

For some reason I got hooked on the idea that I needed to build a list of the factors, and then at the end I would find the largest of them. Eventually I realized I just needed to track the largest so far; I think I just wanted to fiddle with lists in Erlang.

The Erlang came pretty easy to me this time. I’m adjusting to the structures imposed by Single Assignment, which was conceptually a challenge at first. The idea of immutable variables just seemed so wrong! But I’ve read more and understand why that’s the case and I’m getting a feel for how to deal with them.

The only real Erlang catch came from the line that finds the co-factor of the most recently found factor – “Cofactor = round(N / Factor)”. You’ll notice the “round” function there. The division returned a floating point number, when what I wanted was an integer. Casting variable types turns out to be a bit clunky in Erlang, mostly done by BIFs (Built In Functions) with unwieldy names like “integer_to_list” and so on. But there is no “float_to_integer” BIF! So it had to be the “round()” function. While fine in this case, I’m not sure this will always do what I need it to do.

A couple of other notes- This isn’t very optimized, I’m intentionally not optimizing in this initial pass. I do plan to revisit and refactor down the road, once I have a better idea what I’m doing. I did sneak in an optimization in the factor search, limiting the upper end to the square root of the number we’re looking for factors of. That’s a very simple trick which does save some iterations (if you haven’t found a factor by the time you reach the square root of a number, you’re not going to). I could have further limited the search range by limiting the lower end to being equal to or greater than the previously found factors, but that would add parameters to the functions so I skipped it for now.

One last thing, the program doesn’t seem to work properly on very large numbers (giving me a factor of “2″ on numbers that aren’t even, for example), I’m not sure why. Probably some sort of overflow condition.

My code of codes-

 -module(euler3).
  -import(math).
  -export([greatestprimefactor/1]).

  greatestprimefactor(N) ->
     Greatest = factor(1,N),
     io:format("GPF is ~w~n", [Greatest]).

  factor(Greatestsofar,N) ->
    Max=math:sqrt(N),
    Factor = nextfactor(Max,2,N),
    if
      Factor > Greatestsofar ->
            Newgreatest = Factor;
      true ->
            Newgreatest = Greatestsofar
    end,
    Cofactor = round(N / Factor),
    io:format("Factor ~w~n",[Factor]),
    if
      Cofactor == 1 ->
           Newgreatest;
      true->
           factor(Newgreatest,Cofactor)
    end.

 nextfactor(Max,X,N)->
      if
       N rem X == 0 ->
 	    X;
       X =< Max ->
            nextfactor(Max,X+1,N);
       true ->
            N
       end.

Getting started with my quest via my first attempt at a solution in Erlang to Project Euler’s problem number 1.

The problem itself is simply stated : “Find the sum of all the multiples of 3 or 5 below 1000.”

A naive algorithm is immediately apparent- cycle through each number between below 1000 and sum those that are evenly divisible by 5 or 3. While hardly sophisticated or efficient, it’s an algorithm that will work.

In thinking about how to do this in a functional language like Erlang, it seems the obvious approach is recursion. A function that takes a number N as an input and calls itself for N-1, adding N to the result of the recursive call if N is evenly divisible by 3 or 5. I also decided to make the determination if N was a 3 or 5 multiple its own function.

So conceptually, the answer and the approach came pretty quickly. I stumbled a bit on implementation mostly due to not understanding Erlang’s if-statement at all. Once I sussed out the oddities there (including not being able to call a function in a guard expression- this puzzles me, but I also get the feeling that understanding why this is true is important to my grokking Erlang. I must explore further), the functions fell into place and I had a tiny understanding of how to start thinking about this sort of thing.

It’s been too long for me. Tiny little baby steps needed. I could have written this in a C-like language as fast as I can type. This took a bit longer.

My magnificent code for Problem 1.

-module(euler1).
-export([sumof3and5multiples/1]).

sumof3and5multiples(0)->
	0;
sumof3and5multiples(N) ->
	Multiple = ismultipleof3or5(N),
	if
          Multiple == true ->
	    N + sumof3and5multiples(N-1);
          true ->
	    sumof3and5multiples(N-1)
	end.   	

ismultipleof3or5(X) ->
	if
	   X rem 3 == 0 ->
	     true;
	   X rem 5 == 0 ->
	     true;
	   true ->
	     false
	end.