Project Euler - first 100 problems
Last updated: Mar 20, 2025.
My solutions to the problems from Project Euler.
Problem 1
Difficulty: 5%
Find the sum of all multiples of 3 or 5 below 1000.
(->> (range 1000)
(filter #(or (zero? (mod % 3)) (zero? (mod % 5))))
(reduce +))233168
Problem 2
Difficulty: 5%
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
(loop [f1 1,
f2 2,
even-sum 0]
(if (>= f2 4000000)
even-sum
(if (zero? (mod f2 2))
(recur f2 (+ f1 f2) (+ even-sum f2))
(recur f2 (+ f1 f2) even-sum))))4613732
Problem 3
Difficulty: 5%
Find the largest prime factor of 600851475143.
We’ll just brute force all primes below \(\sqrt{N}\) and try them as divisors.
(let [N 600851475143]
(->> (primes/sieve-of-eratosthenes (int (Math/sqrt N)))
reverse
(filter #(zero? (mod N %)))
first))6857
Problem 4
Difficulty: 5%
Find the largest palindrome made from the product of two 3-digit numbers.
We write a function to check if an integer is a palindrome.
(defn is-palindrome? [x]
(let [xstr (Integer/toString x)]
(= (map char xstr) (reverse xstr))))Run through all \(a \times b\) where \(a, b \in [100, 999]\).
(->> (for [a (range 100 1000)
b (range 100 1000)
:when (is-palindrome? (* a b))]
(* a b))
sort
last)906609
Problem 5
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
I was happy to solve this with just pen and paper. Let \(N\) be the answer we seek. It has to be divisible by every prime and composite number \(\le 20\). But since the composite numbers upto \(20\) are themselves just products of primes smaller than themselves, we can write
\[ N = 2^a \cdot 3^b \cdot 5^c \cdot 7^d \cdot 11^e \cdot 13^f \cdot 17^g \cdot 19^h \]
For each prime above, the exponent has to be the highest exponent of that prime that appears in the factorization of any of the numbers \(1..20\). For example, \(a = 4\) because \(16 = 2^4\) and for \(N\) to be divisible by \(16\) it must have \(2^4\) as a factor. Similarly for \(N\) to be divisible by \(18\) and \(9\) it must have \(3^2\) as a factor. By doing this for all the primes we get the answer:
(* (* 2 2 2 2) (* 3 3) 5 7 11 13 17 19) 232792560
Problem 6
Difficulty: 5%
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
(- (int (Math/pow (->> (range 1 101)
(reduce +))
2))
(->> (range 1 101)
(map #(int (Math/pow % 2)))
(reduce +)))25164150
Problem 7
Difficulty: 5%
What is the 10,001st prime number?
As a consequence of the Prime Number Theorem (wiki), the \(N\)th prime is approximately
\[N \ ln(N)\]
So we’ll generate all primes upto a little more than that number and pick out the 10,001st one.
(let [N 10001
approx-nth-prime (* N (Math/log N))]
(nth (primes/sieve-of-eratosthenes
(int (* 1.2 approx-nth-prime)))
(dec N)))104743
Problem 8
Difficulty: 5%
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
We slide a 13-digit window across the 1000-digit number, compute each product and pick the maximum.
(def INPUT-8 (filter #(not= % \newline)
(slurp "src/code/data/euler-8-input.txt")))
(->> (for [i (range 0 (- (count INPUT-8) 13))]
(reduce * 1 (map #(Character/digit % 10)
(take 13 (drop i INPUT-8)))))
sort
last)23514624000
Problem 9
Difficulty: 5%
Find the one Pythagorean triplet for which \(a + b + c = 1000\).
We first write a function to check if a triplet is Pythagorean (\(a^2 + b^2 = c^2\)).
(defn is-pythagorean? [v]
(let [[a b c] (sort v)]
(= (* c c)
(+ (* a a) (* b b)))))(->> (for [c (range 1 1000)
:let [aplusb (- 1000 c)]]
(for [a (range 1 aplusb)
:let [b (- aplusb a)]
:when (and (distinct? a b c)
(is-pythagorean? (vector a b c)))]
(sort [a b c])))
(mapcat identity)
distinct
first
(reduce * 1))31875000
The triplet is (200 375 425).
Problem 10
Difficulty: 5%
Find the sum of all the primes below two million.
(reduce + 0 (primes/sieve-of-eratosthenes 2000000)) 142913828922
Problem 11
Difficulty: 5%
In the 20x20 grid of numbers, find the largest product of four adjacent numbers. Adjacent is defined as up, down, left, right, and four diagonals.
There is probably a much cleaner way of writing this, but this is the brute force solution. First we read the grid into a 2d array.
import java.io.File
val GRID_SIZE = 20
fun parseGrid(path: String): Array<Array<Int>> {
val grid: Array<Array<Int>> = Array<Array<Int>>(GRID_SIZE,
{ _ -> Array<Int>(GRID_SIZE, { _ -> 0 }) })
val text = File(path).readText()
val lines = text.lines()
for ((i, line) in lines.withIndex()) {
val nums = line.split(" ")
for ((j, n) in nums.withIndex()) {
grid[i][j] = n.toInt()
}
}
return grid
}Then we just compute all possible sums and pick the maximum.
// For each "anchor" position (i, j) compute the max product among the
// 8 possible adjacent quartets (four cardinal directions and four diagonals)
fun maxProductForAnchor(i: Int, j: Int, grid: Array<Array<Int>>): Int {
val get = { i: Int, j: Int ->
if (i in 0..GRID_SIZE-1 && j in 0..GRID_SIZE-1) {
grid[i][j]
} else {
0
}
}
val left = get(i, j) * get(i, j-1) * get(i, j-2) * get(i, j-3)
val right = get(i, j) * get(i, j+1) * get(i, j+2) * get(i, j+3)
val up = get(i, j) * get(i-1, j) * get(i-2, j) * get(i-3, j)
val down = get(i, j) * get(i+1, j) * get(i+2, j) * get(i+3, j)
// north-west diagonal
val northWest = get(i, j) * get(i-1, j-1) * get(i-2, j-2) * get(i-3, j-3)
// north-east diagonal
val northEast = get(i, j) * get(i-1, j+1) * get(i-2, j+2) * get(i-3, j+3)
// south-west diagonal
val southWest = get(i, j) * get(i+1, j-1) * get(i+2, j-2) * get(i+3, j-3)
// south-east diagonal
val southEast = get(i, j) * get(i+1, j+1) * get(i+2, j+2) * get(i+3, j+3)
return arrayOf(
left, right, up, down,
northWest, northEast, southWest, southEast
).max()
}
fun main() {
val grid = parseGrid("src/euler-11.txt")
var allMax = 0
for (i in 0..GRID_SIZE-1) {
for (j in 0..GRID_SIZE-1) {
val m = maxProductForAnchor(i, j, grid)
if (m > allMax) { allMax = m }
}
}
println(allMax)
}70600674
Problem 12
Every time I try Rust I’m delighted by how fast my code runs. For once it feels like I’m actually taking advantage of the insane Apple M4 chip. I’ve tried to learn Rust a few times in the past, but maybe doing the rest of the problems in this set is how I’ll finally get it.
I did the brute force solution here because the smarter solutions I read about (quadratic sieve) seemed too complicated for the first 100 problems.
use std::collections::HashSet;
fn count_divisors(n: usize) -> usize {
let mut divisors: HashSet<usize> = HashSet::new();
divisors.extend([1, n]);
for d in 2..((n as f32).sqrt() as usize) + 1 {
if n % d == 0 {
divisors.insert(d);
divisors.insert(n / d);
}
}
divisors.len()
}
fn main() {
let mut sum = 1;
let mut i = 1;
loop {
if count_divisors(sum) > 500 {
println!("{}", sum);
break;
}
i += 1;
sum += i;
}
}76576500
Problem 13
Difficulty: 5%
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
I absolutely love Clojure’s thread-last macro because it makes certain transformations of sequences perfectly concise and natural. Compare the English description and the code in the solution to this problem. In English,
- Read the file with the input numbers.
- Split the file into lines.
- Convert each line (
String) into a number (BigInteger). - Sum all the numbers.
- Convert the sum back to a string.
- Take the first 10 characters of the string.
- Convert the sequence of 10 characters into a single string.
In code:
(->> (slurp "src/code/data/euler-13.txt")
str/split-lines
(map #(BigInteger. %))
(reduce + 0)
.toString
(take 10)
(apply str))“5537376230”
Problem 14
Difficulty: 5%
The Collatz sequence is defined as: \(n_{i+1} = n_i / 2\) (when \(n_i\) is even) and \(n_{i+1} = 3n_i + 1\) (when \(n\) is odd). Assuming that every starting value eventually converges to 1, which starting value under one million produces the longest sequence?
(defn collatz-length
"Return the length of the Collatz sequence starting at x"
[x]
(loop [n 1
xi x]
(cond
(= xi 1) [x n]
(= (mod xi 2) 0) (recur (inc n) (quot xi 2))
:else (recur (inc n) (+ (* 3 xi) 1)))))
(->> (range 2 1000000)
(map collatz-length)
(apply max-key second))[837799 525]
Problem 15
Difficulty: 5%
function fac(n: bigint): bigint {
let result = 1n;
for (let i: bigint = n; i > 1n; i--) {
result *= i;
}
return result;
}
const choose = (n: bigint, k: bigint): bigint =>
fac(n) / (fac(k) * fac(n - k));
function problem15() {
console.log(choose(40n, 20n));
}137846528820
Problem 16
Difficulty: 5%
Find the sum of the digits of \(2^{1000}\).
(->> (.toString (.pow (BigInteger/valueOf 2) 1000))
(map #(Character/digit % 10))
(reduce + 0))1366
Problem 17
Difficulty: 5%
Write out each number 1-1000 (inclusive) as words. For example \(342\) = “three hundred and forty-two”. Count the total number of letters, excluding spaces and hyphens.
We define all the words needed for this problem.
(def DIGITS
{
1 "one"
2 "two"
3 "three"
4 "four"
5 "five"
6 "six"
7 "seven"
8 "eight"
9 "nine"
}
)
(def TEENS
{
11 "eleven"
12 "twelve"
13 "thirteen"
14 "fourteen"
15 "fifteen"
16 "sixteen"
17 "seventeen"
18 "eighteen"
19 "nineteen"
})
(def TENS
{
10 "ten"
20 "twenty"
30 "thirty"
40 "forty"
50 "fifty"
60 "sixty"
70 "seventy"
80 "eighty"
90 "ninety"
})Next we define two functions to count the number of letters needed to express the hundreds place value and the tens place value parts of a number.
(defn hundreds-count [h]
(if (zero? h) 0
(+ (count (DIGITS h)) (count "hundred"))))
(defn tens-count [t]
(cond
(zero? t) 0 ;; when t is 0
(< t 10) (count (DIGITS t)) ;; single digit numbers
(<= 11 t 19) (count (TEENS t)) ;; teen numbers
:else (+ (count (TENS (* 10 (quot t 10)))) ;; numbers 20-99
(if (zero? (mod t 10))
0
(count (DIGITS (mod t 10)))))))When counting the letters for a number, we need to handle the special case of whether “and” needs to be included. For example, \(342\) = “three hundred and forty-two” but \(100\) = “one hundred”.
(defn number-in-words-count [x]
(let [h (quot x 100)
t (mod x 100)
and-count (if (and (> h 0) (not (zero? t))) (count "and") 0)]
(+ (hundreds-count h) (tens-count t) and-count)))The last special case to handle is the number \(1000\).
(+ (->> (range 1 1000)
(map number-in-words-count)
(reduce + 0))
(count "onethousand"))21124
Problem 19
Difficulty: 5%
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
First we need the definition of a leap year:
(defn is-leap-year? [y]
(let [four (zero? (mod y 4))
hundred (zero? (mod y 100))
four-hundred (zero? (mod y 400))]
(or (and four (not hundred))
(and four hundred four-hundred))))(map is-leap-year? [1900 1996 2000]) (false true true)
Then we need the number of days in any month of any year:
(defn days-in-month [m y]
(case m
1 31
2 (if (is-leap-year? y) 29 28)
3 31
4 30
5 31
6 30
7 31
8 31
9 30
10 31
11 30
12 31))Idiomatic Clojure style is to write immutable code. But I find this problem easier to solve by imagining adding up the days for each month starting from 1901.
(let [day (atom 2) ;; Jan 1 1901 was a Tuesday
result (atom 0)]
(doseq [year (range 1901 2001)
month (range 1 13)]
(reset! day (mod (+ @day (days-in-month month year)) 7))
(when (zero? @day)
(println year month)
(swap! result inc)))
@result)171
Problem 20
Difficulty: 5%
Find the sum of the digits in \(100!\).
For a change I did this in Kotlin.
import java.math.BigInteger
fun fac(n: BigInteger): BigInteger {
var f: BigInteger = BigInteger.ONE
var i: BigInteger = n
while (i > BigInteger.ONE) {
f *= i
i -= BigInteger.ONE
}
return f
}It’s almost as concise as Clojure.
fun main() {
println(fac(BigInteger.valueOf(100))
.toString()
.toCharArray()
.fold(0) { result, c -> result + c.digitToInt() }
)
}648
Problem 21
Difficulty: 5%
Let \(d(n)\) be the sum of all proper divisors of \(n\) (numbers less than \(n\) that divide \(n\)). If \(d(b) = a\) and \(d(a) = b\) while \(a \ne b\), then both \(a\) and \(b\) are called amicable numbers. Find the sum of all amicable numbers under 10000.
We sum the proper divisors of a number by brute force.
(defn sum-proper-divisors
"Returns the sum of all divisors of n, excluding n itself"
[n]
(->> (range 1 (inc (Math/ceil (/ n 2))))
(filter #(= (mod n %) 0))
(reduce + 0)))Define an amicable number.
(defn amicable? [a]
(let [b (sum-proper-divisors a)]
(and (not= a b)
(= (sum-proper-divisors b) a))))Check each number under 10000.
(->> (range 2 10001)
(filter amicable?)
(reduce + 0))31626
Problem 22
Difficulty: 5%
Let the word-score of a name be the sum of its letters expressed as numbers (A = 1, B = 2, …). So for example
COLIN = 53. Sort the list of names in the input file, compute the word score for each name, multiply the position of each name in the sorted list by its score and sum everything.
(defn word-score [w]
(reduce + 0 (map #(- (int (Character/toUpperCase %)) 64) w)))(word-score “COLIN”) 53
The key useful function here is map-indexed that turns a sequence into (index, value) pairs and applies a function to each such pair.
(let [sorted-names (->> (str/split
(slurp "src/code/data/euler_0022_names.txt")
#",")
(map #(str/replace % #"\"" ""))
sort)]
(reduce + 0 (map-indexed
#(* (inc %1) (word-score %2))
sorted-names)))871198282
Problem 23
A number is abundant if the sum of its proper divisors is greater than the number. By analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
As much as I love Lisp and functional programming, there are times when writing loops is just easier. I solved this problem in Kotlin and I’m starting to really like it.
// Computes the sum of the proper divisors (= excluding 1 and itself) of n
fun sumProperDivisors(n: Int): Int {
var sum = 0
for (d in 2..ceil(n.toDouble()/2).toInt()) {
if (n % d == 0) { sum += d }
}
return sum
}
fun isAbundant(n: Int): Boolean {
return when {
n < 4 -> false
else -> sumProperDivisors(n) > n
}
}
// Computes the set of abundant numbers <= n
fun abundantNumbers(n :Int): BitSet {
val result = BitSet(n)
for (m in 1..n) {
if (isAbundant(m)) { result.set(m) }
}
return result
}Once we have the set of all abundant numbers under the analytical limit, we loop through all possible pairs and figure out the positive integers that are expressible as their sum.
val ANALYTICAL_LIMIT = 28123
val ABUNDANT = abundantNumbers(ANALYTICAL_LIMIT + 1)
fun abundantSums(): BitSet {
val result = BitSet(ANALYTICAL_LIMIT + 1)
for (a in ABUNDANT.stream()) {
for (b in ABUNDANT.stream()) {
if (a + b <= ANALYTICAL_LIMIT) {
result.set(a+b)
}
}
}
return result
}
fun main() {
val expressible = abundantSums()
var sum = 0
for (n in 1..ANALYTICAL_LIMIT) {
if (!expressible.get(n)) {
sum += n
}
}
println(sum)
}4179871
Problem 25
Difficulty: 5%
Find \(n\) such that the \(n\)th Fibonacci number is the first one in the sequence to have 1000 digits.
A lot of these problems are meant to test your ability to deal with arbitrarily large integers, I think. They are easy to do when you have that capability in the standard library (BigInteger).
import java.math.BigInteger
class Fibonacci() {
var i = 1
private var f1 = BigInteger.ONE
private var f2 = BigInteger.ONE
fun next(): BigInteger {
return when (i) {
1, 2 -> {
i += 1
BigInteger.ONE
}
else -> {
val fi = f1 + f2
i += 1
f1 = f2
f2 = fi
fi
}
}
}
}By writing this as an iterator class we make sure that we compute each Fibonacci number only once.
fun main() {
val fib = Fibonacci()
while (true) {
val f = fib.next()
if (f.toString().length == 1000) {
println("${fib.i-1}: $f")
break
}
}
}4782
Problem 29
Difficulty: 5%
With \(2 \leq a \leq 100\) and \(2 \leq b \leq 100\), how many distinct values of \(a^b\) are there?
import java.math.BigInteger
fun main() {
val distinctPowers: HashSet<BigInteger> = HashSet(99*99)
for (a in 2..100) {
for (b in 2..100) {
distinctPowers.add(a.toBigInteger().pow(b))
}
}
println(distinctPowers.size)
}9183
Problem 32
use std::{collections::HashSet};
fn is_pandigital(a: usize, b: usize, prod: usize) -> bool {
const DIGITS: [char; 9] = ['1', '2', '3', '4', '5', '6', '7', '8', '9'];
let mut digits: Vec<char> = Vec::new();
digits.extend(a.to_string().chars());
digits.extend(b.to_string().chars());
digits.extend(prod.to_string().chars());
digits.len() == 9 && DIGITS.iter().all(|&d| digits.contains(&d))
}
pub fn solution() -> usize {
let mut pandigitals: HashSet<usize> = HashSet::new();
for a in 1..2000 {
for b in 1..2000 {
if is_pandigital(a, b, a*b) {
pandigitals.insert(a*b);
}
}
}
pandigitals.iter().fold(0, |acc, x| acc+x)
}45228
Problem 46
export function isGoldbachExpressible(
n: number, primes: Array<number>
): boolean {
const isEven = (x: number) => x % 2 === 0;
const isSquare = (x: number) => Math.sqrt(x) === Math.floor(Math.sqrt(x));
for (let p of primes) {
const rest = n - p;
if (isEven(rest) && isSquare(rest/2)) {
return true;
}
if (p > n) break;
}
return false;
}
function problem46() {
let n = 3;
const LIMIT = 100000;
const primes = sieveOfEratosthenes(LIMIT);
while (n < LIMIT) {
if (!isGoldbachExpressible(n, primes)) {
console.log(n);
break;
}
n += 2;
}
}5777
Problem 47
export function sieveOfEratosthenes(N: number): Array<number> {
let sieve = new BitSet();
sieve.setRange(2, N);
for (let x = 2; x <= Math.floor(Math.sqrt(N)); x++) {
for (let i = 2; i <= Math.ceil(N/x); i++) {
sieve.clear(x * i);
}
}
let primes = [];
for (let i = 2; i <= N; i++) {
if (sieve.get(i)) primes.push(i);
}
return primes
}
export function primeDivisors(
n: number, primes: Array<number>
): Array<number> {
let divisors = [];
for (let p of primes) {
if (n % p === 0) divisors.push(p);
if (p > n) break;
}
return divisors;
}
// Problem 47
// Given that p divides n, find the max p^k that divides n
export function maxPrimePower(n: number, p: number): number {
let k = 2;
while (n % Math.pow(p, k) === 0) {
k++;
}
return Math.pow(p, k-1);
}
export function primePowerFactors(
n: number, primes: Array<number>
): Array<number> {
return primeDivisors(n, primes).map((d, _) => maxPrimePower(n, d));
}
// Returns true if all the factors of a sequence of numbers are
// all distinct
export function allDistinct(
seqFactors: Array<Array<number>>
): boolean {
const allFactors = seqFactors.flat();
const factorSet = new Set<number>(allFactors);
return allFactors.length === factorSet.size;
}
export function problem47() {
console.time('problem47');
let low = 10;
const primes = sieveOfEratosthenes(1000000);
let seq = [
primePowerFactors(10, primes),
primePowerFactors(11, primes),
primePowerFactors(12, primes),
primePowerFactors(13, primes),
];
const allAtleastFour = (seq: Array<Array<number>>) => seq.flat().length >= 16;
while (!(allDistinct(seq) && allAtleastFour(seq))) {
seq.shift();
seq.push(primePowerFactors(low + 4, primes));
low++;
}
console.timeEnd('problem47');
console.log(`${low}: ${seq[0]} ${low+1}: ${seq[1]} ${low+2}: ${seq[2]} ${low+3}: ${seq[3]}`);
}(134043: 3,7,13,491) (134044: 4,23,31,47) (134045: 5,17,19,83) (134046: 2,9,11,677)
Problem 48
Find the last ten digits of the series, \(1^1 + 2^2 + 3^3 + ... + 1000^{1000}\).
import java.math.BigInteger
fun main() {
var result = BigInteger.ZERO;
var i = BigInteger.ONE;
while (i <= BigInteger.valueOf(1000)) {
result += i.pow(i.toInt())
i += BigInteger.ONE
}
val digits = result.toString()
println(digits.substring(digits.length - 10, digits.length))
}9110846700
Problem 52
Find the smallest positive integer \(x\) such that \(x\), \(2x\), \(3x\), \(4x\), \(5x\), and \(6x\) all contain the same digits.
import BitSet from "bitset";
export function digitSet(n: number): BitSet {
const bs = new BitSet("0000000000");
const DIGITS: Record<string, number> = {
"0": 0,
"1": 1,
"2": 2,
"3": 3,
"4": 4,
"5": 5,
"6": 6,
"7": 7,
"8": 8,
"9": 9,
};
for (const c of n.toString()) {
bs.set(DIGITS[c]);
}
return bs;
}
export function allEqual(sets: Array<BitSet>): boolean {
const first = sets[0];
for (let i = 1; i < sets.length; i++) {
if (!first.equals(sets[i])) {
return false;
}
}
return true;
}
export function tryNumber(n: number): boolean {
const sets: Array<BitSet> =
[1, 2, 3, 4, 5, 6].map((x) => digitSet(n * x));
return allEqual(sets);
}
function problem52() {
console.time("problem52");
for (let n = 1; n < 1000000; n++) {
if (tryNumber(n)) {
const vals = [1, 2, 3, 4, 5, 6].map((x) => n * x);
console.log(`${vals.join(" ")}`);
}
}
console.timeEnd("problem52");
}
problem52();142857
Problem 59
function gibberishScore(text: number[]): number {
let gibberishCount = 0;
const isReadable = (c: number) => (
c >= 'a'.charCodeAt(0) && c <= 'z'.charCodeAt(0)
);
for (const c of text) {
if (!isReadable(c)) gibberishCount++;
}
return gibberishCount / text.length;
}
async function loadInput(filePath: string): Promise<number[]> {
try {
const data = await readFile(filePath, 'utf-8');
return data.split(",").map((code: string, _) => parseInt(code));
} catch (error) {
console.error('Error reading file:', error);
throw error;
}
}
function decrypt(cipher: number[], key: number[]): number[] {
if (cipher.length % key.length != 0) {
throw Error("cipher must be multiple of key length");
}
const keyLength = key.length;
return cipher.map((c, i) => c ^ key[i % keyLength]);
}
function allKeys(): number[][] {
let result = [];
const a = "a".charCodeAt(0);
const z = "z".charCodeAt(0);
for (let i = a; i <= z; i++) {
for (let j = a; j <= z; j++) {
for (let k = a; k <= z; k++) {
result.push([i, j, k]);
}
}
}
return result;
}
async function problem59() {
const cipher = await loadInput("src/code/data/euler-59.txt");
let bestGuess: {
key: number[],
plain: number[],
score: number
} = {
key: [],
plain: [],
score: 1
};
for (let k of allKeys()) {
const plain = decrypt(cipher, k);
const score = gibberishScore(plain);
if (score < bestGuess.score) {
bestGuess.key = k;
bestGuess.plain = plain;
bestGuess.score = score;
}
}
console.log(bestGuess.plain.reduce((total, x) => total + x, 0));
}129448
Problem 65
Difficulty: 15%
\(e\) can be written as the continued fraction \([2; 1, 2, 1, 1, 4, 1, 1, 6, 1, ... , 1, 2k, 1, ...]\)
The \(n\)th “convergent” of a continued fraction is the result of summing it upto \(n\) terms. Find the sum of the digits in the numerator of the 100th convergent of the fraction for \(e\).
First we write a generic function to sum the first \(n\) terms of a continued fraction.
(defn sum-terms
[xs]
(if (empty? xs)
0
(/ 1 (+ (first xs) (sum-terms (rest xs))))))We can test that it works by computing \(\sqrt{2}\) upto 10 terms.
(float (+ 1 (sum-terms (repeat 9 2)))) 1.4142137
The fraction for \(e\) is slightly more complicated because the \(k\)th term can be either \(2k\) or \(1\).
(defn e-terms
"The first n terms of the continued fraction for e"
[n]
(take n (map (fn [k]
(case (mod k 3)
0 1
1 (* 2 (inc (quot k 3)))
2 1))
(range n))))Now sum the first 100 terms and compute the sum of the digits of the numerator.
(reduce + (map #(Character/digit % 10)
(str (numerator (+ 2 (sum-terms (e-terms 99)))))))272
Helpers
These are helper functions used across problems.
Since many of the problems deal with prime numbers, let’s write the Sieve of Eratosthenes to generate all prime numbers below \(n\).
(defn sieve-of-eratosthenes
[n]
(let [sieve (BitSet. (inc n))]
;; Set all bits to true initially
(.set sieve 0 (inc n))
;; 0 and 1 are not prime
(.clear sieve 0)
(.clear sieve 1)
(doseq [x (range 2 (inc (int (Math/sqrt n))))]
(doseq [i (range 2 (inc (quot n x)))]
(.clear sieve (* x i))))
(filter #(.get sieve %) (range 2 n))))