Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Octocat-spinner-32-eaf2f5

Cannot retrieve contributors at this time

file 68 lines (56 sloc) 1.646 kb
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
%% Problem
%% ---------------------
%% The sequence of triangle numbers is generated by adding the natural numbers.
%% So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.
%% The first ten terms would be:
%%
%% 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
%%
%% Let us list the factors of the first seven triangle numbers:
%%
%% 1: 1
%% 3: 1,3
%% 6: 1,2,3,6
%% 10: 1,2,5,10
%% 15: 1,3,5,15
%% 21: 1,3,7,21
%% 28: 1,2,4,7,14,28
%%
%% We can see that 28 is the first triangle number to have over five divisors.
%%
%% What is the value of the first triangle number to have over five hundred divisors?
%% ---------------------

-module(p012).
-export([solve1/0, solve2/0]).
-include_lib("eunit/include/eunit.hrl").

%%
%% Brute force solution
%%
solve2() -> triangular(7, 0).

triangular(N, Result) when Result > 500 -> N*(N-1) div 2;
triangular(N, _) -> triangular(N+1, factors(N*(N+1) div 2)).

%%
%% Returns number of divisors of integer N
%%
factors(N) -> factors(N, trunc(math:sqrt(N))).

factors(N, L) when L*L == N -> factors(N, L+1) - 1;
factors(N, L) -> 2 * length([ X || X <- lists:seq(1,L), N rem X =:= 0 ]).

%%
%% Faster solution uses the fact that
%% D(t) = D(n/2)D(n+1) (n is even) or D(t) = D(n)*D((n+1)/2) (n is odd)
%% Also reusing D(n) from previous iteration
%%
solve1() -> tri(2, 1, 1).

tri(N, _, Result) when Result > 500 -> N*(N-1) div 2;
tri(N, D, _) ->
    M = case N rem 2 == 0 of
        true -> N+1;
        false -> (N+1) div 2
    end,
    D1 = factors(M),
    tri(N+1, D1, D*D1).


% Tests

factors_25_test() ->
    ?assertEqual(3, factors(25)).

factors_28_test() ->
    ?assertEqual(6, factors(28)).
Something went wrong with that request. Please try again.