第13回 アカデミックスキルII C言語(6) 余裕がある人向けの課題

10未満の3もしくは5の倍数は, 3, 5, 6, 9 でその和は 23 である．

1000未満の3もしくは5の倍数の和を求めよ．

• 原文と答え合わせはこちらから → Problem 1 - Project Euler

Fibonacci 数列 F(1), F(2), F(3), ... において，=F(n)= の値は F(n-1) と F(n-2) の和で与えられる． F(1) = 1, F(2) = 2 とするとき，最初の10個の項は

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

となる．

400万以下の Fibonacci 数列の中で，偶数のものの和を求めよ.

• 原文と答え合わせはこちらから → Problem 2 - Project Euler

13195 の素因数は 5, 7, 13 および 29 である. 600851475143 の素因数の中で最大のものを求めよ．

600851475143 は int 型で取り扱える最大値(2147483647)よりも大きいので, unsigned long int (符号無し倍長整数型)を使うこと．

• 原文と答え合わせはこちらから → Problem 3 - Project Euler

回文数(palindrome)とは, 11, 101, 12321 など, 右からも左からも同じように読める整数である． 2桁の整数の積として作れる最大の回文数は 9009 = 91 x 99 である．

3桁の整数の積として作れる最大の回文数 を求めよ．

• 原文と答え合わせはこちらから → Problem 4 - Project Euler

2520 は 1 から 10 のいずれの整数でも割り切れる最小の数である． 1 から 20 のいずれの整数でも割り切れる最小の正の整数を求めよ．

• 原文と答え合わせはこちらから → Problem 5 - Project Euler

最初の10個の自然数の 二乗の和 は

1^2 + 2^2 + ... + 10^2 = 385

である．最初の10個の自然数の 和の二乗 は

(1 + 2 + ... + 10)^2 = 55^2 = 3025

である．従って，最初の10個の自然数の二乗の和と和の二乗の差は 3025 - 385 = 2640 である．

最初の100個の自然数の「二乗の和」と「和の二乗」の差を求めよ

• 原文と答え合わせはこちらから → Problem 6 - Project Euler

素数を小さい順に並べると 2, 3, 5, 7, 11, 13 であるから，6番目の素数は 13 と判る． 10,001番目の素数を求めよ

• 原文と答え合わせはこちらから → Problem 7 - Project Euler

ピタゴラス3つ組(Pythagorean triplet) (a, b, c) とは, a < b < c なる自然数で,

a^2 + b^2 = c^2

を満足するものである．例えば, 3^2 + 4^2 = 5^2 なので, (3,4,5) はピタゴラス3数である．

ピタゴラス3数 (a,b,c) で a + b + c = 1000 となるものの積 abc を求めよ

• 原文と答え合わせはこちらから → Problem 9 - Project Euler

10未満の素数の和は 2 + 3 + 5 + 7 = 17 である.

200万未満の素数の和を求めよ

• 原文と答え合わせはこちらから → Problem 10 - Project Euler

三角数の順列 T(1), T(2), ... は，前の項に自然数を加えていくことで生成される．例えば, 7番目の三角数は T(7)=1+2+3+4+5+6+7=28 となる． 最初の10個の三角数は

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

である．

最初の7個の三角数の約数を列挙すると,

1:	1
3:	1,3
6:	1,2,3,6
10:	1,2,5,10
15:	1,3,5,15
21:	1,3,7,21
28:	1,2,4,7,14,28

となり, 5個を超える約数を持つ最初の三角数 が 28 であることが判る．

500個を超える約数を持つ最初の三角数 を求めよ

• 原文と答え合わせはこちらから → Problem 12 - Project Euler

正の整数に対して, 下記のルールに従って生成される数列を考える:

n -> n/2 (n が偶数)
n -> 3n+1 (n が奇数)

このルールに従って 13 から生成した数列は,

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

となり, (13 から始まって 1 まで終わるまで)10個の項で構成される． 厳密な証明はされていない(Collatz 問題)ものの，この数列はどのような整数から始まっても 1 で終わると考えられている．

数列長が最も長くなるような 100万未満の最初の数を求めよ

注意: 生成された数列に100万以上の数値が含まれていてもよい．

• 原文と答え合わせはこちらから → Problem 14 - Project Euler

1から5までの数字を単語で書き下すと one, two, three, four, five となり，そこで使われる文字数は全部で 3 + 3 + 5 + 4 + 4 = 19 個である．

1から1000 (one thousand) までの数字を単語で書き下した時，使われる文字数を求めよ

注意: 空白やハイフンはカウントしない．例えば, 342 (three hundred and forty-two) には 23 文字が含まれ, 115 (one hundred and fifteen) には 20文字が含まれる． 文字を書き下す際の "and" の用法は, British usage (例えば, ここあたり を参考に) に従う．

• 原文と答え合わせはこちらから → Problem 17 - Project Euler

下記の情報が与えられている．

• 1900年1月1日は月曜日
• 4月, 6月, 9月, 11月は 30日
• 2月は閏年ならば 29日, 平年(閏年でない)なら 28日
• それ以外の月(1月, 3月, 5月, 7月, 8月, 10月, 12月)は31日
• 閏年は「4で割り切れるが100では割り切れない年」または「400で割り切れる」年．

20世紀(1901年1月1日から2000年12月31日)の間で，日曜日で始まる月はいくつかあるか求めよ

• 原文と答え合わせはこちらから → Problem 19 - Project Euler

d(n) を n の真の約数(proper divisors; n より小さい約数)の和とする． もし2つの整数 a != b について d(a) = b かつ d(b) = a であるとき, a と b は互いに友好的(amicable)であると呼び, a と b のそれぞれを 友愛数(amicable numbers) と呼ぶ．

例えば, 220 の真の約数は 11, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である． 284 の真の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である．

10000より小さい友愛数の和を求めよ

• 原文と答え合わせはこちらから → Problem 21 - Project Euler

完全数とは, その真の約数の和が，その数自身に一致する数である．例えば， 28 の真の約数の和は 1 + 2 + 4 + 7 + 14 = 28 であるから, 28は完全数である．

ある数 n について，その真の約数の和が n より小さい時は 不足数(deficient), 和が n より大きい時は 過剰数(abundant) と呼ばれる．

最小の過剰数は 12 (1 + 2 + 3 + 4 + 6 = 16)であるため，2つの過剰数の和で表される 最小の数は 24 となる．数学的な解析によって, 28123 より大きな整数は 全て 2つの過剰数の和で表されることが明らかになっている． 「2つの過剰数の和で表せない最大の数」がこの上限よりも小さいことは分かっているのだが， 解析的にこの上限を減らすことはできていない．

2つの過剰数の和で表せない正の整数の総和を求めよ

• 原文と答え合わせはこちらから → Problem 23 - Project Euler

順列(permutation)とは，順序つきの並びである．例えば, 3124 は10進数 1, 2, 3, 4 の順列の1つである． 全ての順列が数値もしくはアルファベット順に並べたものを，辞書式順序(lexicographic order)と呼ぶ． 0, 1, 2 の辞書式順列は

012, 021, 102, 120, 201, 210

である．

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 からなる順列のうち，辞書式順序で 100万番目 になるものを求めよ

• 原文と答え合わせはこちらから → Problem 24 - Project Euler

単位分数(unit fraction)は分子が1の分数である． 2から10までを分母に持つ単位分数を10進数で表すと，

1/2     =       0.5
1/3     =       0.(3)
1/4     =       0.25
1/5     =       0.2
1/6     =       0.1(6)
1/7     =       0.(142857)
1/8     =       0.125
1/9     =       0.(1)
1/10    =       0.1

となる．ここで, 0.1(6)は 0.166666… を意味し, 1桁の循環(recurring cycle)を持つ． 1/7 は 6桁の循環を持つことが判るだろう．

1000未満の整数(d < 1000)の中で，1/n の小数部分に含まれる循環が最も長くなるものを求めよ．

• 原文と答え合わせはこちらから → Problem 26 - Project Euler

Euler は下記の並外れた二次式を発見した:

n^2 + n + 41

この式は, n に 0 から 39 を順に代入することで 40 個の素数を生成できることが判っている． しかし, n = 40 の時には, 40² + 40 + 41 = 40 (40 + 1) + 41 は 41 で割り切れるし，当然ながら, n = 41 の時には, 41² + 41 + 41 は明らかに 41 で割り切れる．

後に, 別の二次式 n ^ 2 - 79 * n + 1601 が発見された．この式は n に 0 から 79 を順に代入することで, 80 個の素数を生成できる． この係数 -79 と 1601 の積は -126479 である．

次の形の二次式:

n^2 + a * n + b, |a| < 1000, |b| < 1000

を考える．ただし, |a|, |b| は, それぞれ, a と b の絶対値を表す． n = 0 から順に値を代入していったときに, 最も多くの素数を生成するようなこの二次式の係数 a と b の積を求めよ．

• 原文と答え合わせはこちらから → Problem 27 - Project Euler

1 から右に時計回りに数値を並べて 5 x 5 の螺旋(spiral)を構成すると

21	22	23	24	25
20	7	8	9	10
19	6	1	2	11
18	5	4	3	12
17	16	15	14	13

となる．このとき，対角要素の和は 101 となる．

同様の方法で 1001 x 1001 の螺旋を構成したときの対角要素の総和を求めよ．

• 原文と答え合わせはこちらから → Problem 28 - Project Euler

驚くべきことに，その各桁の4乗の和で表せるような数は，以下の3つしかない：

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

ただし, 1 = 1⁴ は「和」ではないので含まない．これらの数の和は 1634 + 8208 + 9474 = 19316 である．

「その各桁の5乗の和で表される数」の総和を求めよ

• 原文と答え合わせはこちらから → Problem 30 - Project Euler

英国の貨幣は£(ポンド)トp(ペンス)で構成され，下記の8種類のコインが一般に流通している:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p).

以下の方法で £2 を作ることができる．

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

これらのコインを使って £2 を作るには何通りの方法があるか？

• 原文と答え合わせはこちらから → Problem 31 - Project Euler