Post #1098422

@Taneb@hacksrus.xyz the idea is to use modular arithmetic: pick a small n, find the sum of all 10 digits mod n, and calculate the residue of 2^29 mod n by reducing the intermediate values as you go rather than reducing once at the end. The normal choice is to work mod 9. The sum of all ten digits is 0, because they come in pairs summing to 9. And 2^3 = 8 ≡ −1, so 2^6 ≡ 1, so 2^(any multiple of 6) ≡ 1 as well. Then 2^29 = 2^24 × 2^3 × 2^2 ≡ 1 × −1 × 4 = −4. If the number had all ten digits once each then its residue mod 9 would be 0, but in fact it's −4, so 4 must be missing. (With a bit more theory you can go straight to 2^6 ≡ 1 (mod 9) via the Fermat-Euler theorem, but I think this question is set before getting to that part of the course.) I've never thought of it before, but you could surely work mod 11 almost as easily, which eliminates the risk that the missing digit is one of the two that you can't tell apart mod 9!