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

Project Euler 266(2)

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=266Pythonだととにかくメモリを食う。400MB近く。大きな掛け算を避けるためlogを取るので、それを戻すためにどの素数を使ったのか整数で保持しておく必要がある。その実数と整…

Project Euler 26

Problem 26 (略)1/dが10進で最も長い循環になるd < 1000を求めよ。 http://projecteuler.net/index.php?section=problems&id=26 例えば、 1/7 = 0.142857142857… 循環長は6となります。 これは割り算を進めていけばわかります。10を7で割ると余り3、30を7…

Project Euler 266(1)

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=266風呂入ってまったりしているときに、やっと思いついた。 これ、思いつけるかどうかだけだ。 Pythonだと、メモリ的には限界に近い。

かりやランナーズ マラソン・ジョギング大会

最近すっかり足が遅くなってしまったが、名古屋シティも終わったし、いつも1月中旬にあるこの大会に向けてスピード練習をしないといけないと思い、ウェーブスタジアムへ。1000mを5本、なんとか最後だけ4分を切った。1000mを4分切るペースで走ること自体が久…

オイラーの定理

無数に定理を残したオイラーですが、数学で単に「オイラーの定理」というと、 aφ(n) ≡ 1 (mod n) aとnは互いに素 のことを言います。φ(n)はオイラーのφ関数です。 nが素数の場合、フェルマーの小定理になります。 an-1 ≡ 1 (mod n) 証明は適当なものを参照し…

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

ランネットに結果が出ていた。 https://runnet.jp/record/userRaceTopShowAction.do?raceId=8673 5kmごとのタイムってどこに使われるんだろうと思っていたら、ここにあったか。 Start 00:01:10 5km 00:25:45 0:24:35 10km 00:48:59 0:23:14 15km 01:11:33 0:…

オイラーのφ関数

Project Eulerでは、"Euler's totient function"と呼ばれています。 φ(n)は、n以下のnと互いに素な自然数の個数を表します。 例えばφ(6)は、1と5が互いに素なので、2となります。 もうちょっと系統立てて考えてみましょう。6と互いに素であるというのは、2の…

Project Euler 265(4)

昨日の夜、眠れないので考えていたら、(2)の方法は一般的であることに気がついた。 N=6で考えて、単独の0は、 101xxxで、xは任意だから、0は8つ以上あることになる。同様に、00は4つ以上などとなる。 N × 1 + (N - 2) × 1 + (N - 3) × 2 + ... + 1 × 2N-3 …

2009名古屋シティマラソン

Eブロック最後方からのスタート。去年よりはスタートラインに到着するのが早かった。競技場内はやっぱりどうしようもない。道路に出ても、道幅の間でどこが進んでいるか探している。1kmの表示を見落とした。2kmが10:24か。去年とあまり変わらない。 3kmくら…

5km走

上の問題を考えながらゆっくり走った。寒くて小雨が降っていたが、今日走っておかないと明日体が動かないような気がして。最後の1kmだけ速く、流し2本入れた。 明日は名古屋シティ。 しかし、どうもやる気が。去年のタイムを書いておいたのに、Fブロック中E…

Project Euler 265(2)

最初Pythonで10分以上かかっていたので、高速化を考えてみた。 列挙する候補の数には、以下の条件がある。 1. 000001で始まる。 2. 1で終わる。 3. 0と1は同数、すなわち16個ずつある。1と2でこうなる。 N = 5 M = 2 ** N L = 2 ** (M - N) def gen_number()…

Project Euler 265(3)

湯船につかって考えていたらすぐに思いついた。これこそ「逆から考える」だ。すなわち、数が題意を満たすかを調べるのではなく、題意を満たす数を作る。 題意を満たす数は、頭5桁は00000で、一つずらして00001となる。その次は、00010または00011となる。そ…

素数の魔力に囚われた人々〜リーマン予想天才たちの150年の闘い

この間の放送の完全版? ガウスが素数定理を予想したところで、ガウスが素数の計算をしたように言ってたと思うが、ガウスは素数表を見て数えたんじゃなかったっけ?あとで確認してみる。

Project Euler 265(1)

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=265完全に出遅れて、問題文を見たときには40人以上の正答者が。しかも、なかなか問題の意味がわからなかった。 とりあえず、しらみつぶしで答えだけだしておいた。 60番目くら…

Project Euler 14

Problem 14 (略)(コラッツの問題で)最も長い数列を作る100万より小さい最初の数は? http://projecteuler.net/index.php?section=problems&id=14 「コラッツの問題」は「角谷の予想」とも言われます。 適当な自然数を選んで、偶数なら2で割り、奇数なら3…

Project Euler 12

Problem 12 (略)約数の個数が500を超えるはじめての三角数を求めよ。 http://projecteuler.net/index.php?section=problems&id=12 約数の個数は、素因数分解をすれば簡単に求められますが、個別に素因数分解していては非常に遅くなります。エラトステネス…

Project Euler 21

Problem 21 (略)10000より小さいすべての友愛数の和を求めよ。 http://projecteuler.net/index.php?section=problems&id=21 10000より小さい自然数に対し、素因数分解をし約数の和を求める処理を2回繰り返せば友愛数かの判定ができます。 from itertools i…

Project Euler 264(2)

色々計算してみたが、何も出てこなかった。 結局、C++で強引にメモリにだけ注意して計算した。 たぶん19番目。もう3日経とうとしているのに。 (追記) 垂心の性質ね。計算してみたら確かにそうなる。そういえばそんなのがあったような気がする。こういうの…

2009トヨカワシティマラソン

家から1時間あまり、駅からもそこそこ近いし、距離は近い半田よりもかなり行きやすい。 受付を済ませて、芝生席で準備。50分前くらいからトラックを5周相当。トラックは土。開会式が始まったが、何言ってるかよく聞こえない。かまわずストレッチする。芝生席…

NHKスペシャル|魔性の難問 〜リーマン予想・天才たちの闘い〜

バーゼル問題を説明するとき、すごい書き順だった。πと分数。分母から書くのって、日本だけ? リーマン予想の凄さを全然伝えられてなかった。

Project Euler 264(1)

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=264どうも、的外れの計算を延々としてしまっていたようで。図形で考えるべきだった。 時間切れなので、明日の午後に考えよう。果たして体力が残っているか。

完全数・友愛数・社交数

ここでは、d(n)をn自身を除いたnの約数の総和とします。 完全数 d(n) = n を満たすとき、nを完全数(Perfect number)と呼びます。 p = 2m - 1 で、pが素数のとき、pをメルセンヌ素数と呼びます。メルセンヌ素数には特別な高速の素数判定法があり、現在見つ…

多角数

三角数 図のように三角形を作っていったときに●の個数が三角数になります。最初が1で、2、3と足していけばいいので、n番目の三角数は、 となります。 Project Eulerでもよく使われる数です。 四角数 平方数です。 五角数 図のように五角形を作っていったとき…

Project Euler 10

Problem 10 (略)200万より小さい全ての素数の和を求めよ http://projecteuler.net/index.php?section=problems&id=10 個別に素数を求めるのは非常に遅いので、エラトステネスのふるいを使いましょう。 配列を最初に0,0,2,3,4,5,…と初期化して、素数でない…

約数

約数の個数 自然数の約数(divisor)は、素因数分解されていると簡単に求まります。まず、8の約数は、23だから、2をいくつ選ぶかで決まります。すなわち、0〜3個のうちどれかを選ぶことになります。 1 = 20 2 = 21 4 = 22 8 = 23 ですから、8の約数の個数は4…

Project Euler 263(2)

素数の処理で恐ろしい間違いを犯していたのだが、速度にはそれほど影響がなかった。遅いのは素数の生成の部分だったが、本質的に速くなりそうになかった。Pythonでリストを使うと非常に遅くなることはなんとなく分かっていたので、C++でvectorを使ってほとん…

Project Euler 2(2)

この程度の大きさの数なら問題ありませんが、実数の計算にはどうしても誤差がつきまといます。しかし、今回の計算は誤差無しで計算することができます。 (a + b√5) / c -> (a, b, c) と表すことにしましょう。そうすると、 (a, b, c) + (d, e, f) = (af + dc…

21km走

やっと今シーズンはじめてハーフ相当の距離を走れた。 ゆっくり走ったつもりなのに、15kmくらいから足が重くなってきた。 dist time /km - 1.44 7:29.25 5:12 1.44 7:13.65 5:01 1.44 7:08.26 4:57 1.44 7:12.58 5:00 1.44 7:08.99 4:58 1.44 7:07.23 4:57 1…

Project Euler 263(1)

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=263 う〜ん、なんとか答えが出た。 素数はどうしても列挙しなければならないので、部分的なエラトステネスのふるいを使って、triple-pairが見つかったら、その都度practicalか…

Project Euler 2(1)

Problem 2 フィボナッチ数列の新しい項は、前の2つの項を足して生成される。最初を1,2とすると、最初の10項は、 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 400万を超えない偶数の項の総和を求めよ。 http://projecteuler.net/index.php?section=problems&id=2 その…