Module day20

Infinite Elves and Infinite Houses

Part One

The amount of presents that each house receives is 10 times the divisor function σ. For example the divisors of 6 are 1, 2, 3 and 6, so house 6 receives 10 + 20 + 30 + 60 = 120 presents. The answer will be a superabundant number.

If n has the prime factorization n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ then the sum of divisors is σ(n) = [(p₁^(a₁+1) - 1)/(p₁ - 1)] × [(p₂^(a₂+1) - 1)/(p₂ - 1)] × ... × [(pₖ^(aₖ+1) - 1)/(pₖ - 1)] or more compactly σ(n) = ∏ᵢ₌₁ᵏ [(pᵢ^(aᵢ+1) - 1)/(pᵢ - 1)]

For example n = 12 = 2² × 3¹

• σ(12) = [(2³ - 1)/(2 - 1)] × [(3² - 1)/(3 - 1)]
• [(8 - 1)/1] × [(9 - 1)/2] = 7 × 4 = 28

Starting from 41 (the largest possible prime encountered in houses up to 50 billion presents) we recursively try smaller and smaller prime powers, finding the smallest house number that exceeds the target.

Part Two

We get a list of all possible house numbers that have divisor sums that exceed the value. Checking in ascending order, each house is broken down into its factors, including only those where the second elf will actually deliver.

Constants

PRIMES 🔒

Covers all possible scenarios up to 50 billion presents for part one. Checked by brute forcing all solutions that the highest prime factor is 41.

Functions

factor_sum 🔒

Combine prime factors into all factors, only counting those where the elf will still deliver.

parse

part1

part2