euler.erl

% Project Euler in Erlang.
% John Evans <john@jpevans.com>

% Notes to myself:
% timer:tc(Module, Function, Arguments) -> {Time, Value}

-module(euler).
-export([euler1/0, euler2/0, euler3/0, euler4/0, euler5/0, euler6/0,
         euler7/0]).



% Euler #1
% Answer: 233168
%
% 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.
e1acc(N, MAX, ACC) when N >= MAX -> ACC;
e1acc(N, MAX, ACC) when (N rem 3 == 0) or (N rem 5 == 0) ->
    e1acc(N + 1, MAX, ACC + N);
e1acc(N, MAX, ACC) -> e1acc(N + 1, MAX, ACC).

euler1() -> e1acc(1, 1000, 0).


% Euler #2
% Answer: 4613732
%
% 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.

e2_next(ACC, C) when C rem 2 == 0 -> ACC + C;
e2_next(ACC, _) -> ACC.

e2acc(_, B, ACC) when B > 4000000 -> ACC;
e2acc(A, B, ACC) ->
    C = A + B,
    e2acc(B, C, e2_next(ACC, C)).

euler2() -> e2acc(1, 2, 2).


% Euler #3
% Answer: 6857
%
% The prime factors of 13195 are 5, 7, 13 and 29.
%
% What is the largest prime factor of the number 600851475143 ?

ceiling(X) ->
    T = erlang:trunc(X),
    case (X - T) of
        Neg when Neg < 0 -> T;
        Pos when Pos > 0 -> T + 1;
        _ -> T
    end.

is_prime_search(1, _) -> true;
is_prime_search(N, PP) when PP rem N == 0 -> false;
is_prime_search(N, PP) -> is_prime_search(N - 1, PP).

is_prime(PP) -> is_prime_search(ceiling(math:sqrt(PP)), PP).

e3search(0, _) -> {error, boom};
e3search(N, Target) when Target rem N == 0 ->
    case is_prime(N) of
        true -> N;
        _ -> e3search(N - 1, Target)
    end;
e3search(N, Target) -> e3search(N - 1, Target).

euler3() -> e3search(ceiling(math:sqrt(600851475143)), 600851475143).


% Problem #4
% Answer: 906609
%
% 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.

% Can't find this in Erlang, though I'm sure it's there:
max(X, Y) when X > Y -> X;
max(_, Y) -> Y.

% Since we know we are checking numbers we don't have to worry about
% spaces or puncutation.
is_palindromic_number(N) ->
    S = integer_to_list(N),
    S == lists:reverse(S).

e4next_a(1) -> 999;
e4next_a(A) -> A - 1.

e4next_b(1, B) -> B - 1;
e4next_b(_, B) -> B.

e4search(1, 1, ACC) -> ACC;
e4search(A, B, ACC) ->
    C = A * B,
    NewA = e4next_a(A),
    NewB = e4next_b(A, B),
    e4search(NewA, NewB, 
        case is_palindromic_number(C) of
            true -> max(C, ACC);
            false -> ACC
        end).

euler4() -> e4search(999, 999, 0).


% Problem #5
% Answer: 232792560
% Took 6.8 minutes, so could be better.
%
% 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?

% This took 6.8 minutes
% divisible_by_all(_, []) -> true;
% divisible_by_all(N, PotentialDivisors) ->
%     [H|T] = PotentialDivisors,
%     case N rem H of
%         0 -> divisible_by_all(N, T);
%         _ -> false
%     end.
% 
% e5search(N) ->
%     case divisible_by_all(N, [20,19,18,17,16,15,14,13,12,11]) of
%         true -> N;
%         _ -> e5search(N + 1)
%     end.
% 
% euler5() -> e5search(2520).

% This took even longer... 10 minutes? wtf
lcm(A, B, N) when N rem A == 0, N rem B == 0 -> N;
lcm(A, B, N) -> lcm(A, B, N+1).

lcm(A, B) -> lcm(A, B, 1).


e5search(Acc, N) when N > 20 -> Acc;
e5search(Acc, N) -> e5search(lcm(Acc, N), N+1).

euler5() ->
    e5search(lcm(1, 2), 2).

% Problem #6
% Answer: 25164150
%
% The sum of the squares of the first ten natural numbers is,
%     1² + 2² + ... + 10² = 385
% The square of the sum of the first ten natural numbers is,
%     (1 + 2 + ... + 10)² = 55² = 3025
% Hence the difference between the sum of the squares of the first
% ten natural numbers and the square of the sum is 3025 - 385 = 2640.
%
% Find the difference between the sum of the squares of the first one
% hundred natural numbers and the square of the sum.

square(N) -> N * N.

sum_of_squares(Min, Max, Acc) when Min > Max -> sum_of_squares(Max, Min, Acc);
sum_of_squares(Min, Max, Acc) when Min == Max -> square(Min) + Acc;
sum_of_squares(Min, Max, Acc) -> sum_of_squares(Min + 1, Max, square(Min) + Acc).

sum_of_squares(Min, Max) -> sum_of_squares(Min, Max, 0).

sum_range(Min, Max, Acc) when Min > Max -> sum_range(Max, Min, Acc);
sum_range(Min, Max, Acc) when Min == Max -> Min + Acc;
sum_range(Min, Max, Acc) -> sum_range(Min + 1, Max, Min + Acc).

sum_range(Min, Max) -> sum_range(Min + 1, Max, Min).

square_of_sum(Min, Max) -> square(sum_range(Min, Max)).

euler6() -> square_of_sum(1, 100) - sum_of_squares(1, 100).


% Problem #7
% Answer: 104743
% 
% By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, 
% we can see that the 6th prime is 13.
%
% What is the 10001st prime number?

divisible_by_any(_, []) -> false;
divisible_by_any(N, [Head|_]) when N rem Head == 0 -> true;
divisible_by_any(N, [_|Tail]) -> divisible_by_any(N, Tail).

next_prime(Primes, N) ->
    case divisible_by_any(N, Primes) of
        true -> next_prime(Primes, N + 1);
        _ -> N
    end.

next_prime([]) -> 2;
next_prime([Head|Tail]) -> next_prime([Head|Tail], Head + 1).

tail([_|Tail]) -> Tail.

nth_prime(N, Primes) when length(Primes) > N -> nth_prime(N, tail(Primes));
nth_prime(N, [Head|Tail]) when length([Head|Tail]) == N -> Head;
nth_prime(N, Primes) -> nth_prime(N, [next_prime(Primes)|Primes]).

nth_prime(N) -> nth_prime(N, []).

euler7() -> nth_prime(10001).