Project Euler
No.76 Counting Summations問題.5は正整数の和として:\begin{align*} &4+1\\ &3+2\\ &3+1+1\\ &2+2+1\\ &2+1+1+1\\ &1+1+1+1+1 \end{align*}の6通りに書ける．では，100は正整数の和として何通りに書けるか． 考え方とプログラム例.(c++)動的計画法です．先…
No.77 Prime Summations問題.10は素数の和として:\begin{align*} &7+3\\ &5+5\\ &5+3+2\\ &3+3+2+2\\ &2+2+2+2+2 \end{align*}の5通りに書ける．では，素数の和として5000通り以上の方法で書くことのできる最小の数は何か． 考え方とプログラム例.(c++)答え…
方程式1/a+1/b=p/10最近数カ月ぶりに Project Euler の問題を解いていると，面白い問題があったのでその例題を紹介します．実際の Project Euler の問題については別の記事で書くことにします． 問題．方程式\begin{align}\frac{1}{a}+\frac{1}{b}=\frac{p}{…
No.30 Digit fifth powers問題.驚いたことに, 自身の各桁の数字の 4 乗和として書ける数は 3 つしかない:\begin{align*} 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 \end{align*}ここで, は含めていない.これらの数の和…
No.15 Lattice Paths問題. の格子の左上の角から始めて, 右か下への移動のみ可能であるとき, 右下の角へ移動する道は 6 通りある.では, の格子では何通りあるか求めよ. 考え方とプログラム例(Python3).の格子において左上から右下まで, 右または下への移動の…
No.12 Highly divisible triangular number問題.Q. 三角数 とは, 1 からの連続した自然数の和で表される数です. 例えば 7 番目の三角数は,\begin{align*} 1+2+3+4+5+6+7 = 28 \end{align*}で, 7 番目までの三角数の正の約数は, 以下のようになります.1: 13: …
No.10 Summation of primes問題.Q. 10 未満の素数の和は,\begin{align*} 2+3+5+7 = 17 \end{align*}です. では, 2,000,000 未満の素数の和はいくつになるか. 考え方とプログラム例(Python)実際に 2,000,000 未満の素数を 「エラトステネスの篩」 を用いて求…
No.8 Largest product in a series問題.Q. 下の1000桁の数の中で, 隣り合った4桁の積として最大のものは です.73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 8586156078911294949545950173795833…
No.6 Sum square difference問題.Q. 1から10までの平方の和は,1から10までの和の平方は,で, その差は になります.では, 1から100までの平方の和と和の平方の差はいくつになるか. 考え方とプログラム例(python)この問題は単純に計算すれば良さそうです.LIST …
No.7 10001st prime問題.Q. はじめの6つの素数は 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 です.では, 10001番目の素数は何か. 考え方とプログラム例(Python)1. 小さい数から順に素数かどうかを確かめていく素数の定義通りに, 自分よりも小さい数で割り…
No.5 Smallest multiple問題.Q. 2520 は, 1 から 10 のすべてで割り切れる最小の数です.では, 1 から 20 のすべてで割り切れる最小の数はいくつか. 要は 1 から 20 までの数の最小公倍数を求める問題です. 考え方とプログラム例(c++)1. 1から順に最小公倍数…
No.4 Largest palindrome product問題.Q. 回文数(palindrome number) とは, 左右どちらから読んでも同じになる数です. (例えば, 12021 や, 148841)2桁の数2つの積として表される最大の回文数は, です.3桁の数2つの積として表される最大の回文数はいくらか. …
No.2 Even Fibonacci numbers問題.Q. 直前の2項の和を次の項として生成されるフィボナッチ数列において, 1, 2, から始めたときの最初の10項は次のようになる.\begin{align*} 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots \end{align*}この数列の4,000,000未満…
No.3 Largest prime factor問題.Q. 13195 の素因数は, 5, 7, 13, 29 です. ().では, 600851475143 の素因数で最大のものはなにか? 考え方とプログラム例(Python3)1. 小さい数で順に割っていく与えられた 600851475143 を, で順に割っていき, 最後に割った商…
Project Euler とはProjectEuler とは, プログラミングの問題集です.各問題は数字で答える形になっています. さらに, 各問題をそのままコーディングするのでなく, 問題を数学的に解析して, 上手なアルゴリズムを考える必要がある問題がほとんどです. アカウ…
No.1 Multiples of 3 and 5問題.Q. 10 未満で, 3 または 5 の倍数は 3, 5, 6, 9 の 4 つで, それらの総和は 23 となる.では, 1,000 未満で 3 または 5 の倍数であるものの総和はいくらか. 考え方とプログラム例(c++/Python3)1. シンプルにループで和を求める…
