Now let's simplify things, since for the specific case of a = 1 we get some nice simplifications in Hensel's Lemma
Using this we can quickly find all the solutions to x^2 = 1 (mod p^e) which is step 1 at the begin of this page, then we can use any standard Chinese Remainder Theorem function and we can now calculate I(n) extremely quickly, however this is not good enough to solve the problem.
The last trick is to notice that again due to the Chinese remainder theorem, if we have solved for example I(100) = I(2^2 * 5^2) then we can solve I(300) = I(3 * 100) by using the Chinese remainder theorem since gcd(3, 100) = 1.
Knowing this we can quickly solve for larger n given that we have solved it for smaller n. In this case a smallest prime factor sieve is very useful to not repeatedly call a prime factorization function
Enter an Integer (yourinput)
Code will output ΣI(n) for 3 ≤ n ≤ yourinput