1996年京都大学の入試問題について

Question

m, n は自然数で、m < n を満たすものとする。
m^n + 1, n^m + 1 がともに10の倍数となる m, n を
1組与えよ。

プログラミングで解いてください。
使用言語はC++、Ruby、Pythonのいずれかでお願いします。

ちなみに、私は以下のように解きました。

n, m = 2, 1
ans = []
while ans.size == 0
  for m in (2..n - 1)       # mは1でない。
    ans << m << n if (m ** n % 10 == 9) && (n ** m % 10 == 9)
  end
  n += 1
end
p ans

Answer 1

Enumurator::Lazy を使ってみました。
参考： Ruby 2.1.0 リファレンスマニュアル > ライブラリ一覧 > 組み込みライブラリ > Enumerableモジュール > lazy
http://docs.ruby-lang.org/ja/2.1.0/method/Enumerable/i/lazy.html
> ... ピタゴラス数 (a2 + b2 = c**2 を満たす自然数 a, b, c の組) を 列挙するプログラム ...

# coding: utf-8

def pares
  (1..Float::INFINITY).lazy.flat_map {|n|
    (1...n).select {|m|
      ((n ** m + 1) % 10 == 0) && ((m ** n + 1) % 10 == 0)
    }.map {|m|
      [m, n]
    }
  }
end
# 最初の (m, n) を表示する
p pares.take(1).force[0]

Comments

[katoy]

この手の問題に興味があるなら、次の問題も説いてみるとよいとおもいます。
- 「今週のアルゴリズム：ピタゴラス数」 [https://codeiq.jp/magazine/2013/11/2437/](https://codeiq.jp/magazine/2013/11/2437/)

Answer 2

ループのネストを return で抜けるようにしてみました。

def solve
  (1..2**30).each do |n|
    (1...n).each do |m|
      return [m, n] if ((m ** n + 1) % 10 == 0) && ((n ** m + 1) % 10 == 0)
    end
  end
  []
end

puts "#{solve}"

Answer 3

アルゴリズムは同じですが。

(2..Float::INFINITY).each do |n|
    break unless (1..(n-1)).each do |m|
        if (m**n+1) % 10 == 0 and (n**m+1) % 10 == 0 #ここは問題通り書いた方が良いかと
            p [m,n]
            break false
        end
    end
end

「mは1でない」というのは正しいのですが、数学的に考えた結果かなと思って採用してません。