Problem 14: Find the longest sequence
The problem is:
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.
I just brute forced it. I did take a guess that the number would be in the 500k to 1m range. It takes about 40 seconds. It runs in about 16 seconds if I use only odd numbers between 500001 and 1m. Is there a better way?
Anyway, the code:
%%
% Problem 14 (a bit slow (40 seconds ish) maybe I could add a cache??)
% Note1: optimised after reading the forum to only use the odd numbers
%%
prob14() ->
L = lists:seq(500001, 1000000, 2),
max(lists:map(fun(X) -> {X, length(get_next([X]))} end, L), {0, 0}).
max([], Max) -> Max;
max([{_X, Len}=H|T], {_MaxX, MaxLen}=Max) ->
case Len > MaxLen of
true ->
max(T, H);
false ->
max(T, Max)
end.
get_next([H|T]=L) when H rem 2 =:= 0 ->
get_next([H div 2|L]);
get_next([H|T]=L) when H =:= 1 ->
L;
get_next([H|T]=L) ->
get_next([(3 * H) + 1|L]).
Some people on the forum are getting there results in ~1-5 seconds which is a whole load faster than mine. Some are doing that by using a cache and others by using what appears to be faster implementations. I guess my Erlang solution is slow because I don't know the right way to write Erlang.
I also think (for learning purposes) I'll try and do a multi-process version of this solution since it decomposes well into that idiom.
Problem 13: Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
This is not a tough problem for lisp or erlang. Some bright spark in the forum simply states that he cut and paste the list and wrapped it with (+ ) and had the result. I think the size of the numbers presents problems for some languages and the optimization is to only sum the first eleven digits of the long numbers since we only need the first 10 digits of the result.
I am lazy so I went the cut and paste option...
prob13() ->
BigNumbers = [ELIDED],
lists:sublist(integer_to_list(lists:sum(BigNumbers)), 1, 10).
So sum the list and then take the first 10 digits of the result. If you want to see the list of numbers they are here.
Problem 20: Sum of the digits in 100!
This is so similar to problem 16. The problem is:
n! means n (n 1) ... 3 2 1
Find the sum of the digits in the number 100!
Which is cool 'cos I have learned what n! means. My code is:
prob20(N) -> L = lists:seq(N, 1, -1), NBang = lists:foldl(fun(X, Acc) -> Acc * X end, 1, L), sum_the_digits(NBang). sum_the_digits(N) -> L = integer_to_list(N), lists:foldl(fun(X, Acc) -> Acc + list_to_integer([X]) end, 0, L).
I reuse the sum_the_digits function from problem 16. These recent problems have caused me nothing like the trouble of the first 10. Either I am over some initial erlang/fp/maths hump or they admins have the difficulty order wrong.
Oh yeah. I find that I am using lists:foldl all the time.
Problem 16: Sum of digits
I realised that you can sort the Project Euler problems by difficulty. So I did. Which is why the order gets a bit odd from now onwards. I have no time to do Euler problems so I am cherry picking what I can fit into the spare 5 and 10 minute slots I have. So...problem 16:
15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?
Not a lot to say really so just the code.
prob16(N, Exp) -> sum_the_digits(round(math:pow(N, Exp))). sum_the_digits(N) -> L = integer_to_list(N), lists:foldl(fun(X, Acc) -> Acc + list_to_integer([X]) end, 0, L).
The second function (integer_to_list) turns a number into a list of its digits and then folds the list to sum the digits. Can't just use lists:sum as each list element is now a "String" so needs to be turned back into an integer with list_to_integer([X]). This reeks of hack so if anyone knows a better way please let me know.
Problem 10: Sum of the Primes
I haven't posted for a while. I'm contracting for a VoD producing company pathologically averse to normal quality measures which has taken all (ALL) my time.
Anyway, the problem:
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.Find the sum of all the primes below two million.
Since I already have a functional prime checker from problem 3 so the code is just:
prob10_alt(N) -> Primes = [A || A <- lists:seq(3, N, 2), is_prime2(A)], lists:sum([2|Primes]).
I know this isn't the Sieve of Eratosthenes but I had a crack at a sieve implmentation and it was pitifully slow compared to the above. I know it is not optimal but it is adequate. I did learn about The Sieve due to this problem so it was of benefit. I have also read and implemented a Java version of The Sieve (it really suits iteration) so education has occurred.
In case anyone reads this and can help me with my Sieve versions here it is:
prob10_sieve2(N) ->
Limit = floor(math:sqrt(N)),
Cans = array:new(N, {default, true}),
Cans2 = seive_it(4, N, 2, Cans),
Primes = seive2(Cans2, Limit),
array:foldl(fun(X, Val, Acc) -> arr_fold_fun(X, Val, Acc) end, 0, Primes) - 1.
arr_fold_fun(X, Val, Acc) ->
case Val of
true ->
X + Acc;
false ->
Acc
end.
seive2(Array, Limit) ->
for(3, Limit, 2, Array).
for(Start, Limit, _Step, Array) when Start >= Limit -> Array;
for(Start, Limit, Step, Array) ->
case array:get(Start, Array) of
true ->
for(Start+Step, Limit, Step,
seive_it(Start*Start, array:size(Array), 2*Start, Array));
false ->
for(Start+Step, Limit, Step, Array)
end.
seive_it(Start, Limit, _Step, Array) when Start >= Limit -> Array;
seive_it(Start, Limit, Step, Array) ->
seive_it(Start+Step, Limit, Step, array:set(Start, false, Array)).