【雑記】3乗して下3桁が999になる自然数を求める問題

最近Twitterを見ていたら、「超難問コロシアム」とかいう数学の問題が広告で出てきてやがったので、ちょっと解いてみました。
ただ普通に解くだけじゃ面白くないので、せっかくだから僕が頭を使って自力で解くのと、プログラム書いて解くのとでどちらが早いかを比べてみました。

http://www.zkai.co.jp/z1/www.zkai.co.jp

解いた問題はこちら

自然数のうち、3乗すると下3桁が999になるものを1つ挙げよ。

問題の時点で結果が見えている気がしますが、とりあえずやってみます。

自力編

まず下3桁の話なので、1000の位より上はどうでも良い。
ということで自然数n=100a+10b+c　とする。

3乗して下1桁が9になるには、（c, n^2の下1桁）の組み合わせは(1,9),(3,3),(9,1)の3通りしかないが、cが1ならn^2の下1桁も必ず1になるので(1,9)はあり得ないし、cが3ならn^2の下1桁は9になるはずなのでこれもダメ。
ということでc=9で、ついでにいうとn^2の下1桁は1ということがわかる。

このc=9を当てはめて、n^2の10の位をかけ算の筆算っぽく求めてみると、9b+8+9b=18b+8 の下1桁が、n^2の10の位ということになる。
これを仮にb2と置くと、(b,b2)の組み合わせは(1,6),(2,4),(3,2),(4,0),(5,8),(6,6),(7,4),(8,2),(9,0),(0,8)の10通りのいずれかになる。

さらにb2を使ってn^3の10の位を筆算っぽく求めてみると、
9b2+b の下1桁が9　ということになり、上記の10通りの中からこの条件を満たすのは(b,b2)=(9,0)の時のみであることがわかる。
したがってb=9。

この辺でなんとなく答えは読めてきたけど、ちゃんと解く。
n=100a+99なので、n^3=(100a+99)^2 *(100a+99)
1000の位より上はどうでも良いので、それらを省きながら計算すると、9801(300a+99)。
これの100の位はと言うと、9801*99の百の位は2なので（これはがんばって計算した）、つまり3a+2の下1桁が9ということになる。
こんなaは9しかない。
したがって答えは999。回答にかかった時間は約15分。

プログラム編

public class Main {
	public static void main(String args[]) throws Exception {
		int n = 0;
		while (true) {
			n++;
			
			if ((n * n * n) % 1000 == 999) {
				break;
			}
			if (n > 10000) {
				break;
			}
		}
		System.out.println(n);
	}
}