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

ペル方程式

ペル方程式(Pell's equation)は、フェルマーが問題を数学者たちに送りつけたという逸話が有名ですが、オイラーも研究してこのように(誤って)命名したそうです。 x2 - Dy2 = 1 Dは与えられた平方数でない自然数 この形の整数解を求める問題をペル方程式と…

Project Euler 43

Problem 43 1406357289という数は、0から9のpandigitalであるが、さらに興味深い部分に分割したときの性質を持ちます。 d1を最初の数字、d2を2番目の数字などとする。 d2d3d4=406は2で割り切れる。 d3d4d5=063は3で割り切れる。 d4d5d6=635は5で割り切れる。…

Project Euler 41

Problem 41 1からnまでの数字が全て1回ずつ使われているn桁の数をpandigitalと呼ぼう。例えば、2143は4桁のpandigitalでまた素数でもある。 最も大きいn桁のpandigitalで素数である数は? http://projecteuler.net/index.php?section=problems&id=41 pandigi…

Project Euler 40(2)

本当は文字をいちいちカウントする必要はありません。例えば、d1000を求めてみましょう。 1桁の数は1〜9だから、9までで9桁です。2桁の数は10〜99の90個あるので、99までで9+180=189桁です。3桁の数は100〜999の900個あるので、999までで9+180+2700=2889桁で…

Project Euler 40(1)

Problem 40 無理数を次のように正の整数を結合して作る: 0.123456789101112131415161718192021... 小数部の12番目の数字は1である。 dn を小数部のn番目の数字としたとき、次の値を求めよ。 d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 http://…

Project Euler 270

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=270 今日は久しぶりに出題の時間に家にいた。 適当に組んでいたら、そのうちにこれは重複が生じないように再帰にする問題だと気がついた。昼食のおかずを買いに出かけていると…

Project Eulerに必要な用語集

Project Eulerを解いていくのに便利な数学の用語やアルゴリズムなどを紹介したものをまとめています。 ユークリッドの互除法 互いに素 エラトステネスのふるい 包除原理 ピタゴラス数 バイナリ法 漸化式 約数 多角数 完全数・友愛数・社交数 オイラーのφ関数…

Project Euler 39

Problem 39 pを直角三角形の周囲の長さとすると、p = 120の解は3つある。 (中略)p ≤ 1000に対して、解の個数が最大のものは? http://projecteuler.net/index.php?section=problems&id=39 ピタゴラス数は、 a = 2lmn b = l(m2 - n2) c = l(m2 + n2) m > n …

Project Euler 38

Problem 38 192という数に1,2,3をかけると、 192 x 1 = 192 192 x 2 = 384 192 x 3 = 576 これをつなげると192384576という1から9の数字が一度ずつ使われる数になる。192384576を192と(1,2,3)の結合した積と呼ぶ。 (中略)整数と(1,2,...,n)(n > 1)の結合し…

Project Euler 2

フィボナッチ数列を作らなければならない。Haskellではどのように作ればいいか検索していたら、次のようなものが出てきた。 fib = 1 : 1 : [ a + b | (a, b) http://www.sampou.org/haskell/tutorial-j/functions.html さっぱり意味がわからないが、一つずつ…

Project Euler 269

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=269 見かけがいかにも数学的なので最初はそういう方向で考えていたが、そのうちこれはコーディングの問題だと気がついた。突飛な発想はまったく要らず、地道に考えながらコーデ…

Project Euler 37

Problem 37 3797という数は興味深い性質を持っている。それ自身が素数で、左から順に数字を取り除いていっても素数のままである:3797,797,97,7。同様に右から順に取り除いても素数である:3797,379,37,3。 11個あるこのようにどちらからでも短くできる素数…

Project Euler 36

Problem 36 (中略)10進でも2進でも回文になる100万より小さい数の和を求めよ。 http://projecteuler.net/index.php?section=problems&id=36 どちらかの進数で回文数を生成して、それがもう一方の進数で回文になっているかを判定すればよいです。100万まで…

回文数

Project Eulerでよく出てくる回文数(palindromic number)は、32523のようにどちらから読んでも同じになる整数のことです。 回文数の生成 まず思いつくのは、例えば4桁なら10〜99を用意してそれをひっくり返して結合するという方法です。10なら01と結合して…

Project Euler 1

急にHaskellをやってみようと思い、インストールして、少し調べて、Project EulerのProblem 1を書いてみた。2時間かかった。 まず、 http://haskell.org/ からダウンロードして、デフォルトでインストール。 そして、適当なサイトを見て、こう書いて、test.h…

Project Euler 35(2)

前回のコードでは、197,971,719の素数判定を3回ずつしていることになります。これを避けるには、この3つの中で最も小さい数、すなわちここでは197のみ回転して素数判定をすればよいでしょう。 しかし、回転して最も小さい数だけを生成するのはかなり面倒です…

Project Euler 268

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=268Problem 1と似たような問題の拡張。でも4以上だから包除原理を拡張しないといけないんだが、それに手間取った。これって常識なの? 範囲が小さいときに有効なコード。 def m…

Project Euler 35(1)

Problem 35 197は、数字を回転させた197と971と719がすべて素数なので、circular primeと呼ばれる。 (中略)100万未満にcircular primeはいくつあるか? http://projecteuler.net/index.php?section=problems&id=35 エラトステネスのふるいを行って、2から1…

Project Euler 32(2)

見方を変えて、まず、左辺第2項を固定します。そうすると第1項の範囲が絞れます。例えば、第2項が2だったら、第1項は1000〜4999であることがわかります。そして掛け算をして、数字が1回ずつ使われているかをチェックします。 コードによる速度の違いをチェッ…

Project Euler 32(1)

Problem 32 積7254は、39 x 186 = 7254と書くと1〜9をちょうど1回ずつ使うという意味で特別である。同様の積の和を求めよ。 http://projecteuler.net/index.php?section=problems&id=32 普通に解くと、1〜9の順列を出して、例えば、(1, 8, 6, 3, 9, 7, 2, 5,…

Project Euler 30

Problem 30 驚くべきことに各桁の4乗の和として書ける数は3つしかありません(中略) 1 = 14は和でないので除きます。 (中略)各桁の5乗和として書ける全ての数の和を求めよ。 http://projecteuler.net/index.php?section=problems&id=30 まず、範囲を抑え…

Project Euler 29(4)

この問題は、べき乗数を列挙する、重複する数を数える、という2段階に分かれています。今まで前段は後段にくらべて時間がかからなかったのですが、後段が速くなって前段のほうが時間がかかるようになったので前段を改良します。 例えば100までのべき乗数を考…

第4回愛知県市町村対抗駅伝競走大会

http://www.tokai-tv.com/ekiden09/昨夜と今朝にわけて見た。 スーパー小学生出現だそうで。松原亜純、小学2年生。1500mを5:30。私でもちゃんと練習しないと出せないタイムだ。やっぱり体格がいいね。 親子揃って表情が硬いよ!(ごめんなさい) 途中から雨…

30kmビルドアップ

駅伝とか見ちゃうとついスピード練習をしたくなるが、そういうのは無視して予定通り30km走を敢行。 最初名駅まで走ろうとしたが、風が強いのでやめて、名駅へ。 新幹線口からまったり走る。最初は線路沿いに、R19、R1と走る。 国道だと距離が分かるので、ペ…

Project Euler 267(2)

問題読み違えてた。なんかしらんけど、fは場面で最適なものを選べるのかと思ってた。それでなんとか答えを出してみたものの、答えが合わないので問題を読み直してみたら。 これって、ただの高校数学じゃん。

Project Euler 29(3)

例えば、16は161/4=2と161/2=4と163/4=8に底を移行できます。20までとして16が移行できる指数はそれぞれ、 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1/4 o o o o x x x x x x x x x x x x x x x 1/2 o o o o o o o o o x x x x x x x x x x 3/4 x …

Project Euler 267

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=267ダメだ、計算量が膨大すぎる。

Project Euler 29(2)

ab(2 ≤ a ≤ 100, 2 ≤ b ≤ 100)は99×99個あるのですが、同じ数になるものがあるので問題になっているのです。例えば、 42 = 24 これらを99×99から取り除けばよいです。 ここでは、底が小さくなれるものを数えます。上の例なら、 42 = (22)2 = 24 すなわち、…

Project Euler 29(1)

Problem 29 (略)ab 2 ≤ a ≤ 100, 2 ≤ b ≤ 100で生成される数列で異なる項はいくつあるか。 http://projecteuler.net/index.php?section=problems&id=29 Pythonなら100100も簡単に計算できるので、そのまま書けば答えは出てきます。 from itertools import …

2009名古屋シティマラソン結果(2)

https://runnet.jp/record/userRaceTopShowAction.do?raceId=8673前回の抽出データで前半と後半のタイムの相関を調べてみた。こうして見てみると、人それぞれなんだなあと思う。 2本の線は、回帰線に平行にデータが1/3ずつに分かれるように引いてある。左上…