小町数を使った数学パズルの第4弾です。

問題

３桁の数値とその数値を２乗した値の各数字が１から9までのすべての数字で構成されるような３桁の数値をすべて求めるプログラムを作成せよ。

例えば 763*763=582169 となるが、これは、1,2,3,5,6,7,8,9 からなり、4が抜けているからダメ。

どうやって解くか

これまで、いくつかの小町数に関連するパズルをプログラム(例えばこことかここ)で解いてきましたが、この問題は、100から999までの数を一つずつ調べていけばいいだけなので、プログラム的には一番優しい小町パズルかな。

下一桁が1, 5, 6ならば解ではないという、知識を使えば、さらに速くできるかもしれませんが、そのための判断に時間がかかるし、コードも複雑になります。
たかだた、999回の試行なので、特に工夫することなく素直なコードにしてみました。

LINQ使わないバージョン

static void Main(string[] args) {
    for (var n = 100; n < 1000; n++) {
        if (IsKomachi(n))
            Console.WriteLine($"{n}の2乗 = {n * n}");
    }
}

static private bool IsKomachi(int n) {
    char[] array = (n.ToString() + (n * n).ToString()).ToArray();
    Array.Sort(array);
    var s = new string(array); 
    return s == "123456789";
}

IsKomachi内の実装はいろいろな方法が考えられますが、ここでは、以下のようなロジックで判断しています。

nとnの２乗を文字列としてつなげ、それを　char[]に変換。
文字コード順にソートして、再度文字列に変換。
"123456789"と一致すれば、1-9の数字で構成されると判断。

LINQ使ったバージョンも書いてみました。

class Program {
    static void Main(string[] args) {
        foreach (var n in Enumerable.Range(100, 900).Where(n => IsKomachi(n))) 
            Console.WriteLine($"{n}の2乗 = {n*n}");
    }
    
    static private bool IsKomachi(int n) {
        string s = n.ToString() + (n * n).ToString();
        return "123456789".All(c => s.Contains(c));
    }
}

LINQのWhereメソッド、Allメソッドを使っています。

ちなみに、IsKomachiメソッド内に以下のコードがあります。

"123456789".All(c => s.Contains(c))

この式ですが、1がsに含まれているか、2がに含まれているか、3がに含まれているか、... 9がに含まれているかを調べ、すべてが成り立てば、trueになります。

return s.Length == 9 && "123456789".All(c => s.Contains(c));

とする必要はありません。999 * 999 = 998001 なので、必ず s.Length <= 9 になりますから、
この式がtrueならば、1-9の数字は一つずつ存在することが保証されます。

無理やり感がありますが、こんなコードでも答えを見つけられます。

static void Main(string[] args) {
    Enumerable.Range(100, 900)
              .Where(n => {
                    string s = n.ToString() + (n * n).ToString();
                    return "123456789".All(c => s.Contains(c));
              })
              .ToList()
              .ForEach(n => Console.WriteLine("{0}の2乗 = {1}", n, n * n));
}

結果

567の2乗 = 321489
854の2乗 = 729316

この記事は、Gushwell's C# Programming Pageで公開したものをに加筆・修正したものです。