第4回: 整数問題をPythonで解く----if条件とfor条件の使い方 - 疑念は探究の動機であり、探究の唯一の目的は信念の確定である。

どうも僕です。
今回は、東大の入試問題をプログラムを使って解いてみます。

f:id:yoheiwatanabe0606:20180930114147p:plain

予備知識
プログラムを書く
おまけ

2005年に東大入試で次の整数問題が出ました。

${3}$ 以上 ${9999}$ 以下の奇数 ${a}$ で、 ${a^2-a}$ が ${10000}$ で割り切れるものを全て求めよ。

これを実際に解こうとすると、結構めんどくさいです。ある解法は ${a(a-1)}$ より、「隣り合う整数は互いに素である」ことを利用しています。それでも ${9999}$ 以下の素数の中から ${a = 625, 1250, ..., 9375}$ の15通りを調べなければなりません。ですので、手作業で計算するのはとても煩わしいです。これをプログラムで解きたいと思います。
まずは、プログラムを作るために予備知識として「リスト」「for」「if」を説明したいと思います。

予備知識

>>> r = range(1, 3)
>>> print(r)
range(1, 3)

# range にある3は入らず、その一つ前の整数までしかない。
>>> print(tuple(r))
(1, 2)
>>> print(list(1, 2))
[1, 2]

# 奇数だけ出力することもできる。
>>> r_odd = range(1, 11, 2)
>>> l_odd = list(r_odd)
>>> print(l_odd)
[1, 3, 5, 7, 9]
# 最後の2で一つずつの間隔をあけてリストに表示される。

リストの要素は変更できます。それを増やしたり減らしたりできます。今回は要素を増やす ${\texttt{append}}$ のみを使います。

# 要素を増やす。
>>> l = [1, 2, 3]
>>> l.append(4)
>>> print(l)
[1, 2, 3, 4]

# 空リストから要素を一つずつ入れる。
>>> l_emp = []
>>> l_emp.append(1)
>>> print(l_emp)
[1]
>>> l_emp.append(2)
>>> print(l_emp)
[1, 2]
>>> l_emp.append(3)
>>> print(l_emp)
[1, 2, 3]
>>> l_emp.append(0)
>>> print(l_emp)
[1, 2, 3, 0]

リストはこのように変更可能ですが、タプルはそのようにできません。
次に ${\texttt{if}}$ を説明します。

if条件

${\texttt{if}}$ は「もしも~ならば」と、ある条件を満たす場合のことを表されています。他にも ${\texttt{elif}}$ や ${\texttt{else}}$ がありますが今回は使いませんので省略します。
${\texttt{if}}$ の後に条件を入れます。その後にダブルコロン (:)を入れなければなりません。その次の段落では最低でも1つの空白を入れなければなりません。慣用では4つの空白が入ります。
f:id:yoheiwatanabe0606:20180930131002p:plain

>>> n = 2
>>> if n%2 == 0: #もしnが2で割ってその余りが0ならば, i.e., もしnが2の倍数ならば
...     print('n is even.')
... 
n is even.

>>> n = 3
>>> if n%2 == 0:
...     print('n is even.')
...                           #nが3であり、これが2の倍数ではないので、何も表示されていない。

>>> n = 3
>>> if n%2 == 0:
...     print('n is even.')
... else:          #elseはそうでなければの意味。ここでは「nが2の倍数でないならば」の意味。
...     print('n is odd.')
... 
n is odd.

最後に ${\texttt{for}}$ を説明します。

for条件

${\texttt{for}}$ はだいたい次のような感じです。ダブルコロンの使用や空白の使用は ${\texttt{if}}$ と同じです。

>>> l = [1, 2, 3, 4]
>>> for i in l:
...     i + 1 #リストの各要素に対して、+1する。
... 
2
3
4
5
>>> l = [1, 2, 3, 4]
>>> for i in l:
...     print(i + 1) #printがあってもよい。
... 
2
3
4
5

>>> l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l_emp = []
>>> for i in l:
...     j = i + 2
...     l_emp.append(j)
... 
>>> print(l_emp)
[3, 4, 5, 6, 7, 8, 9, 10, 11] #[1 + 2, 2 + 2, ..., 9 + 2]

以上で準備ができました。

プログラムを書く

今回のプログラムは以下のような仕組みです。

(1) 3から9999までのリスト ${\texttt{l}}$ を用意する。つまり、 ${\texttt{l = [3, 4, 5, ..., 9997, 9998, 9999$ }}]
(2) 空リスト ${\texttt{l_answer = [$ }}] を用意する。
(3) リスト ${\textt{l}}$ の各要素 ${\texttt{i}}$ に対して、
(4) もし、 ${\texttt{i}}$ が奇数であり、かつ、 ${\texttt{i}^2-\texttt{i}}$ が10000で割り切れるならば、
(5) その要素 ${\texttt{i}}$ を空リスト ${\texttt{l_answer}}$ に入れる。
(6) ${\texttt{l}}$ のすべての要素を調べた後に、 ${\texttt{l_answer}}$ をタプルに変換したものをプリントする。

このプログラムはもう少し改良できて、初めからリストを奇数のみにしてそれを調べてもいいと思います。
あとはこの考えをPython言語に翻訳すれば終わりです。そのプログラムは次のように書かれます。

#1
>>> l = list(range(3, 10000))
>>> l_answer = []
>>> for i in l:
...     if i % 2 == 1 and (i**2-i)%10000 == 0: #i**2はiの二乗を表している。
...         l_answer.append(i)
... 
>>> print(tuple(l_answer))
(625,)

#2
>>> l2 = list(range(3, 10000, 2))
>>> l2_answer = []
>>> for i in l2:
...     if (i**2 -i)%1e4 == 0: #1e4は1×10^4(10の4乗)を表している。
...         l2_answer.append(i)
... 
>>> print(tuple(l2_answer)) 
(625,)

よって、答えは625です。実際、625を確認したら、 ${625^2-625}$ が10000で割り切れることがわかりました。

>>> (625**2 -625)/1e4
39.0

おまけ

東大の入試は3から9999までの奇数の範囲での問題でした。その範囲を変えてみたらどのような結果が出るのでしょうか。少し調べてみました。

#1: 範囲を99999までに拡大したとき: 実は625の次は10001である。
>>> l2 = list(range(3, 100000, 2))
>>> l2_answer = []
>>> for i in l2:
...     if (i**2 -i)%10000 == 0:
...         l2_answer.append(i)
... 
>>> print(tuple(l2_answer))
(625, 10001, 10625, 20001, 20625, 30001, 30625, 40001, 40625, 50001, 50625, 60001, 60625, 70001, 70625, 80001, 80625, 90001, 90625)

#2: 範囲を負の整数のとき: -2000までならば、-624しかない。
>>> l_test = list(range(-2000, 0))
>>> l_test_answer = []
>>> for i in l_test:
...     if (i**2 -i)%10000 == 0:
...         l_test_answer.append(i)
... 
>>> print(tuple(l_test_answer))
(-624,)

>>> l_test = list(range(-10000, 0))
>>> l_test_answer = []
>>> for i in l_test:
...     if (i**2 -i)%10000 == 0:
...         l_test_answer.append(i)
... 
>>> print(tuple(l_test_answer))
(-10000, -9999, -9375, -624)

他にも条件を変えて調べてみたらおもしろいかもしれません。

僕から以上