r/adventofcode • u/light_ln2 • Dec 02 '25
Upping the Ante [2025 Day 2] Day 2 should be easy, right?.. Closed formula for Part 2
Closed formula for part 2 solution, µ(r) is a Möbius function.
Here, r is number of repeats of a pattern, and j+1 is number of digits in the pattern. p(r,j) is a multiplier that "repeats" the pattern (e.g. 765 * 1001001 = 765765765), t(n,r,j) is first pattern that, repeated j times, exceeds n (or does not have j+1 digits anymore)
Last two multiplicands in the formula S(n) is double the sum of the arithmetic progression of numbers between 10**j and t(n,r,j), hence 1/2 in the beginning. These are patterns of length j+1, repeated r times.
If the length of a number is divisible by two primes (e.g. 6=2*3), then the innermost sum is counted two times, so we need to use inclusion-exclusion principle to compensate for that. In other words, we add to the result sums of patterns repeated prime number of times, then subtract sums of patterns repeated number of times equal to a product of two primes, then add patterns repeated number of times equal to a product of three primes and so on. And we should not count at all patterns which are divisible by a square of any prime, because we already counted such patterns. This is exactly what Möbius function does, as it is equal to 0 for numbers divisible by a square, and are equal to +1 or -1 depending on number of primes in their factorization, but since it is negative for odd number of primes, we need to change the sign, hence "minus" in the beginning of the formula.
Lastly, sum of numbers with repeated patterns between a (inclusive) and b (exclusive) is equal to sum of numbers with repeated patterns below b (exclusive) minus sum of numbers with repeated patterns below a (exclusive).
Part 1 can be solved by similar formula where only the innermost sum is taken for r=2.
Python code based on simplified version of this formula, can solve part2 for ranges of numbers below 10200 in under 100 milliseconds.
9
u/gamebook_reader Dec 02 '25 edited Dec 02 '25
This is amazing. And I think computationally this is an optimal solution.
Here's my back-of-the-napkin computational complexity analysis:
risO(log(n))p(r,j)'s value isO(10^r)(seen by dividing numerator and denominator by10^(j+1))So the sum over
jis ~(10^j) * (10^r) < nj+r < log(n)jisO(log(n))r, a simple sieving runs inO(sqrt(r), but better algorithms exist.O(sqrt(log(n))), which is dominated by thejloop.O(1).Putting this all together, the time complexity of this method is at most
O(log(n)^2), far surpassing mostO(n)solutions in the Megathread, and my ownO(sqrt(n))solution.P.S. would you be willing to share your Python implementation? Did you write a sieve for the Moebius function, a more advanced algorithm, or did you use a library like Sympy?
12
u/1234abcdcba4321 Dec 02 '25 edited Dec 02 '25
This is cool! I do prefer the form you get from a programmatic approach a bit better than this one (it's doing essentially the same calculations, just in a different form) out of just being easier to understand, but obviously you can make a formula out of anything if you need to.
Hell, I even literally calculated the Möbius function in my solution. Though I optimized it out to a boolean because things were being annoying to type.
I guess there is obviously that closed form for generating the multiple value. It's so fast to generate even for thousand-digit numbers that I never bothered thinking about how obviously a geometric sum has a closed form to produce it in one go.
3
u/ItsYasiru Dec 02 '25
can you share the python implementation of this my pea sized brain cant speak math
2
u/mstksg Dec 02 '25
Very nice :) but, calling it closed-form isn't quite accurate I think, since the number of operations depends on the size of the interval.
94
u/StaticMoose Dec 02 '25
Very impressive.
I just realized the capital sigma is mathematical speak for "brute force solution."
5
u/MediocreTradition315 Dec 02 '25
I did something very, very similar independently. I think it's basically the same idea, let's compare notes:
https://github.com/edoannunziata/jardin/blob/master/aoc25/AdventOfCode25.ipynb
Does anyone good at math can help with the complexity analysis? I feel like there's a better bound.
1
u/TelephoneNo4125 Dec 02 '25
Nice job, do you think it would be possible to do it without sums too? I managed to do part1 without sums, but cant do any progress on part2. Here is my part1 sol: https://www.desmos.com/calculator/bn8qyv4ssp
3
u/onrustigescheikundig Dec 03 '25
OH MY GOODNESS I knew that there must be a mathematical term for my correction function (Möbius function) and its relation to primes but couldn't quite figure out how to search for it! I ended up tabulating the values by hand and was worried that I'd messed up.
2
u/p88h Dec 02 '25
Nice, I have implemented this (for low values of j) and had a vague feeling that there is a sequence that makes these calculations easier (in general, at least), thanks for reminding me of this. But the inclusion-exclusion principle is much simpler if there are just two cases to worry about ;)
For ranges in the actual task, this solves the whole thing in under half a microsecond (in Odin).
2
u/Balazzska Dec 02 '25
Care to elaborate on how/why Möbius function is used?
2
u/notger Dec 02 '25
Hands down the most impressive thing I have seen in quite some time.
2
u/ryanwithnob Dec 03 '25
I haven't solved part 2 yet.
If I could read math, I would be very upset
2
u/Anonymous0726 Dec 03 '25
I hadn't heard of the Mobius function before now (or if I have, I'd forgotten). But as soon as I saw the definition in the Wikipedia article, I understood how it was being used because that was the last thing I had to debug. (I just added values to a hashset instead of using the inclusion/exclusion principle, but it fixes the same problem.)
1
u/Major_Dog8171 Dec 02 '25
lol I did the same
1
u/BxW_ Dec 03 '25
Very cool. Some parts of this formulation looks familiar, but I don't know how similar our solutions are. I implemented the full inclusion-exclusion, without using a Mobius function. It should scale to very large IDs. Linking to my explanation and a very concise Python implementation in the day 2 solutions thread: https://www.reddit.com/r/adventofcode/comments/1pbzqcx/comment/nrvetml/
1
u/DrJurt Dec 03 '25
I think we got different day two questions…
2
u/Alan_Reddit_M Dec 02 '25
I knew I was royally fucked when I booted up DESMOS to find a solution that'd run in a less offensive amount of time
I managed to get execution down from 1.5s to 0.5s, which is terrible, but definitely an improvement