Problem Definition: Euler Problem 5

I am rather happy with this python version because I can basically get it done in about 15 min in total. Some useful primitives have been developed in module p3 (See my previous post, little erlang exercise 3)

“”“
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
”“”


from p3 import isprime, factorise

def product(x, y):
 return x * y

if name == “main”:
 factors = dict()
 for l in [factorise(i) for i in xrange(2, 21)]:
     tmp = dict()
     # count them
     for n in l:
         tmp[n] = 1 + tmp.get(n, 0)
     # reguster the max frequency of factor
     for k, v in tmp.items():
         factors[k] = max(factors.get(k, 0), v)

 print reduce(product, [pow(k, v) for k,v in factors.items()])

-module(p5).
-import(p3).
-export([main/0, get_factor_freq_lst/1]).

%% run this to print the result
main() –>
  L = [ p3:factorise(X) || X <– lists:seq(1, 20)],   
  io:format(“~f~n”, [product(get_factor_freq(L))]).   

get_factor_freq(L) –>
  Dict = dict:new(),
  get_factor_freq(L, Dict).

%% spec: H, T are list of list of number
%% e.g. [ [N1, N1, N2…], [N1, N2…], …]
get_factor_freq([H|T], Dict) –>
  Dist = get_factor_freq_lst(H),
  D1 = dict:from_list(Dist),
  D2 = dict:merge(fun(K, X, Y) –> update_if_bigger(K, X, Y) end, D1, Dict),
  get_factor_freq(T, D2);
get_factor_freq([], Dict) –>
  dict:to_list(Dict).  %% has to convert to list

%% Aux function
update_if_bigger(, Initial, NewValue) when Initial < NewValue –>
  NewValue;
update_if_bigger(, Initial, _) –>
  Initial.

%% This function assumes the list is sorted
%% This function is to delinate a list of number
%% into a list of {Key, Frequency}
get_factor_freq_lst([A|T]) when is_integer(A) –>
  get_factor_freq_lst([{A, 1}|T]);
get_factor_freq_lst([{A, N}, A|T]) when is_integer(A) –>
  get_factor_freq_lst([{A, N + 1}|T]);
get_factor_freq_lst([{A, N}, B|T]) when is_integer(A), is_integer(B), A /= B –>
  get_factor_freq_lst([{B, 1}|T] ++ [{A, N}] );
get_factor_freq_lst(L) –>
  L.

%% find the product of a list of tuple {Base, Power)
product(L) –>
  product(L, 1).
product([], Sum) –>
  Sum;
product([{Base, Power}|T], Sum) –>
  product(T, Sum * math:pow(Base, Power)).

Problem Definition: Euler Problem 4

Through this exercise, I realised that I can reverse a string using a [::-1] operator. Really cryptic, but yet handy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# A palindromic number reads the same both ways. The largest palindrome
# made from the product of two 2-digit numbers is 9009 = 91 x 99.
# 
# Find the largest palindrome made from the product of two 3-digit numbers.

def isPalindromic(Num):
  #  For string reversal, pls check this url:
  #
  #    http://www.python.org/doc/2.3.5/whatsnew/section-slices.html

  N = str(Num)
  l = len(N)
  div, mod = divmod(l, 2)
  if mod == 1: # odd
    fh = N[0:l/2]
    sh = N[1+l/2:]
    # print “%s %s” % (fh, sh)
  else:
    fh = N[0:l/2]
    sh = N[l/2:]
  return fh == sh[::-1]


if __name__ == "__main__":
  g = [ x * y for x in xrange(100, 999) for y in xrange(100, 999) ]
  print max(filter(lambda x: isPalindromic(x), g))

Here comes an erlang version. In this rare occasion, erlang runs faster than python. It is probably because, first of all, the list comprehension I used in erlang produces a smaller list. Secondly the test of palindromic is more straightforward in the erlang version.

I will revisit the python version, later, when I get a bit more time.

1
2
3
4
5
6
7
8
9
10
11

-module(p4).
-export([findLargestProduct/0]).

isPalindromic(N) when is_list(N) –>
  N == lists:reverse(N).

findLargestProduct() –>
  List = [X * Y || X <– lists:seq(100, 999),
                   Y <– lists:seq(100, 999),
                   isPalindromic(integer_to_list(X * Y))],
  lists:max(List).

Problem Definition: Euler Problem 3

Obviously, these scripts did not actually implement the solution. The problem statement required to pick the largest factor, but I just realized I had not done it.

Python Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#
# The prime factors of 13195 are 5, 7, 13 and 29.
#
# What is the largest prime factor of the number 317584931803?
#

import sys

primes = []

def isprime(N):
  #  Original version use xrange, but caused
  #
  #  "OverflowException: long int too large to convert to int”
  # 
  #  when taking in a large number
  # 
  #  So, I have to use while loop to replace “for i in xrange(2, N):”
  #
  #  And in order to speed up the process, the prime calculation result
  #  is cached
  global primes

  # we have already tested it
  if N in primes:
    return True

  # use the prime results first 
  for i in primes:
    if (N % i) == 0:
      return False

  # now computation is required
  maxprime = 2
  if len(primes) > 0:
    maxprime = primes[-1]

  i = maxprime + 1
  while i < N:
    if (N % i) == 0:
      return False
    i = i + 1

  primes.append(N)
  return True


def factorise(N):
  #
  #  To factorise a integer
  #

  # short cut
  global primes
  res = []

  if N in primes:
    res.append(N)
    return res

  # original algorithm
  idx = 2
  while idx <= N:
    if isprime(idx):
      div, mod = divmod(N, idx)
      if mod == 0:
        res.append(idx)
        res.extend(factorise(div))
        break
    idx = idx + 1
  return res

if __name__ == ”__main__“:
  print factorise(int(sys.argv[1]))

Erlang Solution

Here comes the erlang version. There is some performance issue with this version. hopefully I would have some free time soon to improve the algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

-module(p3).
-export([isprime/1, factorise/1]).

%%
%% prime means it is not divisible by any numbers other than 1 and itself.
%%
isprime(1) –>
 false;

isprime(2) –>
 true;

isprime(N) when N > 2 –>
 Pid = self(),
 C = lists:seq(2, N – 1),
 process_flag(trap_exit, true),
 lists:map(fun(Div) –>
               spawn_link(fun() –>
                   test_if_divisible(Pid, N, Div)
                   end)
               end, C),
 isprime_poll(length(C)).


%%
%% Message loop: to listen and receive message from voters
%%
isprime_poll(0) –>
 true;
isprime_poll(NumVote) –>
 receive
   {nondivisible, } –>
       isprime_poll(NumVote – 1);
   {divisible, } –>
       clean_mailbox(),
       false
 end.

%%
%% To clear away any messages in mailbox
%%
clean_mailbox() –>
 receive
   _ –>
     clean_mailbox()
   after 0 –> ok
 end.

%%
%%
%%
test_if_divisible(Pid, N, Div) –>
 case N rem Div of
   0 –> Pid ! {divisible, Div};
   _ –> Pid ! {nondivisible, Div}
 end.

%%%
%%% To factorise an integer – wrappers
%%%
factorise(N) when is_list(N) –>
   N1 = string:to_integer(N),
   factorise(N1, 2, []);

factorise(N) –>
   factorise(N, 2, []).

%%%
%%% To factorise an integer
%%%
factorise(N, Factor, Result) when Factor < N+1  –>
 case isprime(Factor) of
   true –>
     if
       (N rem Factor) == 0 –>
         %% io:format("Residual is 0 by Factor ~p~n”, [Factor]),
         factorise(N div Factor, 2, [Factor|Result]);
       true –>
         factorise(N, Factor + 1, Result)
     end;
   false –>
       factorise(N, Factor + 1, Result)
 end;

factorise(_, _, Result) –>
 R = lists:reverse(Result),
 %% io:format(“~p~n”, [R]),
 R.

Problem Definition: Euler Problem 2

In order to solve this problem in python, I have used the yield keyword to implements a generator to provide a sequence of Fibonacci’s numbers. I think I can do a better work in using list comprehension in the main routine to filter and add up the even numbers, but the current version is basically good enough.

“”“

Euler 2

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 one million.


”“”
def gen_fib_seq():
a = 1
b = 2
yield a
yield b
try:
 while 1:
   c = a + b
   a, b = b, c
   yield c
except StopIteration:
 pass


if name == “main”:
b = 0
onemillion = 1000000
for x in gen_fib_seq():
 if x % 2 == 0:
   if b + x < onemillion:
     b = b + x
   else:
     break
print b

-module(p2).
-export([main/0]).

start() –> spawn(fun() –> fib(0, 1) end).

fib(N, M) –>
receive
 {Pid, next} –>
   Pid ! {self(), N + M},
   fib(M, N+ M)
end.

get_next_fib(Pid) –>
Pid ! {self(), next},
receive
 {, N} –>
   %% io:format(“~p~n”, [N])
   N
end.

%% accumulator
acc(N, Pid, Acc) when (N rem 2) =:= 1 –>
 N1 = get_next_fib(Pid),
 acc(N1, Pid, Acc);
acc(N, Pid, Acc) when N + Acc < 1000000 –>
 N1 = get_next_fib(Pid),
 acc(N1, Pid, Acc + N);
acc(, _, Acc) –>
 Acc.


%%%
%%% Program main()
%%%
main() –>
 Pid = start(),
 Acc = acc(1, Pid, 0),
 Acc.