澤健治(2012)「Python によるプログラミング入門(第6版)」

==================================================
p.16
問 3 最後まで実行はするのだが変な結果を表示するプログラムの例をプログラム1 を1 文字だけ変更して見つけなさい。

----------

プログラムを作ったときに、動くのだけれども、ちゃんとした答を返さなかった、ということはありませんか?大抵は打ち間違いによるもの、特に間違った変数を使った場合に起こります。

この問題は、この逆で、ちゃんと動くプログラムを元に、そのようなプログラムを作れ、という変わった問題です(やらなくてもよい、と書いたほうが良かったかもしれませんが、プログラムのデバッグをある程度経験していれば、思いついたはずです)

ここにあげるのはその一つの例です。局所変数として nとmが現れていますから、それを『間違った使い方』をすれば、答えとなるでしょう。

wday=("sun","mon","tue","wed","thu","fri","sat")

def cal0(n,m):
  # cal0(n,m) は1 つの月のカレンダーを作成する。
  # n は月の開始日の曜日を表す数字(0 から6) であり、
  # 0 は日曜日を意味する。
  # m はその月の日数である。例えば1 月はm=31 である。
  # 従って2000 年1 月のカレンダーはcal0(6,31) で表示される。
  for x in wday: print " ",x,
  print
  for x in range(0, n): print "  ---",
  for x in range(1, n+1):            # m+1 を n+1と「間違えて書く」
    print "%5d"%x,
    if (x+n)%7==0 : print
  print

この実行結果は次です:

>>> cal0(6,31)

  sun   mon   tue   wed   thu   fri   sat
  ---   ---   ---   ---   ---   ---     1
    2     3     4     5     6


本来の結果と比べてみてください:

>>> cal0(6,31)
  sun   mon   tue   wed   thu   fri   sat
  ---   ---   ---   ---   ---   ---     1
    2     3     4     5     6     7     8
    9    10    11    12    13    14    15
   16    17    18    19    20    21    22
   23    24    25    26    27    28    29
   30    31


==================================================

p.18
問4 四捨五入によって得られた2 つの数字3.278 と73.2 がある。この2 つの数字の掛け算を計算機で計算すると239.9496 になるのだが、この数字のどこまでが信頼できるかを元の数字の曖昧さを考慮した上で吟味しなさい。

ヒント: 3.278 は四捨五入で得られた数字てあるから、元の数字は、3.2775 以上、3.2785 未満である

----------

解説: これは Python の問題ではなく、数を扱う問題一般についての話。

「有効数字の桁数」というのを覚えているだろうか(高校の物理でやったはず)。
巻き尺で長さを諮ることを考えよう。単位をm単位とすると、
3.278 というのは、 3m 27.8cm と読み取ったことを意味する。もちろん、このようにきちんと測れるわけではないので、読み取り誤差や、目盛の粗さが関係している。
普通はヒントにあるように、3.278という値は、実際の値が3.2775m以上、3.2785未満であったことを示している。つまり信用できる値は3 2 7 8という4個の数字であるので、この場合有効数字を4桁という。
それに対し、3.278000 と書いたらどうだろうか。
   これが意味することは、実際の値が 3.2789995以上 3.278005未満であったことである。従って、この場合の有効数字の桁数は 3 2 7 8 0 0 0 という7個である。
値としては 3.278 と同じ用に見えるかもしれないが、伝えられる情報はかなり違うものだ、ということに注意して欲しい

次の 73.2 は有効数字が3桁、というのはわかりますね。
これらを掛け算した場合、計算上は 239.9596 になります。しかし、今の説明から分かるように、 3.278では4つの数字だけが信用でき、73.2では3つの数字だけが信用できるものでした。そこで、その掛け算では本当に信用できるものは 先頭の3つだけ、と考えます(他の数値には誤差が含まれている)。
         239.9596
           ↑ までが信用できる  --- 239 
そして、239の次の数字を四捨五入します。9 ですから、239 + 10 = 240 
となります。

実際に、 3.27845 * 73.15 と 3.27855 * 73.25 を計算してみるとわかります。

>>> 3.2775*73.15
239.74912500000002

>>> 3.2785 * 73.25
240.150125

上の計算から分かるようにどちらも 240 ± 0.5 の範囲に収まっていることがわかりますね。

ちなみに、この2つの足し算の結果は
76.478000000000009
と表示されます (最後の 9 に不思議に思う人がいるかもしれませんね)。
これは科学的にはどのように書くのが妥当でしょうか。
考えてみてください
(ヒント: 1つの物を2つに分けて計測することを考えましょう)

==================================================

問6 上の問題は、次の有名な定理(Fermat の定理):
     m が素数の時にx^(m-1) をm で割った余りは1 である。ここに xは 1,2,...,m-1の
     どれでもよい。
の特別な場合(x = 7、m = 11) です。x = 2 として、いろいろなm について試し、m が素数でなくとも余りが1 になるm の値を見つけなさい。

----------

解説:
  Fermatの定理とここで行うことの違いについて注意しておく。
Fermatの定理は「 mが素数なら m-1以下の数 xに対し x^(m-1)をmで割った余りが1になる」と書いてあります。
これはつまり、mが素数でないなら「x^(m-1)をmで割った余りが1になる」ことを排除していません。
そして、実際に、x=2として、そのような数mを見つけてみよう、というのがこの問題です。

しかしながら、これは手計算ではとても無理です。そこで計算機 (プログラミング) の出番です。

初めに m ≦100として、 2^(m-1) % m がどのような値になるかみてみましょう。

>>> for z in range(2,100):
    w = 2**z
    print 2,"**",z-1," = ",w/2," and residual by ",z, " = ",(w/2)%z

2 ** 1  =  2  and residual by  2  =  0
2 ** 2  =  4  and residual by  3  =  1
2 ** 3  =  8  and residual by  4  =  0
2 ** 4  =  16  and residual by  5  =  1
2 ** 5  =  32  and residual by  6  =  2
2 ** 6  =  64  and residual by  7  =  1
(中略)
2 ** 96  =  79228162514264337593543950336  and residual by  97  =  1
2 ** 97  =  158456325028528675187087900672  and residual by  98  =  58
2 ** 98  =  316912650057057350374175801344  and residual by  99  =  58

余りが1になっても、mが素数かどうかの判定が難しそうです。

そこで、xの候補として 3と7 (いずれも素数)を加えて
2^(m-1)%m は1になるが 3^(m-1)%m か 7^(m-1)%mが1ではない(つまり素数ではない)
数を見つけることを考えましょう。
それが次のプログラムです

>>> for z in range(8,1000):         # 8から1000までの範囲で探す
  w = 2**(z-1)%z; u = 3**(z-1)%z; v = 7**(z-1)%z
  if (w == 1) and ((u != 1) or (v != 1)):	# すべてが1でなければ素数でない
     print w, u, v, "\t",z

1 56 56 ==> 341
1 375 1 ==> 561
1 36 436 ==> 645

あきらかに645は素数でない。また,561も3の倍数、341は11の倍数。