2009-06-01から1ヶ月間の記事一覧

Project Euler 204

プロジェクトオイラー http://projecteuler.net/index.php Q204. 100以下の素因数のみ持つ109以下の自然数の個数。 ただ素数で割って、再帰を使うだけ。2で割った数の同様の個数と、3で割った数の同様の個数(ただし、3以上しか因数に使えない)と、...、97…

Project Euler 203

プロジェクトオイラー http://projecteuler.net/index.php Q203. パスカルの三角形の最初の51列で自乗の因子を含まない異なる自然数の和。 どうやっても解けるような気がする。 素因数分解はあまりやりたくないので、あらかじめ1〜50の素因数分解を行い、そ…

Project Euler 202

プロジェクトオイラー http://projecteuler.net/index.php Q202. 正三角形状に鏡を配置する。頂点をA,B,Cとする。その頂点には無限小の隙間があり、Cからレーザーが入って反射する。12017639147回レーザーが反射して再びCから出る入射法は何通りあるか。 よ…

Project Euler Level 5

Nice work, inamori, you've just advanced another level というわけで、今日やっと200問解いてレベル5に上がった。2ヶ月以上かかった。 これを機に、統計を少し調べてみた。まずは、国別の参加者数(100人以上)。 1. USA 8517 2. England 1683 3. Germany…

Project Euler 201

プロジェクトオイラー http://projecteuler.net/index.php Q201. S = {12, 22, ... , 1002}という集合を考える。この部分集合で要素数が50のものの和を全て列挙したとき、重複しない和の集合をU(S,50)とする。この集合の要素の和を求めよ。 要素数1の部分集…

Project Euler 200

プロジェクトオイラー http://projecteuler.net/index.php Q200. p2q3(pとqは異なる素数)をsqubeと呼ぶことにする。また、200のようにどの一つの桁の数字を変えても素数にならない数をprime-proofと呼ぶことにする。prime-proofであるsqubeで1992008のよう…

Project Euler 199

プロジェクトオイラー http://projecteuler.net/index.php Q199. 図のように3つの円に接するように円を描いていく。これを10回繰り返したとき、円で塗りつぶされていない領域の割合はいくらか? 互いに接する3つの円C1,C2,C3の半径をそれぞれr1,r2,r3、その…

Project Euler 198

プロジェクトオイラー http://projecteuler.net/index.php Q198. 9/40のように分母5以下で近似すると、1/4と1/5の2つ出てくることがある。1/100未満で、分母が108を超えないとき、そのような正数はいくつかるか。 恐らく6日間考えた。昨日になってようやく糸…

Project Euler 251

http://projecteuler.net/index.php?section=problems&id=251Cardanoというキーワードから分かるように、三次方程式の解法がらみで式は簡単になる。しかし、問題はそこから。実際、しらみつぶしでは非常に時間がかかる。一工夫して速くしたが、それでも30分…

Project Euler 197

プロジェクトオイラー http://projecteuler.net/index.php Q197. f (x) = [230.403243784-x2] × 10-9 とする。u0 = -1、un+1 = f (un)としたとき、un + un+1(n = 1012)を求めよ。 値域が狭いので、周期性を調べればよい。xは109倍して整数化すると考えやすい…

Project Euler 196

プロジェクトオイラー http://projecteuler.net/index.php Q196. 自然数を三角形状に並べる。3つの素数の組がそのうち1つを選ぶと残りの2つが隣(斜め含む)になっているときprime tripletと呼ぶことにする。S(n)をn列上の素数でprime tripletの要素の一つに…

Project Euler 195

プロジェクトオイラー http://projecteuler.net/index.php Q195. 辺の長さが整数で、1つだけ角度が60度で、内接円がr以下の三角形の個数をT(r)とする。T(1053779)を求めよ。 角度60度の頂点の対辺をc、他の辺をa, b(a > b)とすると、余弦定理から、 c2 = a2 …

Project Euler 194

プロジェクトオイラー http://projecteuler.net/index.php Q194. 省略 まず、単体のAとBの取りうる色のパターンの数を数えた。ここに時間がかかっているが、手抜きで特に工夫はしていない。グラフを作ってしらみつぶしに調べている。使う色の数ごとに求めて…

1.5km走

本当に久しぶりに1.5kmを走った。去年の8月以来かもしれない。 2:03.14 2:00.43 1:58.42 - 6:01.99この前書いた6分半ではなかったが、とにかく筋力が足りない。筋肉痛になりそう。これ以上はなかなか速く走れそうにない。

Project Euler 193

プロジェクトオイラー http://projecteuler.net/index.php Q193. 平方数で割り切れない250未満の自然数の個数。 割り切れるほうの個数を考える。n2で割り切れる自然数の集合の個数をSnとすると、なんらかの平方数で割り切れる自然数集合の個数Sは、和集合の…

Project Euler 192

プロジェクトオイラー http://projecteuler.net/index.php Q192. 1 < n ≤ 100000で平方数でないnに関して、√nの分母が1020の以下で最もよい近似になる分数を得る。そのときの分母の総和。 有理数による近似は連分数で表される。例えば、√2 = 1.41421356…なら…

Project Euler 191

プロジェクトオイラー http://projecteuler.net/index.php Q191. 3日続けて休むか、遅刻が2回あったら賞がもらえない。30日間で賞がもらえるパターンはいくつあるか。 n日間で今欠席が何回続いていて何回遅刻しているという状態で何通りあるかという数列に対…

Project Euler 190

プロジェクトオイラー http://projecteuler.net/index.php Q190. x1 + x2 + ... + xm = m のときに、Pm = x1x1x22 ... xmmの最大値を求める。ただし、xk > 0。このとき、∑[Pm] (2 ≤ m ≤ 15) を求めよ。 ラグランジュの未定乗数法を使う。

Project Euler 250

これもQ.249と同じ。

素数を列挙する

数学者が数学を「語る」ことの良さ - hiroyukikojimaの日記で紹介されていた、リーマン予想は解決するのか? ―絶対数学の戦略―作者: 黒川信重,小島寛之出版社/メーカー: 青土社発売日: 2009/06/01メディア: 単行本購入: 31人 クリック: 614回この商品を含むブ…

Project Euler 189

プロジェクトオイラー http://projecteuler.net/index.php Q189. 辺の長さ8の正三角形を、辺の長さ1の小正三角形にわける。それを隣が同じ色にならないように赤・青・緑の3色で塗り分ける。塗り分け方は何通りあるか。 辺の長さ7の正三角形の有効な塗り分け…

Project Euler 249

http://projecteuler.net/index.php?section=problems&id=249昨日新たに出ていた問題をチラッと見て、昨日の夜寝ながら考えたら簡単にアルゴリズムを思いついた。次に書く問題と同じ手法。今朝起きてささっと書いたら一発で答えがあった。メモリを食いすぎで…

10km走

2ヶ月ぶりに10km走った。暑かったが、多少風があったのでよかった。割と気分よく走ることが出来た。10km換算で1時間3分か。最初に10km走ったときもこんなもんだった。あのときはペースがわからないのでなるべくゆっくり走った。そうすると股関節が痛くなる。…

Project Euler 188

プロジェクトオイラー http://projecteuler.net/index.php Q188. a↑↑bを次のように再帰的に定義する。 a↑↑(k+1) = a(a↑↑k) このとき、1777↑↑1855の下8桁を求めよ。 オイラーの定理より、 1777φ(108) ≡ 1(mod 108) φ(108) = 4×107より、17774×107 ≡ 1(mod 108…

Project Euler 187

プロジェクトオイラー http://projecteuler.net/index.php Q187. 1億より小さい2つの素数の積で表される数の個数。 まず、1万までの素数を求める。そこまでの素数の積で表される個数はすぐにわかる。一方の素数が1万以上の数の個数を求めるために、5000万未…

Project Euler 186

プロジェクトオイラー http://projecteuler.net/index.php Q186. 100万人いて、与えられた疑似乱数で電話をかける人とかけられる人を決める。かけた人とかけられた人は友達であるとする。この作業を繰り返し、首相の友達、友達の友達、、、が100万人の99%以…

Project Euler 185

プロジェクトオイラー http://projecteuler.net/index.php Q185. 省略 あれこれ考えて分からなかったので、焼きなまし法を使ってみた。ある整数のエネルギーを各整数のcorrectの真値との差の平方の総和として、エネルギー最小問題とした。しかし、これは大雑…

Project Euler 184

プロジェクトオイラー http://projecteuler.net/index.php Q184. 中心が原点、半径rの円の内側(周上は含まない)の格子点からなる三角形で原点を内部に含むものの個数をIrとする。I105を求めよ。 対称性を考えると、三角形の点の位置は次の5種類に分類され…

Project Euler 182

プロジェクトオイラー http://projecteuler.net/index.php Q182. p = 1009、q = 3643のとき、n = pq、φ(n) = (p - 1)(q - 1)として、1 < e < φ(n)かつ(e, φ(n)) = 1のeについて、me ≡ m(mod n)となる0 ≤ m < nのmの個数を得たとき、最小のmの個数を持つeの総…

Project Euler 183

プロジェクトオイラー http://projecteuler.net/index.php Q183. 自然数Nに対して、自然数kを変化させて、(N/k)^kの最大値を求める。このとき、D(N)は、この最大値が無限小数ならN、有限小数なら-Nを返す。D(5) + ... + D(10000)を求めよ。 特になんのひねり…