Expand description
§Infinite Elves and Infinite Houses
The amount of presents that each house receives in part one 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.
It’s highly likely that the answer will be a
superabundant number but there’s no way
to easily prove that so we brute force check every possible solution. The approach is similar
to a reverse Sieve of Eratosthenes,
iterating first over each elf, then over each house adding the presents.
Somewhat unintuitively the ln(x) asymptotic complexity of this approach is much lower
than the n√n complexity of finding the factors of each number.
To speed things up we make one high level optimization and a few low tweaks.
The high level optimization is an observation from user warbaque on the
Day 20 solution thread
that Robin’s inequality
shows that the σ(n) function is lower than eᵞ * n * ln(ln(n)) for all n greater than 5040.
This means that we can determine a starting index close to the final result, skipping over a
huge chunk of numbers.
The low level tweaks reduce the amount of work that needs to be done.
We break the search range into fixed size blocks from start to end,
for example 200000 to 299999 with a block size of 100000. Then we can make some observations:
- Elf 1 visits each house once.
- Elves from
starttoendeach visit a different house exactly once, bringing start, start + 1, … presents. - Elves from
end / 2tostartskip over all the houses. - Elves from
block sizetoend / 2visit at most one house as the increment is greater than the size of the block. - Elves from
2toblock sizemay visit any number of times.
Constants§
- BLOCK 🔒
Functions§
Type Aliases§
- Input 🔒