疑念は探究の動機であり、探究の唯一の目的は信念の確定である。

数学・論理学・哲学・語学のことを書きたいと思います。どんなことでも何かコメントいただけるとうれしいです。特に、勉学のことで間違いなどあったらご指摘いただけると幸いです。 よろしくお願いします。くりぃむのラジオを聴くこととパワポケ2と乃木坂(けやき坂)が人生の唯一の楽しみです。

第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」を説明したいと思います。

予備知識

リスト

リストは重複を許す集まりです。タプルもそのようなものですが、リストは中身を変化できますが、タプルはできません。

# list
>>> list_empty = []
>>> print(list_empty)
[]
>>> l = [1, 2, 3]
>>> print(l)
[1, 2, 3]
>>> a = 1, 2, 3
>>> list(a)
[1, 2, 3]

# rangeというものを使って、整数を表示させる。
>>> list(range(1, 4))
[1, 2, 3]
>>> l2 = [1, 1, 2, 3, 4]
>>> print(l2)
[1, 1, 2, 3, 4]
# tuple
>>> t = (1, 2, 3)
>>> print(t)
(1, 2, 3)

# かっこ( )はあってもなくてもいい。
>>> a = 1, 2, 3
>>> print(a)
(1, 2, 3)
>>> print(tuple(a))
>>> (1, 2, 3)

# tupleを使ってリストをタプルに変換する。
>>> l = [1, 2, 3]
>>> t= tuple(l)
(1, 2, 3)

ここで {\texttt{range}} の使い方についてみてみましょう。

>>> 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
f:id:yoheiwatanabe0606:20180930131102p:plain
f:id:yoheiwatanabe0606:20180930131219p: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)

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



僕から以上