using Iterators, Primes, Combinatorics, Distributions, DataStructures, StatsBase, Digits
# Combines an array of integers into one integer.
function combine_list(l::Array{Int,1})
s, p = 0, 0
for (i, n) in enumerate(reverse(l))
s += n * 10^p
p += ndigits(n)
end
s
end
# Selects the first element from a list for which a condition is true
function ifirst(cond, itr)
for elem in itr
cond(elem) && return elem
end
end
# More functions for Digits
isanagram(a, b) = sort(digits(a)) == sort(digits(b))
ispandigital(l, n=9) = sort(digits(l)) == [1:n;]
# Finds the most common elements in a counter object
most_common(ct) = sort(collect(ct.map), by=p->p[2], rev=true)
most_common(ct, n) = Base.select(collect(ct.map), 1:n, by=p->p[2], rev=true)
# An iterator of prime numbers
primeiter(n=2) = filter(isprime, countfrom(big(n)))
# Returns the integer value of a hypotenuse
ihypot(a,b) = isqrt(a^2 + b^2);
# Returns square numbers up to hi (inclusive)
function square_numbers(hi)
l = []
for n in countfrom()
sq = n^2
if sq <= hi
push!(l, sq)
else
break
end
end
l
end
# Returns all non-square numbers up to hi (inclusive)
non_squares(hi) = setdiff(1:hi, square_numbers(hi))
triangular(n) = div(n * (n + 1), 2)
pentagonal(n) = div(3*n^2 - n, 2)
hexagonal(n) = div(2*n*(2*n -1), 2)
function divisors(n)
n == 0 && return []
l = [1]
for (p,e) in factor(n)
l = reduce(vcat, l, [l * p^j for j in 1:e])
end
l
end
proper_divisors(n) = divisors(n)[1:end-1];
L = 999
@time sum(union(0:3:L, 0:5:L))
0.087482 seconds (36.03 k allocations: 1.515 MB)
L = 4*10^6
function p2()
l = []
for n in countfrom()
push!(l, fibonaccinum(n))[end] > L && break
end
sum(filter(iseven, l))
end
@time p2()
0.108539 seconds (30.94 k allocations: 1.356 MB)
@time maximum(keys(factor(600851475143)))
0.000030 seconds (20 allocations: 1.219 KB)
@time maximum(filter(ispalindrome, map(prod, combinations(100:999, 2))))
0.415372 seconds (2.95 M allocations: 180.946 MB, 6.26% gc time)
@time lcm(1:20)
0.053492 seconds (17.82 k allocations: 820.314 KB)
@time sum(1:100)^2 - sum(square_numbers(100))
0.019625 seconds (4.37 k allocations: 202.390 KB)
@time nth(primeiter(), 10001)
0.129407 seconds (358.19 k allocations: 8.060 MB, 5.68% gc time)
n = [parse(Int, c) for c in readstring("p/p008_number.txt")]
@time maximum(i -> prod(n[i:i+12]), 1:length(n)-12)
0.067704 seconds (25.30 k allocations: 1.179 MB)
@time first(a*b*ihypot(a,b) for (a,b) in combinations(1:500, 2) if a + b + hypot(a,b) == 1000)
0.128624 seconds (658.47 k allocations: 35.793 MB, 3.37% gc time)
Calculate the sum of all the primes below two million.
L = 2*10^6
@time sum(primes(L))
0.093572 seconds (3.46 k allocations: 2.692 MB)
What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?
a = readdlm("p/p011_grid.txt", Int)
function p11()
n = size(a, 1)
line_value(start, direction) = prod(k -> a[start[1] + direction[1]*k, start[2] + direction[2]*k], 0:3)
directions = filter(d -> d != (0,0), product(-1:1, -1:1))
maximum(line_value(start, direction) for start in product(4:n-4, 4:n-4), direction in directions)
end
@time p11()
0.696232 seconds (341.82 k allocations: 14.091 MB, 1.41% gc time)
What is the value of the first triangle number to have over five hundred divisors?
@time ifirst(n -> length(divisors(n)) > 500, imap(triangular, countfrom()))
0.494830 seconds (1.10 M allocations: 62.531 MB, 1.86% gc time)
Find the first ten digits of the sum of one-hundred 50-digit numbers.
a = readdlm("p/p013_numbers.txt", BigInt)
@time Digits.select(sum(a), 1:10)
0.102453 seconds (36.08 k allocations: 1.535 MB)
Which starting number, under one million, produces the longest collatz chain?
L = 10^6
function collatz(n)
n == 1 && return 1
return iseven(n) ? collatz(div(n,2)) + 1 : collatz(3*n + 1) + 1
end
@time indmax(map(collatz, 1:L))
0.987422 seconds (31.25 k allocations: 8.982 MB, 0.61% gc time)
Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?
Analysis: To get to the corner, you need to go down exactly 20 times in a total of 40 moves, with each step being a choice between two options. This is given by the binomial distribution.
@time binomial(40, 20)
0.000015 seconds (5 allocations: 176 bytes)
What is the sum of the digits of the number 2^1000?
@time sum(digits(big(2)^1000))
0.015957 seconds (2.73 k allocations: 87.234 KB)
How many letters would be needed to write all the numbers in words from 1 to 1000?
function english(n)
ones = ["one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven",
"twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]
tens = ["ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"]
n == 1000 && return "onethousand"
n >= 100 && return ones[fld(n, 100)] * "hundred" * (n % 100 > 0 ? "and" : "") * english(n % 100)
n >= 20 && return tens[fld(n, 10)] * english(n % 10)
n > 0 && return ones[n]
return ""
end
@time length(prod(english, 1:1000))
0.123722 seconds (58.32 k allocations: 31.420 MB, 4.22% gc time)
Find the maximum sum traveling from the top of the triangle to the base.
Analysis: Start at the bottom and go up. Assign each tile the value of itself plus the largest of the two tiles that can lead to it. This will be the maximum sum leading to that tile.
a = readdlm("p/p018_triangle.txt")
function triangle_sum(a)
for row in reverse(1:size(a, 2)-1), col in 1:row
a[row, col] += max(a[row+1, col], a[row+1, col+1])
end
a[1, 1]
end
@time triangle_sum(a)
0.028874 seconds (7.97 k allocations: 348.880 KB)
How many Sundays fell on the first of the month during the twentieth century?
@time count(date -> Dates.day(date) == 1 && Dates.dayofweek(date) == 7, Date(1901, 1, 1):Date(2000, 12, 31))
0.094457 seconds (50.17 k allocations: 2.133 MB)
Find the sum of digits in 100!
@time sum(digits(factorial(big(100))))
0.061847 seconds (22.51 k allocations: 943.126 KB)
Evaluate the sum of all the amicable numbers under 10000.
L = 10^4
function amicable(a)
b = sum(proper_divisors(a))
return a != b && sum(proper_divisors(b)) == a
end
@time sum(filter(amicable, 2:L))
0.877834 seconds (1.87 M allocations: 95.861 MB, 3.95% gc time)
What is the total of all the name scores in the file of first names?
a = readdlm("p/p022_names.txt", ',', String)
@time sum(sum(char -> findfirst('A':'Z', char), name) * i for (i, name) in enumerate(sort(vec(a))))
0.104837 seconds (47.44 k allocations: 1.996 MB)
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
L = 28123
function p23()
s, abundants = 0, Set()
for n in 1:L
sum(proper_divisors(n)) > n && push!(abundants, n)
if !any(a -> n - a in abundants, abundants); s += n; end
end
s
end
@time p23()
1.825126 seconds (13.80 M allocations: 268.302 MB, 4.67% gc time)
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
@time combine_list(nthperm(collect(0:9), 10^6))
0.088130 seconds (11.15 k allocations: 497.436 KB)
What is the first term in the Fibonacci sequence to contain 1000 digits?
L = 1000
@time ifirst(n -> log10(fibonaccinum(n)) + 1 >= L, countfrom(1))
0.302039 seconds (117.02 k allocations: 5.519 MB)
Find the value of d < 1000 for which 1/d contains the longest recurring cycle.
Analysis: https://en.wikipedia.org/wiki/Repeating_decimal#Fractions_with_prime_denominators. The length of the repetend (period of the repeating decimal) of 1/p is equal to the order of 10 modulo p.
L = 999
function cycle_length(d)
for k in 1:big(d)
10^k % d == 1 && return k
end
0
end
@time indmax(map(cycle_length, 1:L))
1.419154 seconds (10.14 M allocations: 303.302 MB, 14.50% gc time)
Find a quadratic formula with terms below 1000 that produces the maximum number of primes for consecutive values of n.
L = 999
consecutive_primes_of_quadratic(a, b) = ifirst(n -> !isprime(n^2 + a*n + b), countfrom())
@time maximum((consecutive_primes_of_quadratic(a, b), a*b) for a in -L:L, b in primes(L))[2]
0.271666 seconds (789.91 k allocations: 18.744 MB, 3.81% gc time)
What is the sum of both diagonals in a 1001 by 1001 spiral?
L = 1001
function p28()
l, diagonal = [1], 1
for sidelength in 3:2:L, corner in 1:4
diagonal += sidelength - 1
push!(l, diagonal)
end
sum(l)
end
@time p28()
0.016608 seconds (7.07 k allocations: 249.779 KB)
How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
L = 100
@time length(unique(a^b for a in 2:big(L), b in 2:L))
0.256971 seconds (448.86 k allocations: 13.967 MB, 3.47% gc time)
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.
Analysis: The highest sum of fifth powers of digits for a number with 7 digits is 9^5 * 7 = 413343, which has only 6 digits. So the number must have at most 6 digits.
hi = 10^6
@time sum(filter(n -> n == sum(d -> d^5, digits(n)), 2:hi))
0.350097 seconds (1.03 M allocations: 124.079 MB, 3.05% gc time)
How many different ways can 2 pounds be made using any number of coins?
Analysis: Dynamic programming. Approach described here: https://en.wikipedia.org/wiki/Change-making_problem
function find_ways(l)
ways = vcat([1], zeros(Int, l[end]))
for i in 1:length(l) -1, j in 1:length(ways) - l[i]
ways[l[i] + j] += ways[j]
end
ways[end]
end
@time find_ways([1,2,5,10,20,50,100, 200]) + 1
0.021557 seconds (4.75 k allocations: 213.026 KB)
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
Analysis: For a x b to be a 9-digit number, either a is 1-digit and b is 4-digit, or a is 2-digit and b is 3-digit. So a can be at most 2 digit and b at most 4 digit. (This could easily be optimized further.)
hi_a, hi_b = 100, 10000
@time sum(Set(a*b for a in 1:hi_a, b in 1:hi_b if ispandigital(combine_list([a,b, a*b]))))
1.697287 seconds (10.06 M allocations: 913.936 MB, 11.14% gc time)
Discover all the fractions with an curious cancelling method.
curious_cancelling(num, den) = digits(num)[1] == digits(den)[2] && digits(num)[2] / digits(den)[1] == num / den && num != den
@time Int(prod(den / num for num in 10:99, den in 10:99 if curious_cancelling(num, den)))
0.154890 seconds (58.61 k allocations: 3.355 MB)
Find the sum of all numbers which are equal to the sum of the factorial of their digits.
Analysis: 9! x 8 has only 7 digits, so an upper bound is 9! * 7.
hi = factorial(9)*7
@time sum(filter(n -> sum(map(factorial, digits(n))) == n, 3:hi))
1.170661 seconds (10.19 M allocations: 748.111 MB, 15.88% gc time)
How many circular primes are there below one million?
L = 10^6
is_circular(n) = all(isprime, combine(crop(n, i), crop(n, i - ndigits(n))) for i in 1:ndigits(n))
@time count(is_circular, primes(L))
0.174397 seconds (465.75 k allocations: 46.426 MB, 4.10% gc time)
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
L = 10^6
@time sum(filter(n -> ispalindrome(n) && bin(n) == reverse(bin(n)), 1:L))
0.302072 seconds (1.03 M allocations: 124.354 MB, 4.38% gc time)
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
function p37()
l = []
for n in primeiter(10)
all(isprime, crop(n, i) for i in -ndigits(n)+1:ndigits(n)-1) && push!(l, n)
length(l) == 11 && return(sum(l))
end
end
@time p37()
1.235966 seconds (8.69 M allocations: 238.342 MB, 11.81% gc time)
What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n)?
Analysis: Each increment of n adds at least as many digits as the number has. So n must be less than 10, and the number of digits in the base number multiplied by n must be at most 9. (This could easily be optimized further.)
@time maximum(filter(ispandigital, combine_list([a*j for j in 1:n]) for n in 2:10 for a in 1:10^(div(9, n))))
0.223927 seconds (181.81 k allocations: 12.655 MB, 5.99% gc time)
Find the perimeter <= 1000 for which there is the highest number of right-angled triangles with integer side lengths.
L = 1000
@time Int(mode(filter(p -> p == round(p) && p <= L, [a + b + hypot(a, b) for (a,b) in combinations(1:L/2, 2)])))
0.341787 seconds (807.61 k allocations: 44.938 MB, 2.94% gc time)
An irrational decimal fraction is created by concatenating the positive integers: If dn represents the nth digit, find the value of the following expression: d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000
@time prod(d -> parse(Int, join(1:10^6)[10^d]), 1:6)
1.475002 seconds (18.04 M allocations: 762.385 MB, 6.04% gc time)
What is the largest n-digit pandigital prime that exists?
Analysis: 9 and 8 digit pandigital numbers are divisible by 3 and thus cannot be prime. We find the largest prime by starting from the highest pandigital number and going down until we find a prime.
hi = 10^7
@time ifirst(n -> ispandigital(n, ndigits(n)), reverse(primes(hi)))
0.181940 seconds (881.82 k allocations: 102.983 MB, 9.96% gc time)
Find the number of triangle words in a list.
a = [strip(w) for w in readdlm("p/p042_words.txt", ',')]
@time count(word -> sum(char -> Int(char) - Int('A') + 1, word) in Set(map(triangular, 1:28)), a)
0.064393 seconds (78.98 k allocations: 7.379 MB)
Find the sum of all pandigital numbers with a sub-string divisibility property.
Analysis: Build the pandigital number recursively, adding one new digit at a time, so that the property is true with each addition.
function get_sum(l)
any(i -> (length(l) >= i && combine_list(l[end+1-i:end+3-i]) % primes(17)[10-i] != 0), 3:9) && return 0
length(l) == 9 && return sum(combine_list(l))
s = 0
for elem in collect(setdiff(Set(0:9), Set(l)))
s += get_sum(insert!(copy(l), 1, elem))
end
s
end
@time get_sum(Int[])
0.081455 seconds (60.74 k allocations: 3.676 MB)
Find the pair of pentagonal numbers for which their sum and difference are pentagonal and the difference is minimized.
Analysis: Go through the pentagonals in increasing order. For each pentagonal, look for a smaller pentagonal that satisfies the criteria, and save the one with minimized difference. Once the difference between successive pentagonals is larger than the minimum difference found, stop the search.
function p44()
hi = 10^7
pentas = map(pentagonal, 1:hi)
pentaset = Set(pentas)
mindiff = maximum(pentas)
for i in countfrom(1)
for j in reverse(1:i-1)
diff = pentas[i] - pentas[j]
diff > mindiff && break
if diff in pentaset && pentas[i] + pentas[j] in pentaset
mindiff = diff
end
end
pentas[i+1] - pentas[i] > mindiff && break
end
mindiff
end
@time p44()
3.716701 seconds (23.05 k allocations: 221.304 MB, 3.30% gc time)
Find the next triangle number that is also pentagonal and hexagonal.
hi = 10^5
@time first(intersect(
Set(map(triangular, 286:hi)),
Set(map(pentagonal, 166:hi)),
Set(map(hexagonal, 144:hi))))
0.131044 seconds (20.44 k allocations: 13.296 MB)
What is the smallest odd composite that is not a goldbach number (can be written as the sum of a prime and twice a square)?
function p46()
hi = 10^4
goldbachs = Set(prime + 2 * square for prime in primes(hi), square in square_numbers(hi))
ifirst(n -> !(isprime(n) || n in goldbachs), 3:2:hi)
end
@time p46()
1.868557 seconds (1.46 M allocations: 46.790 MB, 8.33% gc time)
Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?
@time ifirst(n -> all(i -> length(factor(n+i)) == 4, 0:3), countfrom())
0.630264 seconds (1.81 M allocations: 152.956 MB, 5.05% gc time)
Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000
@time sum(n -> n^n, 1:big(1000)) % 10^10
0.161696 seconds (144.25 k allocations: 6.613 MB, 2.69% gc time)
WARNING: could not attach metadata for @simd loop.
Find the members of a 4-digits sequence.
is_unusual_series(seq) = all(isanagram(seq[1], elem) for elem in seq) && seq[1] != 1487 && all(isprime, seq)
@time combine_list(ifirst(is_unusual_series, [[a, a + 3330, a + 6660] for a in 1000:3340]))
0.105660 seconds (91.61 k allocations: 6.129 MB)
Which prime, below one-million, can be written as the sum of the most consecutive primes?
function p50()
L = 10^6
prs, l = primes(L), []
for i in 1:length(prs)-1
prsum = prs[i]
for j in i+1:length(prs)
prsum += prs[j]
prsum > L && break
isprime(prsum) && push!(l, (j-i, prsum))
end
end
maximum(l)[2]
end
@time p50()
0.267989 seconds (281.31 k allocations: 8.348 MB)
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
Analysis: Start with 5-digit numbers, in increasing order, looking at all subsets. If none are found fulfilling the criteria, look at 6-digits numbers, etc.
function p51()
function replacements(prime, subset)
digits = 1 in subset ? collect(1:9) : collect(0:9)
[Digits.replace(prime, subset, fill(d, length(subset))) for d in digits]
end
family_size(prime, subset) = sum(isprime, replacements(prime, subset))
for n in countfrom(5), prime in primes(10^n, 10^(n+1)), subset in subsets(1:n)
if family_size(prime, subset) == 8 && prime in replacements(prime, subset)
return prime
end
end
end
@time p51()
0.876182 seconds (5.33 M allocations: 615.901 MB, 4.84% gc time)
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.
@time ifirst(n -> all(m -> sort(digits(n*m)) == sort(digits(n)), 2:6), countfrom(2))
0.151504 seconds (1.15 M allocations: 113.272 MB, 9.68% gc time)
How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?
L = 100
@time count(t -> binomial(reverse(big(t))...) > 10^6, combinations(1:L, 2))
0.091601 seconds (134.87 k allocations: 4.946 MB, 5.35% gc time)
How many poker hands does Player 1 win?
function rank_hand(hand)
vals = map(card -> searchindex("x23456789TJQKA", card[1]), hand)
suits = map(card -> card[2], hand)
flush = length(unique(suits)) == 1
straight = maximum(vals) - minimum(vals) == 4 && allunique(vals)
of_a_kind = map(t -> last(t), most_common(counter(vals)))
if straight && flush
order = "8_"
elseif 4 in of_a_kind
order = "7_"
elseif 3 in of_a_kind && 2 in of_a_kind
order = "6_"
elseif flush
order = "5_"
elseif straight
order = "4_"
elseif 3 in of_a_kind
order = "3_"
elseif count(n -> n==2, of_a_kind) == 2
order = "2_"
elseif 2 in of_a_kind
order = "1_"
else
order = "0_"
end
sorted_values = map(t -> first(t), sort(collect(counter(vals)), by=t->reverse(t), rev=true))
sorted_values_str = map(value -> lpad(string(value), 2, "0"), sorted_values)
return order * join(sorted_values_str, "_")
end
a = readdlm("p/p054_poker.txt", String)
@time sum(mapslices(l -> rank_hand(l[1:5]) > rank_hand(l[6:end]), a, 2))
1.796863 seconds (1.52 M allocations: 68.323 MB, 1.73% gc time)
How many Lychrel numbers are there below ten-thousand?
L = 9999
function is_lychrel(n)
n = big(n)
for _ in 1:50
n += reversedigits(n)
ispalindrome(n) && return false
end
true
end
@time count(is_lychrel, 1:L)
0.648186 seconds (6.67 M allocations: 187.056 MB, 22.30% gc time)
Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?
L = 99
@time maximum(sum(digits(a^big(b))) for a in 1:L, b in 1:L)
0.648536 seconds (7.02 M allocations: 193.326 MB, 19.34% gc time)
In the first one-thousand expansions of the square root of 2, how many fractions contain a numerator with more digits than denominator?
function p57()
n = 0
expander = big(2)
for _ in 1:1000
expander = 2 + 1 // expander
fraction = 1 + 1 // expander
if ndigits(num(fraction)) > ndigits(den(fraction))
n += 1
end
end
n
end
@time p57()
0.159370 seconds (207.33 k allocations: 7.543 MB, 9.99% gc time)
What is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?
function p58()
nprimes, diagonal = 0, 1
for sidelength in countfrom(3,2), corner in 1:4
diagonal += sidelength - 1
nprimes += isprime(diagonal)
if nprimes / (2 * sidelength - 1) < 0.1
return sidelength
end
end
end
@time p58()
0.055767 seconds (45.11 k allocations: 932.160 KB)
Find the key that decrypts a file.
Analysis: We check all possible keys, and identify the key that finds at least 7 common words.
text = readdlm("p/p059_cipher.txt", ',', Int)
function p59()
common_words = ["the", "and", "be", "of", "that", "have", "for", "it", "not", "on", "with", "you"]
many_common_words(text) = count(word -> Base.contains(text, word), common_words) > 6
convert(text, key) = [letter $ key[1 + (i - 1) % 3] for (i, letter) in enumerate(text)]
decrypt(text, key) = join(map(Char, convert(text, key)))
key = ifirst(key -> many_common_words(decrypt(text, key)), product(97:123, 97:123, 97:123))
sum(convert(text, key))
end
@time p59()
0.872329 seconds (654.20 k allocations: 73.307 MB, 2.00% gc time)
Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
Analysis: We add the primes recursively one at a time, so that all primes in the set concatenate with each other.
function p60()
hi = 10^4
pr = primes(hi)
@noinline all_concatenate(p_indices, i) =
all(j -> isprime(combine(pr[j], pr[i])) && isprime(combine(pr[i], pr[j])), p_indices)
function find_primeset(p_indices)
length(p_indices) == 5 && return p_indices
start = isempty(p_indices) ? 1 : p_indices[end] + 1
for i in start:length(pr)
if all_concatenate(p_indices, i)
result = find_primeset(push!(copy(p_indices), i))
result != nothing && return result
end
end
end
sum(pr[find_primeset([])])
end
@time p60()
0.971747 seconds (4.14 M allocations: 85.908 MB, 1.91% gc time)
ndigits(38)
Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.
Analysis: Build the sets recursively. Each new addition to the set must be cyclic with the previous number, and be of a new polygonal type.
function p61()
len, ndigit, hi_poly = 6, 4, 200
square(n) = n^2
heptagonal(n) = div(n * (5*n - 3), 2)
octogonal(n) = n * (3*n - 2)
vals = Dict()
for (nsides, polygon) in zip(3:8, [triangular, square, pentagonal, hexagonal, heptagonal, octogonal])
vals[nsides] = filter(n -> ndigit == ndigits(n), map(n -> polygon(n), 1:hi_poly))
end
arelinked(n1, n2) = digits(crop(n1, 2)) == digits(crop(n2, -2))
function fits(chain, value)
isempty(chain) && return true
! arelinked(chain[end], value) && return false
if length(chain) == len -1
return arelinked(value, chain[1])
else
return true
end
end
function get_chain(chain, polygons)
length(chain) == len && return chain
for polygon in setdiff(Set(3:8), polygons), val in vals[polygon]
if fits(chain, val)
new_chain = get_chain(push!(copy(chain), val), push!(copy(polygons), polygon))
new_chain != nothing && return new_chain
end
end
end
sum(get_chain([], Set()))
end
@time p61()
0.232055 seconds (529.59 k allocations: 36.667 MB, 3.46% gc time)
WARNING: Method definition p61() in module Main at In[14]:2 overwritten at In[15]:2.
Find the smallest cube for which exactly five permutations of its digits are cube.
Analysis: Look at all cubes with a specific number of digits, make a dictionary with keys as the digits, and values as all the cubes that contain exactly those digits. Find all the keys that contain exactly 5 cubes. If there are any, return the smallest of these cubes. If there aren't any, clear the dictionary, and look at all cubes with one more digit.
function p62()
cubes, nd = DefaultDict(Array{Int,1}), 1
for n in countfrom(1)
cube = n^3
if ndigits(cube) > nd
l = [v[1] for v in values(cubes) if length(v) == 5]
if !isempty(l)
return minimum(l)
else
cubes, nd = DefaultDict(Array{Int,1}), ndigits(cube)
end
end
push!(cubes[sort(digits(cube))], cube)
end
end
@time p62()
0.548282 seconds (520.43 k allocations: 24.302 MB, 1.05% gc time)
How many n-digit positive integers exist which are also an nth power?
Analysis: a cannot excede 10 since 10^n is n+1 digits long.
hi_a, hi_n = 10, 100
@time sum(ndigits(a^n) == n for a in 1:big(hi_a), n in 1:hi_n)
0.092655 seconds (58.58 k allocations: 1.986 MB)
How many continued fractions for N ≤ 10000 have an odd period?
Analysis: Algorithm from https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Algorithm
L = 10^4
function continued_fraction_period(n)
m, d = 0, 1
a0 = floor(sqrt(n))
a = [a0]
while 2 * a0 != a[end]
m = d * a[end] - m
d = (n - m^2) / d
push!(a, floor((a0 + m) / d))
end
return a
end
@time count(n -> iseven(length(continued_fraction_period(n))), non_squares(L))
0.143329 seconds (2.35 M allocations: 44.425 MB, 9.25% gc time)
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.
function p65()
cont_fraction(n) = n % 3 == 2 ? 2*n : 1
num, den = 2, big(1)
for n in 1:100
num, den = cont_fraction(n) * den + num, num
end
sum(digits(den))
end
@time p65()
0.037850 seconds (6.32 k allocations: 271.143 KB)
Solve diophantine equations.
Analysis: Method from https://en.wikipedia.org/wiki/Chakravala_method
function chakravala(N)
sq = BigInt(floor(sqrt(N)))
a, b, k, m = sq, 1, sq^2 - N, sq
while k != 1
m = div((m + sq), k) * k - m
a, b, k = div((a*m + N*b), abs(k)), div((a + b*m), abs(k)), div((m^2 - N), k)
end
a
end
@time maximum(map(i -> (chakravala(i), i), non_squares(1000)))[2]
0.150747 seconds (676.78 k allocations: 16.425 MB, 3.89% gc time)
Find the maximum sum traveling from the top of the triangle to the base.
Analysis: Reuse of code from problem 18.
a = readdlm("p/p067_triangle.txt")
@time triangle_sum(a)
0.000529 seconds (8.65 k allocations: 135.188 KB)
What is the maximum 16-digit string for a "magic" 5-gon ring?
Analysis: 10 has to be in the outer ring for the ring to have 16 digits. We first select the 5 numbers 1:9 that make up the inner ring. The outer numbers is determined from these.
function p98()
strings = []
for innerset in subsets(collect(1:9), 5)
outerset = setdiff(Set(1:10), Set(innerset))
groupsum = (2 * sum(innerset) + sum(outerset)) / 5
groupsum != round(groupsum) && continue
for inner in permutations(innerset)
outer = [Int(groupsum) - inner[i] - inner[i%5+1] for i in 1:5]
(Set(outer) != outerset || outer[1] != minimum(outer)) && continue
ring = [[outer[i], inner[i], inner[i%5+1]] for i in 1:5]
push!(strings, combine_list(vcat(ring...)))
end
end
maximum(strings)
end
@time p98()
0.455496 seconds (298.26 k allocations: 13.965 MB, 3.16% gc time)
Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
Analysis: n/φ(n) is lowest when n has the most prime factors compared to its size. This is the case when n is a primorial
primorial(ifirst(n -> primorial(n+1) > L, countfrom()))
Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum
Analysis: φ is lowest when its the product of exactly two primes. The algorithm searches through pairs of primes and saves the best pair product.
L = 10^7
function p70()
pr = primes(floor(Int, 1.2 * sqrt(L)))
min, min_n = 10, 0
for (p1, p2) in combinations(pr, 2)
n = p1 * p2
φ_n = (1 - p1) * (1 - p2)
if n / φ_n < min && n <= L && isanagram(n, φ_n)
min, min_n = n / φ_n, n
end
end
min_n
end
@time p70()
0.251114 seconds (1.72 M allocations: 107.609 MB, 9.51% gc time)
By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.
L = 10^6
@time num(maximum(filter(fr -> fr != 3//7, map(n -> fld(3*n, 7) // n, 1:L))))
0.654339 seconds (49.91 k allocations: 34.610 MB, 0.65% gc time)
How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?
Analysis: Go through the primes in order. For each prime, update all the values of d and discount the denominators for which the fraction could be reduced by that prime.
L = 10^6
function p72()
d = [i-1 for i in 1:L]
for n in 2:L
if d[n] == n - 1
for i in 2*n:n:L
d[i] -= div(d[i], n)
end
end
end
sum(d)
end
@time p72()
1.408494 seconds (23.94 M allocations: 432.392 MB, 5.63% gc time)
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?
L = 12000
@time sum(gcd(num, den) == 1 for den in 4:L for num in div(den, 3)+1:div(den, 2))
1.013527 seconds (54.37 k allocations: 2.154 MB)
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?
Analysis: For each starting number we find the chain, and add all the numbers in that chain to 'lengths' dictionary. This dictionary is used to find the lengths of future chains.
function p74()
lengths = Dict(169 => 3, 363601 => 3, 1454 => 3, 871 => 2, 45361 => 2, 872 => 2, 45362 => 2)
for start in 1:10^6
chain = [start]
while true
if chain[end] in keys(lengths)
for (i, elem) in enumerate(chain)
lengths[elem] = length(chain) - i + lengths[chain[end]]
end
break
end
push!(chain, sum(map(factorial, digits(chain[end]))))
if chain[end] == chain[end-1]
lengths[chain[end]] = length(chain) - 1
break
end
end
end
count(n -> n == 60, values(lengths))
end
@time p74()
1.054663 seconds (7.02 M allocations: 477.947 MB, 14.84% gc time)
Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?
Analysis: Formula from https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple
function p75()
L = 1.5 * 10^6
hi = floor(Int, sqrt(L))
perimeters = []
for n in 1:hi, m in n+1:2:hi
if gcd(m, n) == 1
for k in countfrom()
perimeter = k * (m^2 - n^2 + 2*m*n + m^2 + n^2)
perimeter > L && break
push!(perimeters, perimeter)
end
end
end
count(t -> t[2] == 1, counter(perimeters))
end
@time p75()
1.687752 seconds (11.55 M allocations: 233.776 MB, 25.94% gc time)
How many different ways can one hundred be written as a sum of at least two positive integers?
Analysis: Reuse of code from problem 31.
@time find_ways(collect(1:100))
0.000019 seconds (11 allocations: 2.953 KB)
What is the first value which can be written as the sum of primes in over five thousand different ways?
Analysis: Reuse of code from problem 31.
L = 5000
@time ifirst(n -> find_ways(primes(n)) > L, countfrom(2))
0.008558 seconds (2.16 k allocations: 167.065 KB)
Let p(n) represent the number of different ways in which n coins can be separated into piles. Find the least value of n for which p(n) is divisible by one million.
Analysis: Solution from
https://en.wikipedia.org/wiki/Partition_(number_theory):
p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ...
function p78()
pentagonals = filter(n -> n != 0, sort(map(pentagonal, -250:250)))
signs, p = [1,1,-1,-1], [1]
while p[end] != 0
p_n = 0
for i in countfrom()
pentagonals[i] > length(p) && break
p_n = (p_n + signs[(i-1)%4+1] * p[length(p) + 1 - pentagonals[i]]) % 10^6
end
push!(p, p_n)
end
length(p) - 1
end
@time p78()
0.503586 seconds (65.04 k allocations: 3.902 MB)
Analyse the file so as to determine the shortest possible secret passcode of unknown length.
Analysis: Sort the numbers in order of how many different numbers appear after it.
logins = readdlm("p/p079_keylog.txt", String)
function p79()
numbers_pressed_after = DefaultDict(Set)
for login in Set(logins)
push!(numbers_pressed_after[login[1]], login[2:3]...)
push!(numbers_pressed_after[login[2]], login[3])
push!(numbers_pressed_after[login[3]], "")
end
join(map(t -> t[2], sort([(length(v), k) for (k,v) in numbers_pressed_after], rev=true)))
end
@time p79()
0.722035 seconds (425.11 k allocations: 17.957 MB, 4.04% gc time)
"73162890"
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.
Analysis: This method is used to calculate square roots: http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf
function dsqrt(n, decs)
a, b = 5*n, big(5)
while length(digits(b)) < decs + 2
if a >= b
a -= b
b += 10
else
a *= 100
b = fld(b, 10) * 100 + 5
end
end
b
end
@time sum(n -> sum(digits(dsqrt(n, 100))[end-100:end]), non_squares(100))
2.047113 seconds (23.22 M allocations: 624.470 MB, 20.91% gc time)