Expand description
§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
highly abundant 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
It is easy enough to pre-generate a list of highly-abundant numbers, or
even just grab one from OEIS A002093.
Inspecting that list shows that between house numbers 540_540 and 1_201_200,
there are only 28 candidates. In turn, it is easy to precompute their
sum of divisors, turning this into a LUT (lookup table) on the target,
sufficient to cover the range of all known puzzle inputs (30-40 million).
§Part Two
As with part one, an offline brute force search showed that for all house numbers between
540_540 and 1_201_200, there are only 46 record-holders; just use another LUT.
Structs§
- Mapping 🔒