night! good luck to you too!
https://crypto.stanford.edu/pbc/notes/numbertheory/crt.html\|https://crypto.stanford.edu/pbc/notes/numbertheory/crt.html @notjack this looks like the algorithm; now to find a « modular-inverse » I can implement for SML :)
The algorithm i learned for modular-inverse was the extended euclidean algorithm, you might want to use that too.
Yeah, that’s what I’m finding, too.
@notjack how do you get your struct to print with a special format like you did with the congruence?
thank you!
Man, I held off on looking for solutions to part 2 for a long time. I’m kind of disappointed with this puzzle for “Advent of Code” - seems more appropriate for “Advent of Math” i.e. if you have some special knowledge it’s trivial; otherwise, pretty darn hard.
I even spent some time flipping through my “Concrete Mathematics” by Knuth et al, but didn’t have enough time to find the relevant bits.
Wow, the Julia implementation is impressive! function chineseremainder(n::Array, a::Array)
Π = prod(n)
mod(sum(ai * invmod(Π ÷ ni, ni) * (Π ÷ ni) for (ni, ai) in zip(n, a)), Π)
end
It was a frustrating puzzle and it was a real struggle for me, but I honestly am glad I got to learn a little number theory
Sure. I think the thing that frustrated me was that I kept assuming that there was probably something basic that I was missing. However, after looking through half a dozen algorithm text books and a few discrete math books, I wouldn’t say it was “basic” :) I think folks have either come across the info, or they haven’t, and that’s a significant divide. I’ll definitely dig into that Julia code later!
I had mathy friends who pointed me in the right direction. I definitely wouldn’t have been able to figure it out without that kind of community.
Thanks to @soegaard2 for (require math/number-theory) for Day 13 :)
The only reason i knew this was because we covered it in my mathematics class earlier this semester. For us it was used as part of the process in doing RSA cryptography