暇なので
暇つぶしに数学オリンピックの
問題をプログラムで解いてみることにしました。


解説動画はこちら



さて今回はこんな問題です。

引用:2016年ジュニア数学オリンピック予選
「各桁の数字が相異なるような37の倍数のうち
最大のものを求めよ。」


雑なコードで解いてみることにします。

各桁が異なる整数で最大になるのは・・・
9876543210
でしょうね。

あとは37の倍数ならOKなので
この値から1ずつ引いて
37の倍数 
かつ
各桁が異なる整数
になれば良いですね。

コードはこんな感じになりました。
num = 9876543210
for i in range(num,0,-1):
    if i%37==0 and len({n for n in str(i)})==10:
        print(i)
        break

答えは・・・

9876435012

各桁が異なる整数で37で割り切れますね。

コードでは判定する部分として
37で割りきれるかどうかは
37で割った余りが0になるということになります。

%で余を求められるので
計算できますね。

10桁の各桁が異なるは
いったん数字に直して
10個の数字をセットに入れ込みます。

そうすると各桁が違い場合は
長さが10

各桁で同じ数字が来た場合は
長さが10未満になるので弾けます。

この2つの判定を用いて
その最大値を求めました。

プログラムで解くと
早く終わりますねwww


では次

引用:平成26年度 京都数学オリンピック道場
10 桁の正の整数の各桁に 0 以上 9 以下のすべての整数が現れ
かつ 11111 の倍数であるとき,
その整数を面白い整数と呼ぶことにする。
面白い整数は全部でいくつあるか。

これもさっきと同じ
各桁が違うがそのまま使えますね。

割る数を変えて11111にすれば
簡単に解けちゃいますね!!!!!
num = 9876543210
result = []
for i in range(num,1023456789,-1):
    if i%11111==0 and len({n for n in str(i)})==10:
            result.append(i)

・・・
うーーーん

全然プログラムが終わりません。
10桁なので90億回近く計算する羽目になります。

これだと普通のPCではなかなか終わりません。
そこでもっと効率の良いコードを
考えてみることにします。
import itertools

result = []
for nums in itertools.permutations([1,2,3,4,5,6,7,8,9,0],10):
    num = int(''.join([str(n) for n in nums]))
    if num<1000000000: 
        break
    if num%11111==0:
        result.append(num)
print(len(result))

itertoolsを使うと
順列を求めることができます。

この場合全ての桁の数が違う数値10個を使った
順列を求めてあげれば
10桁全ての整数で判定しなくても良くなります。

答えはresultの個数を数えて
3456個になりました。


最後は
引用:平成26年度 京都数学オリンピック道場

ある日数学者ハーディが入院中の
友人ラマヌジャンを見舞いに行ったとき
「乗ってきたタクシーのナンバーが XXXX だった。」
と言ったところ,これを聞いたラマヌジャンは
「とても興味深い数字です

XXXX は2つの立方数の和で 2 通りに表せる
最小の数なのです。」と答えた。

ここで XXXX はある 4 桁の正の整数を表している。
このとき次の問題に答えなさい。

スクリーンショット 2021-10-02 17.44.40

さて、この数式を少し変えてみると
スクリーンショット 2021-10-02 17.44.45

これならプログラムに組み込めますね。
早速mとnを求める感じにしてみましょう。
for m in range(2,100):
    for n in range(2,100):
        if m**3-n**3 == 999:
            print('m:{0} , n:{1}'.format(m,n))
            break
m:12 , n:9

さて答えはmが12 , nが9です。

この二通りの組み合わせから求められる
4桁の整数は

1729

になります。

このような2つの立方数の和として
n 通りに表される最小の正の整数を

ラマヌジャンさんのタクシー数
と言っているそうです。

なかなか面白い数ですね。

タクシー数は他にもありますが
手計算するのはしんどいですねーーー

でもプログラムならすぐに求めることができるのが
プログラムのいいところです。

数学オリンピックの問題でさえも
整数問題なら、PCを持ち込めれば解ける!!!!!
(多分ダメだーー)

なので、答えだけは出せます。
手でやる解き方は知りません。

今回はここまでです
それでは。