数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

Project Euler

方程式 1/a+1/b=p/10

方程式1/a+1/b=p/10最近数カ月ぶりに Project Euler の問題を解いていると,面白い問題があったのでその例題を紹介します.実際の Project Euler の問題については別の記事で書くことにします. 問題.方程式\begin{align}\frac{1}{a}+\frac{1}{b}=\frac{p}{…

プロジェクトオイラー157. ~ Solving the Diophantine equation 1/a+1/b=p/10^n ~

No.157 Solving the Diophantine equation 1/a+1/b=p/10^n前回の記事で という問題について書きました(→方程式 1/a+1/b=p/10).今回の問題はさらに右辺の分母が になったことで少し難しくなっています. 問題. を正の整数, として,ディオファントス方程式 …

プロジェクトオイラー389. ~ Platonic Dice ~

No. 389 Platonic DiceProject Euler です.前に一度あきらめていた問題がようやく解けたので,書きます.確率の問題です.問題.偏りのない4面のサイコロ1個を投げて,出た目を として記録する. 個の偏りのない6面のサイコロを投げて,出た目を足し合わせ…

プロジェクトオイラー555. ~ McCarthy 91 function ~

No.555 McCarthy 91 function.プロジェクトオイラーの555番です.とりあえず問題を見てみましょう. 問題. マッカーシーの91関数は以下のように定義される. \begin{align*} M_{91}(n) &= \left\{\begin{array}{ll}n-10 & \mathrm{if}\,n>100\\ M_{91}(M_{9…

プロジェクトオイラー104. ~ Pandigital Fibonacci ends ~

No. 104 Pandigital Fibonacci ends問題.フィボナッチ数列とは次の漸化式によって定義される数列です:\begin{align*} F_n &= F_{n-1} + F_{n-2}\\ F_1 &= 1\\ F_2 &= 1. \end{align*}113 桁の数である は末尾の 9 桁が 1 から 9 の並べ替えになっているよ…

プロジェクトオイラー613. ~ Pythagorean Ant ~

No. 613 Pythagorean Ant問題.Dave はバルコニーで宿題をしていて,ピタゴラスの直角三角形についての発表の準備でちょうど辺の長さが 30cm, 40cm, 50cm の三角形を切り取ったとき,強い風が吹いてその三角形は庭へ飛んでいきました.さらに風が吹いて,小…

プロジェクトオイラー343. ~ Fractional Sequences ~

No.343 Fractional Sequences問題.任意の正の整数 に対して,分数 で表される数 の有限列を次のように定義する:(但し最も簡単な形に約分する.) がなんらかの整数になったとき,数列の終わりとする.(つまり, のとき.) と定義する. 例えば, のときなの…

プロジェクトオイラー628. ~ Open chess positoins ~

No.628 Open chess positions問題.与えられたサイズのチェス盤の上にチェスの駒を配置することを考える. 以下では, のチェス盤において, 各行, 各列に 1 つだけあるような, 個のポーンの配置を考える. ルークが盤の左下隅のマスから右上隅のマスまで, 縦, 横…

プロジェクトオイラー30. ~ Digit fifth powers ~

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*}ここで, は含めていない.これらの数の和…

プロジェクトオイラー15. ~ Lattice Paths ~

No.15 Lattice Paths問題. の格子の左上の角から始めて, 右か下への移動のみ可能であるとき, 右下の角へ移動する道は 6 通りある.では, の格子では何通りあるか求めよ. 考え方とプログラム例(Python3).の格子において左上から右下まで, 右または下への移動の…

プロジェクトオイラー601. ~ Divisibility streaks ~

No.601 Divisibility streaks問題.正の数 に対して, が で割り切れないような最小の整数 をもって関数 と定義しよう.例えば:13 は 1 で割り切れる14 は 2 で割り切れる15 は 3 で割り切れる16 は 4 で割り切れる17 は 5 で割り切れないよって, .同様に,120 …

プロジェクトオイラー602. ~ Product of Head Counts ~

No.602 Product of Head Counts問題.Q. アリスは友達に手伝ってもらって, 正しくない(表裏の出る確率が等しくない)コインを使ってランダムな数を生成する. 彼女らは円形に座って, アリスから順番にコインを投げる. それぞれの人は自分が表を出した回数を覚え…

プロジェクトオイラー426. ~ Box-ball system ~

No.426 Box-ball system問題.(ProjectEuler426. より)Q. 無限に並んだ箱を考える. いくつかの箱には玉が入っている. 例えば, 2個連続して玉の入った箱, それに続いて2個の空き箱, 2個の玉の入った箱, 1個の空き箱, 2個の玉の入った箱が並んだ初期配置につい…

プロジェクトオイラー190. ~ Maximising a weighted product ~

No.190 Maximising a weighted product以前の記事「自作問題22」でも紹介した, 条件付きの関数の極値の必要条件の定理が使える問題があったので紹介します.問題.Q.\begin{align*} S_m = (x_1, x_2, \ldots, x_m) \end{align*}は 個の正の実数の組で,\begin{…

プロジェクトオイラー12. ~ Highly divisible triangular number ~

No.12 Highly divisible triangular number問題.Q. 三角数 とは, 1 からの連続した自然数の和で表される数です. 例えば 7 番目の三角数は,\begin{align*} 1+2+3+4+5+6+7 = 28 \end{align*}で, 7 番目までの三角数の正の約数は, 以下のようになります.1: 13: …

プロジェクトオイラー10. ~ Summation of primes ~

No.10 Summation of primes問題.Q. 10 未満の素数の和は,\begin{align*} 2+3+5+7 = 17 \end{align*}です. では, 2,000,000 未満の素数の和はいくつになるか. 考え方とプログラム例(Python)実際に 2,000,000 未満の素数を 「エラトステネスの篩」 を用いて求…

プロジェクトオイラー8. ~ Largest product in a series ~

No.8 Largest product in a series問題.Q. 下の1000桁の数の中で, 隣り合った4桁の積として最大のものは です.73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 8586156078911294949545950173795833…

プロジェクトオイラー6. ~ Sum square difference ~

No.6 Sum square difference問題.Q. 1から10までの平方の和は,1から10までの和の平方は,で, その差は になります.では, 1から100までの平方の和と和の平方の差はいくつになるか. 考え方とプログラム例(python)この問題は単純に計算すれば良さそうです.LIST …

プロジェクトオイラー7. ~ 10001st prime ~

No.7 10001st prime問題.Q. はじめの6つの素数は 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 です.では, 10001番目の素数は何か. 考え方とプログラム例(Python)1. 小さい数から順に素数かどうかを確かめていく素数の定義通りに, 自分よりも小さい数で割り…

プロジェクトオイラー5. ~ Smallest multiple ~

No.5 Smallest multiple問題.Q. 2520 は, 1 から 10 のすべてで割り切れる最小の数です.では, 1 から 20 のすべてで割り切れる最小の数はいくつか. 要は 1 から 20 までの数の最小公倍数を求める問題です. 考え方とプログラム例(c++)1. 1から順に最小公倍数…

プロジェクトオイラー4. ~ Largest palindrome product ~

No.4 Largest palindrome product問題.Q. 回文数(palindrome number) とは, 左右どちらから読んでも同じになる数です. (例えば, 12021 や, 148841)2桁の数2つの積として表される最大の回文数は, です.3桁の数2つの積として表される最大の回文数はいくらか. …

プロジェクトオイラー2. ~ Even Fibonacci numbers ~

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未満…

プロジェクトオイラー3. ~ Largest prime factor ~

No.3 Largest prime factor問題.Q. 13195 の素因数は, 5, 7, 13, 29 です. ().では, 600851475143 の素因数で最大のものはなにか? 考え方とプログラム例(Python3)1. 小さい数で順に割っていく与えられた 600851475143 を, で順に割っていき, 最後に割った商…

ProjectEuler はじめました

Project Euler とはProjectEuler とは, プログラミングの問題集です.各問題は数字で答える形になっています. さらに, 各問題をそのままコーディングするのでなく, 問題を数学的に解析して, 上手なアルゴリズムを考える必要がある問題がほとんどです. アカウ…

プロジェクトオイラー1. ~ Multiples of 3 and 5 ~

No.1 Multiples of 3 and 5問題.Q. 10 未満で, 3 または 5 の倍数は 3, 5, 6, 9 の 4 つで, それらの総和は 23 となる.では, 1,000 未満で 3 または 5 の倍数であるものの総和はいくらか. 考え方とプログラム例(c++/Python3)1. シンプルにループで和を求める…