Project Euler 6: Sum square difference

Problem 6 är ett problem som får en mycket vacker lösning med funktionell kod.

The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + … + 10^2 = 385The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)^2 = 55^2 = 3025Hence 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.

Det finns en ganska självklar väg till att lösa detta problem. Räkna ut de båda summorna och subtrahera.

-module(problem_6).
-export([problem_6/0]).

problem_6() ->
    Start = os:timestamp(),
    SumOfSquares = [X*X || X <- lists:seq(1, 100)],
    Sum = lists:sum(lists:seq(1, 100)),
    Res = (Sum*Sum) - lists:sum(SumOfSquares),
io:format("Resultatet är ~poch det tog ~p sekunder att beräkna~n", [Res, timer:now_diff(os:timestamp(), Start)/1000000]).

Koden finns även på github.

Project Euler 5: Smallest multiple

Problem 5 är det enda problemet i project Euler som jag vill ta bort eftersom antalet beräkningar som krävs för att lösa problemet är så pass få att det går snabbare att lösa problemet för hand än att skriva ett program som löser problemet.

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

Vi vet att talet måste vara delbart med 1 och 2, dvs  1 och 2 är faktorer.

3 är också en faktor så då blir faktorerna: 1,2,3.

4 är två 2:or så vi behöver en till 2:a: 1,2,2,3.

5 är också en faktor så då blir faktorerna: 1,2,2,3,5.

6 är 2*3 och vi har redan 2 och 3.

7 är också en faktor så då blir faktorerna: 1,2,2,3,5,7.

8 är tre 2:or så vi behöver en till 2:a: 1,2,2,2,3,5,7.

9 är två 3:or så vi behöver en till 3:a: 1,2,2,2,3,3,5,7.

10 är 2*5 och vi har redan 2 och 5.

11 är också en faktor så då blir faktorerna: 1,2,2,2,3,3,5,7,11.

12 är 2*2*3 och vi har redan 2, 2 och 3.

13 är också en faktor så då blir faktorerna: 1,2,2,2,3,3,5,7,11,13.

14 är 2*7 och vi har redan 2 och 7.

15 är 3*5 och vi har redan 3 och 5.

16 är fyra 2:or så vi behöver en till 2:a: 1,2,2,2,2,3,3,5,7,11,13.

17 är också en faktor så då blir faktorerna: 1,2,2,2,2,3,3,5,7,11,13,17.

18 är 2*3*3 och vi har redan 2,3 och 3.

19 är också en faktor så då blir faktorerna: 1,2,2,2,2,3,3,5,7,11,13,17,19.

20 är 2*2*5 och vi har redan 2,2 och 5.

Faktorerna för detta tal är alltså 1,,2,2,2,2,3,3,5,7,11,13,17,19 Multiplicerar vi ihop detta får vi = svaret.

MVH;

André Le Blanc

 

 

 

Project Euler 3: Largest prime factor

Problemen 3 är det första problemet med primtal.

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

Den grundläggande algoritmen för detta problem är enkel, dela talet med så många primtal som möjligt och se vilka som går in jämt. Att lösa detta problem på ett effektivt sätt handlar om att inte gissa onödiga tal. Eftersom talet inte är delbart med två så behöver vi endast gissa udda tal

problem_3(Num div Fac, Fac);
problem_3(Num, Fac) -> problem_3(Num, Fac+2).

problem_3() ->
Start = os:timestamp(),
Res = problem_3(600851475143, 3),
io:format("Resultatet är ~poch det tog ~p sekunder att beräkna~n", [Res, timer:now_diff(os:timestamp(), Start)/1000000]).

Resultatet tog 4.7e-5 sekunder att beräkna. Koden finns här.

Project Euler problem 4: Largest palindrome product

Detta inlägg kommer bli mycket kort eftersom lösningen är mycket kort. Problem 4 är ett problem där funktionell programmering verkligen möjliggör enkla lösningar.

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.

Den enkla lösningen på detta problem är att generera en lista med alla tre-siffriga tal och kolla vilka kombinationer som ger palindromer. Välj därefter ut den största palindromen.

-module(problem_4).
-export([problem_4/0]).

problem_4() ->
Start = os:timestamp(),
Listan = lists:seq(100,999),
Pallar = [X*Y || X <- Listan, Y <- Listan, integer_to_list(X*Y) == lists:reverse(integer_to_list(X * Y))],
Res = lists:max(Pallar),
io:format("Resultatet: ~p och tog ~p sekunder att beräkna", [Res, timer:now_diff(os:timestamp(), Start) / 1000000]).

Koden hittar ni här. Lösningen tog 342 ms att beräkna. Dock finns det lätta optimeringar att göra. Detta program kollar alla lösningar två gånger. Tex kollas både X = 300, Y = 400 och X = 400, Y = 300. Lägger vi till lite kod så kollar vi färre tal och får ner tiden till 178 ms.

problem_4_snabbare() ->
    Start = os:timestamp(),
    Res = lists:max(pall(999)),
    io:format("Resultatet: ~p och tog ~p sekunder att beräkna", [Res, timer:now_diff(os:timestamp(), Start) / 1000000]).

pall(99) -> [];
pall(N) ->
    Listan = lists:seq(100,N),
    Pallar = [X*N || X <- Listan, integer_to_list(X*N) == lists:reverse(integer_to_list(X*N))],
Pallar ++ pall(N-1).

Project Euler 14: Longest Collatz sequence

Dags för den första roliga inlägget eftersom vi får använda flera processer. Halva poängen med Erlang är att man kan köra flera lättviktsprocesser samtidigt. Har man en dator med flera kärnor kan man alltså låta datorn jobba på flera olika uppgifter samtidigt. I problem 14 så kan vi börja leka med parallellisering.

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Vi kan börja med en helt sekventiell variant där vi gör en lista av alla längder av collatz-sekvensen för talen inom intervallet där vi vill hitta det längsta. Sen tar vi indexet av det största värdet i den listan och så har vi svaret.

collatzFast(1, Acc) -> Acc;
collatzFast(N, Acc) when N rem 2 == 0 ->
    collatzFast(N div 2, Acc+1);
collatzFast(N, Acc) ->
    collatzFast(3*N+1, Acc+1).<span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>

collatzSeq(Lo, Hi) ->
    Start = os:timestamp(),
    Res = collatzSeqRec(Lo, Hi),
    io:format("Svaret är ~p och tog ~f sekunder att beräkna~n", [Res, timer:now_diff(os:timestamp(), Start) / 1000000]).

collatzSeqRec(Lo, Hi) ->
    X = [collatzFast(X, 1) || X <- lists:seq(Lo, Hi)],     Lo + maxZ(X, 0, 0, 0). 

Denna lösning tog 5.254460 sekunder att beräkna. Vi kan nu parallellisera denna lösning igenom att ha två processer som gör halva uppgiften var. Vi skapar två processer, den ena processen hanterar den första halvan av talen och den andra den andra halvan av talen. Då har varje process endast hälften så många tal att hantera. När processerna har kört klart så kan man se vilken process som hittade det största talet. Teoretiskt sätt borde denna lösning vara dubbelt så snabb. I verkligheten så tar det en hel del resurser att skapa två trådar.

 collatzFast(1, Acc) -> Acc;
collatzFast(N, Acc) when N rem 2 == 0 ->
    collatzFast(N div 2, Acc+1);
collatzFast(N, Acc) ->
    collatzFast(3*N+1, Acc+1).

collatzRange(Lo, Hi) ->
    X = [collatzFast(X, 1) || X <- lists:seq(Lo, Hi)],     Res = Lo + maxZ(X, 0, 0, 0),     master ! Res,     exit(normal). maxZ([], _, _, IndexOfMax) ->
    IndexOfMax;
maxZ([H|T], Index, Max, _) when H > Max ->
    maxZ(T, Index+1, H, Index);
maxZ([_|T], Index, Max, IndexOfMax) ->
    maxZ(T, Index+1, Max, IndexOfMax).

collatzProc(Lo, Hi) ->
    Start = os:timestamp(),
    register(master, self()),
    spawn(fun () ->
          collatzRange(Lo, Hi div 2)
    end),
    spawn(fun () ->
         collatzRange(Hi div 2, Hi)
    end),
    io:format("Svaret är ~p och tog ~f sekunder att beräkna~n", [reciever(0, 0), timer:now_diff(os:timestamp(), Start) / 1000000]).

reciever(Antal, 2) -> Antal;

reciever(Antal, Count) ->
    receive
        Num when
            Num > Antal ->
                reciever(Num, Count + 1);
            Num when Num < Antal -> reciever(Antal, Count + 1)
    end.

Det tog 2.818826 sekunder att beräkna resultatet. Det är nästan hälften av vad det första programmet tog. Det är ungefär vad man förväntade sig. Att det tog ett par millisekunder att skapa två processer och skicka meddelanden mellan dem visar Erlangs sanna styrka.

Koden hittar ni på min githubsida

Mvh;

André Le Blanc

Project Euler problem 2

Dags för den första uppgiten som det finns mer att skriva om. Problem 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, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

 

 

Detta problem skiljer sig från de flesta problem med Fibonacci-sekvensen eftersom man från början inte vet hur långt man ska beräkna. Dock kan man dra fördel av det använda en snabb algoritm för att beräkna fibonacci-sekvensen. Istället för fib(N) -> fib(N-1) + fib(N-2) så kan man beräkna fib(N, N-1) -> fib(N+ N-1, N). Skillnaden mellan att börja vid ett och räkna uppåt och att börja uppifrån och räkna ner kan verka liten men har stor betydelse för hur snabb algoritmen är. Att börja uppifrån och räkna neråt har en tidskomplexitet på O(2^n) medan nerifrån och upp har en tidskomplexitet på O(n).

-module(problem_2).
-export([problem_2/0]).

problem_2() ->
Start = os:timestamp(),
Resultat = even_euler(1, 1, 0),
io:format("Svaret är ~p och tog ~f sekunder att beräkna~n", [Resultat, timer:now_diff(os:timestamp(), Start) / 1000000]).

even_euler(N, N_minus_ett, Tot) when N < 4000000 ->
case N rem 2 of
0 -> even_euler(N + N_minus_ett, N, Tot + N);
1 -> even_euler(N + N_minus_ett, N, Tot)
end;

even_euler(_, _, Tot) -> Tot.

länk till github

Mvh;
André Le Blanc

Problem 1: multiplar av 3 och 5

Vi börjar med en mjukstart:

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.

Denna uppgift finns det inte mycket att säga om mer än att det är bara att generera talen och kolla vilka som uppfyller kraven.

-module(problem_1).
-export([fiveThree/0]).

fiveThree() ->
Start = os:timestamp(),
Y = [X || X <- lists:seq(1, 999), (X rem 3 =:= 0) or (X rem 5 =:= 0)],
Resultat = lists:sum(Y),
io:format("Svaret är ~p och tog ~f sekunder att beräkna~n", [Resultat, timer:now_diff(os:timestamp(), Start) / 1000000]).

Koden kan ni hitta på min githubsida

MVH;

André Le Blanc