4 ms·
I'm pretty sure there was a project Euler problem premised on this property but I can't find it at the moment.
by scuppernong 10mo ago
I'm pretty sure there was a project Euler problem premised on this property but I can't find it at the moment.
- AnotherGoodName 10mo agoA classic would be quickly computing such big numbers under a modulus. You just compute the carmichael totient recursively till it hits 1, disregard higher orders and then going backwards calculate the powers, reducing by the modulo of the current order (this way it never gets large enough to be a pain to calculate). The totients reduce in logn time and each step is logn so it’s merely logn^2 to calculate.