Problem 1 「3と5の倍数」
10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.
同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.
練習問題。ベクトルで一気に求める。
v = 1:999
ans = sum(v[(v%%3==0)|(v%%5==0)])
print(ans)
Problem 2 「偶数のフィボナッチ数」
フィボナッチ数列の項は前の2つの項の和である. 最初の2項を$1, 2$とすれば, 最初の10項は以下の通りである.
$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.
フィボナッチ数列の一般項は、黄金比を$\phi$と表すと、$$F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$$で求まる。ただし、$F_1=F_2=1$である。
ここで、$\phi^n \gg (-\phi)^{-n}$となるので、$$F_n \simeq \frac{\phi^n}{\sqrt{5}}$$と近似すると、$F_n \leq N$を満たす最大の$n$は以下の式で求まる。
n = \mathrm{floor}\left(\frac{\log_{10}N + \log_{10}\sqrt{5}}{\log_{10}\phi}\right)
あとは、フィボナッチ数列を初項から第$n$項まで生成して、そのうち偶数値の項の和をとれば良い。
ちなみに、$N=4000000$のとき、
\begin{align}
n &= \mathrm{floor}\left(\frac{\log_{10}N + \log_{10}\sqrt{5}}{\log_{10}\phi}\right) \\
&= \mathrm{floor}\left(\frac{\log_{10}4000000 + \log_{10}\sqrt{5}}{\log_{10}\phi}\right) \\
&= \mathrm{floor}\left(33.26295\right) = 33
\end{align}
なので、第$33$項まで。
limit = 4000000
phi = (1+sqrt(5))/2
n = (log10(limit) + log10(sqrt(5)))%/%log10(phi)
f = as.integer((phi^(1:n) - (-phi)^(-(1:n)))/sqrt(5))
ans = sum(f[f%%2==0])
print(ans)
Problem 3 「最大の素因数」
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
$n=600851475143$とする。
素因数を探すには素数で割り切れるかを確認していけば良い。
$n$は奇数なので、$2$は素因数ではない。
従って、$3$から$\sqrt{n}$までの素数で割り切れるかを確認していけば良い。
しかし、素数の一覧を用意するのは面倒なので、$3$から$\sqrt{n}$までの奇数で割り切れるかを確認していく。
そして、もし割り切れる場合は$n$を割り、割った数を覚えておく。
n = 600851475143
i = 3
ans = 0
while(i^2<n){
while(n%%i==0){
n = n / i
ans = i
}
i = i + 2
}
ans = max(ans, n)
print(ans)
Problem 4 「最大の回文積」
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
3桁の数の積は、$1000*1000$個くらいなので、ベクトルで一気に処理する。
$v = 100\sim999$の列ベクトルとすると、
$v \cdot {v}^{\mathrm{T}}$で重複はあるが全パターンを作ることができる。
あとは、その中から最大の回文数を見つければ良い。
v = 100:999
v = as.character(unique(c(v %*% t(v))))
r = unlist(lapply(lapply(strsplit(v, ""), rev), paste, collapse=""))
ans = max(as.integer(v[v==r]))
print(ans)
Problem 5 「最小の倍数」
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
$1$から$10$の最小公倍数は、$$2^3 \times 3^2 \times 5 \times 7 = 2520 $$で求まる。
ここで、$2, 3, 5, 7$は$10$以下の素数である。
そして、それぞれ$10$を超えない範囲で累乗する。
つまり、例えば$2$に対しては、
\begin{align}
2^3 &= 8 < 10 \\
2^4 &= 16 > 10
\end{align}
なので、$2$の指数は$3$である。
ある整数$N$以下の素数を列挙するには、エラトステネスの篩を使えば良い。
ある素数$p$とある整数$N$に対して、$p^n \leq N$を満たす整数$n$の最大値は、$$n = \mathrm{floor}\left(\frac{\log{N}}{\log{p}}\right)$$で求まる。
getprimes = function(limit){
p = rep(TRUE, limit)
p[1] = FALSE
for(i in c(2, seq(3, sqrt(limit), 2)))
if(p[i])
p[seq(i*2, limit, i)] = FALSE
return(as.numeric(which(p)))
}
limit = 20
p = getprimes(limit)
ans = prod(p^(log(limit)%/%log(p)))
print(ans)
Problem 6 「二乗和の差」
最初の$10$個の自然数について, その二乗の和は,$$ 1^2 + 2^2 + ... + 10^2 = 385 $$最初の$10$個の自然数について, その和の二乗は,$$(1 + 2 + ... + 10)^2 = 3025$$これらの数の差は $3025 - 385 = 2640$ となる.
同様にして, 最初の$100$個の自然数について二乗の和と和の二乗の差を求めよ.
$100$個の自然数くらいであれば一気にベクトルで計算すれば良い。
少し工夫してみる。最初の$n$個の自然数の二乗の和は、$$\frac{n(n+1)(2n+1)}{6}$$であり、和の二乗は、$$\frac{n^2(n+1)^2}{4}$$なので求めたいその差は、
\begin{align}
&\frac{n^2(n+1)^2}{4}-\frac{n(n+1)(2n+1)}{6} \\
= &\frac{n(n-1)(n+1)(3n+2)}{12}
\end{align}
と表せる。
v = 1:100
ans = sum(v)^2-sum(v^2)
print(ans)
Problem 7 「10001番目の素数」
素数を小さい方から6つ並べると$2, 3, 5, 7, 11, 13$であり, $6$番目の素数は$13$である.
$10001$番目の素数を求めよ.
$n$番目の素数を$p_n$とすると、$n\geq6$に対して、
$$p_n \leq n(\log n + \log (\log n ))$$が成り立つ。
$n=10001$のとき、$p_n \leq 114319.2$となる。
この値より小さい範囲でエラトステネスの篩を使い素数を列挙し$10001$番目の素数を探す。
ちなみに、$114319.2$以下の素数は$10818$個あった。
getprimes = function(limit){
p = rep(TRUE, limit)
p[1] = FALSE
for(i in c(2, seq(3, sqrt(limit), 2)))
if(p[i])
p[seq(i*2, limit, i)] = FALSE
return(as.numeric(which(p)))
}
n = 10001
limit = ceiling(n*(log(n) + log(log(n))))
p = getprimes(limit)
ans = p[n]
print(ans)
Problem 8 「数字列中の最大の積」
次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で, 最大となる値は, 9 × 9 × 8 × 9 = 5832である.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
この1000桁の数字から13個の連続する数字を取り出して, それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.
EX 6桁の数123789から5個の連続する数字を取り出す場合, 1*2*3*7*8と2*3*7*8*9の二通りとなり, 後者の2*3*7*8*9=3024が最大の総乗となる.
Rのembedという関数を使う。
> embed(1:10, 3)
[,1] [,2] [,3]
[1,] 3 2 1
[2,] 4 3 2
[3,] 5 4 3
[4,] 6 5 4
[5,] 7 6 5
[6,] 8 7 6
[7,] 9 8 7
[8,] 10 9 8
このようにベクトルと次元を入力すると、スライドさせた行列を作ってくれる。
あとは、各行で総乗し、最大値を探せば良い。
v = "73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"
v = as.numeric(strsplit(gsub("\n", "", v), "")[[1]])
ans = max(apply(embed(v, 13), 1, prod))
print(ans)
Problem 9 「特別なピタゴラス数」
ピタゴラス数(ピタゴラスの定理を満たす自然数)とは$a < b < c$で以下の式を満たす数の組である.$$a^2 + b^2 = c^2$$
例えば,$3^2 + 4^2 = 9 + 16 = 25 = 5^2$である.
$a + b + c = 1000$となるピタゴラスの三つ組が一つだけ存在する.
これらの積$abc$を計算しなさい.
$a+b+c = 1000$という条件から、
$c = 1000-a-b$を$a^2+b^2=c^2$に代入して整理すると、
\begin{align}
a^2+b^2=&(1000-a-b)^2 \\
=&1000^2+a^2+b^2 -2 \cdot 1000a -2 \cdot 1000b + 2ab
\end{align}
となる。これを$b$について解き、
$$b=\frac{1000(1000-2a)}{2(1000-a)}$$
これが整数となれば良い。
$a<b<c$とすると、
$$1000=a+b+c>3a$$より、$a<1000/3$となるので、この範囲内で探す。
p = 1000
a = 3:((p/3)-1)
a = a[(p*(p-2*a))%%(2*(p-a))==0]
b = (p*(p-2*a))/(2*(p-a))
c = p - a - b
ans = a * b * c
print(ans)
Problem 10 「素数の和」
10以下の素数の和は$2 + 3 + 5 + 7 = 17$である.
200万以下の全ての素数の和を求めよ.
Problem 5 や Problem 7 で使用したエラトステネスの篩を使えば簡単に求まる。
getprimes = function(limit){
p = rep(TRUE, limit)
p[1] = FALSE
for(i in c(2, seq(3, sqrt(limit), 2)))
if(p[i])
p[seq(i*2, limit, i)] = FALSE
return(as.numeric(which(p)))
}
limit = 2000000
p = getprimes(limit)
ans = sum(p)
print(ans)