1. 10000以下の 完全数 を求めるプログラムを組め。 ただし、完全数とは自分以外の約数の総和が自分自身と等しくなる 自然数のことである。たとえば6の約数は1,2,3,6であるが、6=1+2+3となる。
   • 完全数は無限個あるかどうかは未解決問題である。
   • 完全数は偶数のようであるが、 奇数の完全数が存在するかどうかは未解決問題である。
   • 知られている完全数は44個ある。
   (解答)

「任意の0でない自然数 n について

• n が偶数の場合、n を 2 で割る
• n が奇数の場合、n に 3 をかけて 1 を足す

1. n が10以下の自然数に関して正しいことを手計算で確かめよ。
2. 各ステップ毎にの自然数がどのように変化して1になるかプログラムを組みんで表示せよ。
3. n が10以下の自然数において最も長いステップ数となる数値はいくらか。

二乗の差の問題

Nを2以上の自然数として与えたとき x² - y² = N のように二乗の差がNとなるような 自然数の組(x,y)をこの問題の「解」と呼び、解を出力したい。

1. x² - y² = 31 をみたす解を手計算で求めよ。
2. x² - y² = 303 をみたす解を手計算で求めよ。

   この2問は「フォーミン他著, 志賀他訳, やわらかな試行を育てる数学問題集, 第3章問13(54ページ), 岩波, 2012」から出題。

3. N を任意の自然数として与えたときに x² - y² = N をみたす解 の存在について議論せよ(任意のNについて解があると言えるか？ 解が存在しない事もあるか？)。
4. N を与えたときに解を出力するプログラムを作成せよ。 「解なし」の出力は必要であるかどうか前問で確かめた上でプログラムせよ。

ラマヌジャンのタクシー問題(配列とソートの練習)

• i³ + j³ = k³ + l³ をみたす整数に1729が含まれていることを確認せよ。
• 1≦i,j,k,l≦100の範囲で i³ + j³ = k³ + l³ をみたす整数の個数を求めよ。(ラマヌジャン より)
• 1≦i,j,k,l≦100の範囲で i³ + j³ = k³ + l³ をみたす整数を大きさの小さい順番に並べよ。

カプレカ数

(カプレカ数 より引用) 整数の桁を並べ替えて、最大にしたものから最小にしたものの差を取る。 この操作によって元の値に等しくなる数をカプレカ数と呼ぶ。 例えば、7641 - 1467 = 6174 であるから、6174 はこの意味でのカプレカ数であり、 4桁では唯一のものである。

• 1から9999まで(1111 の倍数は除いた9990個)の数字から出発する。 4桁の数字について「最大にしたものから最小にしたものの差を取る」 操作を何回施せば6174に辿りつくか？
  (解答)

ユークリッドの互除法とは、自然数 a>b が与えられたとき、

gcd(a,b) = gcd(b,r)    ……(*)

ただし、

• gcd(a,b)はa,bの最大公約数を表す。
• r は a を b で割ったときの余りを表す。 (つまり、商を q とすると a = bq + r で 0 ≦r ≦b-1)

1. ユークリッドの互除法を用いて 12 と 8 の最大公約数が4であることを手計算で示せ。
2. 123456 と 234567の2数の最大公約数を求めよ。
3. 上記の関係式(*)を数学的に示せ (解答)。
4. (*)は「割られる数aと割る数 b の最大公約数は割る数 bと余り r の最大公約数と等しい」ことを言っている。 これを繰り返すと余りはいつかは必ず0になることを示せ (解答)。
5. 2¹²⁰-1と 2¹⁰⁰-1の最大公約数を求めよ。 これを求めるための計算を簡易的に行うためには厳密に言うと 上記の意味に限定した「ユークリッドの互除法」は直接適用できない ように思われる。どの部分か指摘した上で、 その具体例を小さな2数を用いて説明せよ。 (解答)
6. (*)を用いたユークリッドの互除法を用いて 最大公約数を出力するプログラムを作成せよ。ただし、以下のように行え。
   • 2つの自然数 a, b をscanfで読み込むようにせよ。
   • 入力は123456 と 234567の2数とせよ。
   (解答)

1. 35x + 22y = 1 となる (x,y)を求めるための(計算機を使わない)手計算を行え。 お勧めはユークリッドの互除法を用いて最大公約数を求めて、 それを遡って行う方法。 (解答)

2. 35x + 22y = 1 となる整数の組 (x,y)を求めるための手計算で 以下のように行った。同様な手法で 122 x + 41 y = 1 となる整数の組(x,y)を求めよ。 (解答)

   --------------------------------------------------------
   35 * 1 + 22 * 0 = 35
   35 * 0 + 22 * 1 = 22
   
   において、a = 35, b = 22 とおくと
   a * 1 + b * 0 = 35
   a * 0 + b * 1 = 22
   となり、この2つの式から0,1となっている部分を変化させることにより
   右辺が1となるように細工する。右辺を徐々に1に近づけることを考える。
   
   両辺を引いて
   a * 1 + b * (-1) = 13
   となるので1に近づいた。この式の1倍を直前の式から引いて
   
   a * (-1) + b * 2 = 9
   となるので1に近づいた。この式の1倍を直前の式から引いて
   
   a * 2 + b * (-3) = 4
   となるので1に近づいた。この式の2倍を直前の式から引いて
   
   a * (-5) + b * 8 = 1
   
   これにより x = -5, y = 8 として 35*(-5) + 22*8 = 1 と出力する。
   --------------------------------------------------------
   

3. 前問題を一般化して自然数 a≧b を与えた際に、a x + b y = gcd(a,b) となる整数の組 (x,y) を出力するプログラムを作成する。

   ========拡張ユークリッドの互除法のアルゴリズム========
   ----------------- 
   入力 : a,b
   出力 : gcd(a,b), 
          a*x+b*y = gcd(a,b) となる整数の組 (x,y)
   ----------------- 
   [1] (a(0),x(0),y(0))=(a,1,0), (a(1),x(1),y(1))=(b,0,1)
   [2] i=1,2,...について以下を繰り返す
   q(i+1) := a(i-1)をa(i)で割った整数の商 (<-商の整数部分)
   a(i+1) := a(i-1) - q(i+1)*a(i)
   x(i+1) := x(i-1) - q(i+1)*x(i)
   y(i+1) := y(i-1) - q(i+1)*y(i)
   ただし、a(i+1)=0ならばループを終了する。
   [3] [2]のループを出た後に
   gcd(a,b)=a(i)
   x = x(i)
   y = y(i)
   として出力する。
   

   このとき、以下の命題を証明することにより、 プログラムが正しく動作することが分かる。それぞれ証明せよ。 (解答)

   ------------------------
   命題1: a(i-1) を a(i) で割ったときの整数の商がq(i+1)で余りが a(i+1)となる。
         すなわち、a(i-1)=a(i)*q(i+1)+a(i+1)が任意のi≧1について成立する(ほぼ自明)。
   ------------------------
   ------------------------
   命題2: 任意のi≧1で a(i+1) = a*x(i+1)+b*y(i+1) が成立する(帰納法)
   ------------------------
   

   さらに、プログラムを作成して 35x + 22 y = 1 となる x,yをみつけよ。 その際、命題2が正しいことをプログラムを用いて確かめよ。 (解答)

• 二分法の問題
  • e^x は math.hを用いること。 使用の方法はここを見ること。
  (解答)

• ニュートン法の問題
  • sin(x) は math.hを用いること。 使用の方法はここを見ること。
  (解答)

• テイラー展開(指数関数)の問題
  • e^x は math.hを用いること。 使用の方法はここを見ること。
  (練習問題1の解答) (練習問題2の解答)

• テイラー展開(三角関数)の問題
  • sin(x), cos(x) は math.hを用いること。 使用の方法はここを見ること。
  (解答)

• 第二種スターリング数の問題
  • 再帰プログラムを用いること。
  (解答)
• 第1種スターリング数