●回答
2001


●証明


○補題
「n^nの末尾m桁はnの下m桁で決まる」
(証明略、ほぼ自明）


これによって、１桁目より順番に決定していけばよい。


１桁目が１になるのは


・1(nは何でもよい）
・9(nは２の倍数)だが、


nの下一桁が9であることとnが偶数であることは矛盾するので、１桁目は１に確定する。


同様に２桁目は０になる。
２桁目を他の数字にすると、nが２の倍数／５の倍数／１０の倍数の時に条件を満たすが、いずれも仮定した１，２桁目の条件に矛盾する。


３桁目も同様に０となる。


４桁目については以下の通り。


nの下４桁……n^nの下４桁が2001になる条件
0001……不適
1001……n=2+10a
2001……n=1+5a
3001……n=4+10a
4001……n=3+5a
5001……不適
6001……n=2+5a
7001……n=6+10a
8001……n=4+5a
9001……n=8+10a


上記のうち、左右矛盾しないのはnの末尾が2001のときのみ。
また、nの下４桁が2001の時、必ずn=1+5aの形で書き表されるので、「nの下４桁が2001である」という条件はn^nの下４桁が2001となるための必要十分条件である。


●短評
一番綺麗な答えになって満足しました。見事です。

補題は、
「n^nの末尾m桁は(nの下m桁)^nで決まる」
ですね。
２桁目（３桁目）、４桁目の決め方からはきちんと認識されていことが伺えます。

解答
２００１
問題になるくらいだから想像です。
正直に言うとLongcalcという電卓フリーソフトで確認しました。
下一桁は手計算で１になったけど、2001乗は断念しました。
（１０桁電卓では無理だってえの。ばかだねえ）
ですので当然、証明など私の頭では不可能です。


ところで、新しい作品集完成おめでとうございます。
神詰大全の続編を期待していたのですが、すぐに発行されるとは！
神詰大全も毎日で２ヶ月かかり堪能しました。
このところの一族の精力的な活動には敬服いたします。
今回はCDROM版で拝見させていただきます。（ごめんなさい）
ですので住所などは省略します。（懸賞では心苦しい）
これからも、作品や熱き語りなどで楽しませてくださいね。
ではまた。楽しみに待ちつつ…。

想像だろうが電卓を使おうが正解は正解です。


「神詰大全」お申し込みのときの住所を控えてありますので、「TURN OF THE CENTURY」も送付させていただきます。
ぜひ、お受け取りください。
今後もいろいろの作品集を出して行こうと夢想しています。こちらも気長にお待ち下さい。

答えはやはり、2001しかありません。
以下、簡単な証明です。
（証明）
nの下４桁をABCDとします。


2001は奇数なので、nも奇数。つまり、Dは1,3,5,7,9のいずれかです。
しかし、奇数乗して下一桁が1になりうるのは D=1 のときだけです。


次に、n = 1 + 10C +（100の倍数） とおくと、
n^n = 1 + n*10C +（100の倍数）
= 1 + 10C +（100の倍数）
となり、C=0 がわかります。


さらに、n = 1 + 100*AB +（10000の倍数） とおくと、
n^n = 1 + n*100*AB +（10000の倍数）
= 1 + 100*AB +（10000の倍数）
となり、AB = 20 がいえます。
（証明終）

簡単なというより簡潔な証明ですね。
蛇足ながら、上記証明には二項定理が使われています＞訪問諸氏


ちなみに作者はまずプログラムを書いて検証したのでした。

/*
 * m = n % 10000 (m ^ n % 10000 = n ^ n % 10000)
 * m ^ g % 10000 = 1
 * m ^ a % 10000 = 2001
 * n = 10000 * x + m = g * y + a
 */

#include <stdio.h>

void main()
{
    long m, g, a, p;

    for (m = 0; m < 10000; m++) {
        if (m % 2 == 0 || m % 5 == 0) continue;
        for (p = 1, g = 1; ; g++) if ((p = p * m % 10000) == 1) break;
        for (p = 1, a = 1; a < g; a++) if ((p = p * m % 10000) == 2001) break;
        if (a == g) continue;
        if (10000 % g != 0 ) printf("!\n");
        else if ((m - a) % g != 0) continue;
        else printf("m = %ld\n", m);
    }
}