Problem 5

Problem

\(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 divisibledivisible with no remainder by all of the numbers from \(1\) to \(20\)?

Julia (using lcm)

p5() = lcm(1:20...);
p5()

232792560

using BenchmarkTools;
@benchmark p5()

BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  1.132 ns … 3.647 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     1.142 ns             ┊ GC (median):    0.00%
 Time  (mean ± σ):   1.140 ns ± 0.038 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%
  ▁                                                  █       
  █▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▄ ▂
  1.13 ns        Histogram: frequency by time       1.14 ns <
 Memory estimate: 0 bytes, allocs estimate: 0.

Julia

include("euler.jl")

function prime_decomposition(n::Integer)
    possible_primes = Euler.sieve_of_eratosthenes(n)
    temp_n = n
    dec = Int32[]

    while temp_n > 1
        for p ∈ possible_primes
            q, r = divrem(temp_n, p)            
            if iszero(r)
                temp_n = temp_n ÷ p
                push!(dec, p)
                break
            end
        end
    end
    return dec
end;

function p5()
    decomposition = map(prime_decomposition, 2:20)
    distinct_primes = vcat(decomposition...) |> unique

    count_matrix = 
    map(distinct_primes) do p
        map(decomposition) do d
            count(==(p), d)
        end
    end |> stack

    primes_powers = map(maximum, eachcol(count_matrix))

    n = (distinct_primes .^ primes_powers) |> prod

    return n
end;

p5()

232792560

using BenchmarkTools;
@benchmark p5()

BenchmarkTools.Trial: 10000 samples with 6 evaluations.
 Range (min … max):  5.078 μs … 701.066 μs  ┊ GC (min … max):  0.00% … 97.51%
 Time  (median):     5.646 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   6.691 μs ±  22.319 μs  ┊ GC (mean ± σ):  13.51% ±  4.02%
         ▃▆▇█▇▃▂                                               
  ▁▁▁▂▃▅█████████▇▆▄▄▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  5.08 μs         Histogram: frequency by time        7.99 μs <
 Memory estimate: 12.66 KiB, allocs estimate: 142.