前回とほとんど同じなのですが、 ηという学習率を掛けるところが違います。これは時間の関数になっていて、t = 1, 2, …に対し、恐らく単調減少になっているほうが収束が速くなると思われます。η= 1 次元 1000サンプル 10000サンプル 100000サンプル 2 0.0433…

ここからは、この本を参考に進めていきます。オンライン機械学習 (機械学習プロフェッショナルシリーズ)作者: 海野裕也,岡野原大輔,得居誠也,徳永拓之出版社/メーカー: 講談社発売日: 2015/04/08メディア: 単行本（ソフトカバー）この商品を含むブログ (5件)…

点を打つのはいいのですが、本当にそれが超球面上に一様に分布しているのか確認したいところです。ある点を固定して、超球の中心を挟んでその点と他の点との成す角度がある分布をしているはずです。例えば3次元で考えると、角度θとθ+dθの間の表面積は 2πr2si…

まずは、二値分類のプログラムを書こうと思います。そのために、ランダムに超平面を作ります。しかし、超平面をランダムに作ろうとすれば、法線ベクトルをランダムに作る必要があります。すなわち、これは超球面上にランダムに点を打つことになります。最も…

Problem 468の計算量を見積もるときにこんな問題が思い浮かびました。 N以下を素因数分解したとき、素因数の個数の平均は？ 例えば、2、3、4 = 22、5なら1個、6 = 2 * 3なら2個とします。logNよりはずっと小さいと思われます。とりあえずコードを書いて調べ…

世界は2乗でできている 自然にひそむ平方数の不思議 (ブルーバックス)作者: 小島寛之出版社/メーカー: 講談社発売日: 2013/08/20メディア: 新書この商品を含むブログ (13件) を見るこの本に、オイラーのバーゼル問題に対する執念が書かれていました。バーゼ…

全問正解を達成したので、最近は問題作りをしている。Project Eulerでは誰でも出題することができる。ログインしてフォームに問題とコードと解説を貼りつけてサブミットするだけだ。もちろん英語で書かなければならないので、そこにはハードルがある。土曜日…

Pell方程式の初期解は、連分数から求められます（ペル方程式（2）参照）。拡張Pell方程式の初期解があるときは、この連分数がPell方程式の初期解が求まる前に求められます。D = 5でやってみましょう。 √5 = 2 + (√5 - 2) = 2 + 1/(√5 + 2) = 2 + 1/(4 + (√5 …

@Mi_Sawaさんの指摘を受けて書き直しました。拡張Pell方程式を x2 - Dy2 = -1 (Dは平方数でない自然数） とします。Pell方程式 x2 - Dy2 = 1 (Dは平方数でない自然数） はどのDに対しても解を持つことが知られています。では、拡張Pell方程式はどうでしょう…

「これまでで最大の素数」を発見 << WIRED.jp久しぶりに新たなメルセンヌ素数が発見されたようです。メルセンヌ数は、 Mn = 2n - 1 という形をしているのですが、なぜこの形の素数を求めようとするかというと、非常に高速な素数判定法があるからです。さて、…

各桁が異なる自然数について（2）の続きです。すべての東工大数の平方の和を考えましょう。 平方なので各桁ごとに和を取るというわけにもいきません。ここでは分割統治法を使ってみます。例えば1〜5を1回ずつ使った5桁の数の平方の総和を考えます。120個あり…

各桁が異なる自然数について（1）の続きです。まず、東工大数はいくつあるでしょう。 桁数ごとに考えましょう。1桁なら、1〜9の9個ですね。2桁なら、10〜99から11,22,…99を除くから81個あります。 3桁ならこんなに考え方では難しいですね。10個の数字から3個…

元ネタはこれです。 東工大学長「本学では2013が素数ではないと落胆する学生が多いようですが、ここでは2013のような各桁が異なる自然数を「東工大数」と呼びましょうか。 このネタでProject Eulerの問題になりそうなものが考えられないでしょうか。例えば、…

剰余類 まずは剰余類の説明からします。例えば15の剰余で考えます。2と17と32は15で割ると余りが2になります。これらは同じとみなして剰余類と呼びます。 H0 = { …, -15, 0, 15, 30, … } H1 = { …, -14, 1, 16, 31, … } H2 = { …, -13, 2, 17, 32, … } … -13…

分割数というのは、例えば5を自然数で分割することを考えます。同じ数を何度も使ってもよいですが、順序違いは区別しません。そうすると、 5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1の7通りあります。これを p(5)…

数学の難問「ＡＢＣ予想」、京大教授が解明かWikipediaを読んでもわからないと思う。ここのrという関数は、Project Euler Problem 127に書かれているradのことのようだ。この問題ではc 20まで求められているらしい。どうやって求めればよいのだろう。 [追記 …

Problem 160に少し出てくるので考えてみました。Wilsonの定理は、 pが素数なら(p - 1) ! ≡ -1 です。これは、pを法とした既約剰余類群の元を全て掛け合わせると-1となる、とも言えます。その積をP(p)と書くことにします。例えばp = 7として P(7) = 1 * 2 * 3…

昨日はcos20°を求めましたが、今日は√2を求めます。100万桁を目標にしましょう。 √nの循環連分数になります。√2は、 √2 - 1 = 1 / (2 + 1 / (2 + ...)) = [ 0; 2, 2, ... ] となります。連分数を途中で打ち切ったときの分数をan / bnと置くと、 an+2 = 2an+1…

Modegramming Style: Scalazの型クラスこれを読んでいてふと思ったこと。 結合則が成り立つ場合、畳込み（fold）を行うときリストを分割して並列で計算させれば速くなります。例えばsumですね。1〜100を足し合わせるときに、1〜50と51〜100に分けてそれぞれ…

Problem 375で使われている擬似乱数は sn+1 = sn2 mod d ここで法dはd = pqでpとqは4n+3型の素数です。これをBlum-Blum-Shubというそうです。 知りたいのはこの数列が戻ってくるかです。まず、初項に戻ってこないかもしれないのは当然です。自乗の剰余になれ…

英語ではHighly composite numberです。これより小さい数は全て、約数の個数が自分のそれより小さい自然数です。なぜこれが重要なのかは知りません。これはProblem 110のコードを少し改変するだけで得られます。1分以内に約数の個数が1012以内の高度合成数な…

http://projecteuler.net/index.php?section=problems&id=34これもProblem 30とほとんど同じです。 重複組合せを使う方法に対して、8倍くらい速かったです。

http://projecteuler.net/index.php?section=problems&id=30以前のと違う方法をふと思いついたので書きます。例えば、6桁として456789を考えます。 45 + 55 + 65 + 75 + 85 + 95 - 456789 が0ならいいわけです。ここで3桁ずつにわけて考えましょう。456000と…

エラトステネスのふるいです。ふつうに書いてみます。 def sieve1(N :Int) :List[Int] = { val a = new Array[Boolean](N + 1) for(n <- 2 to N) a(n) = true for(p <- Iterator.range(2, N + 1).takeWhile(p => p * p <= N) if a(p); k <- Iterator.range(p…

Pythonと同じことをします。 まずは試し割りから。 def is_prime1(n :Int) :Boolean = Iterator.from(2).takeWhile(p => p * p <= n).forall(p => n % p != 0) def make_primes(N :Int, is_prime :Int => Boolean) :List[Int] = Iterator.range(2, N + 1).fi…

エラトステネスのふるいの速度を確認します。まずは最も単純なもの。 def sieve1(N): a = [ True ] * (N + 1) for p in takewhile(lambda p: p * p <= N, (n for n in count(2) if a[n])): for k in xrange(p * 2, N + 1, p): a[k] = False return [ n for n…

昨日ひどかったので考え直してみました。要するに試し割りの回数がわかればいいのです。もちろんわからないので、n前後の試し割りの回数の平均を求めます。ガウスの故事に倣って1000個ずつ取って平均します。なるべく長いスパンで見たいので、平均を取る範囲…

どの素数判定法を使うべきか迷うことがあるのでまとめてみます。 試し割り法 ある整数が素数であるか2から順に割っていきます。nが素数かどうかの判定には√nまでの素数で割り、全て割り切れなかったら素数です。途中で割り切れたらその時点で合成数と分かり…

いわゆる分割数ではありません。分割して0も認めます。また順番が変わっただけの分割も別とみなします。すなわち、3を3分割なら、 3 = 3 + 0 + 0 = 2 + 1 + 0 = 2 + 0 + 1 = 1 + 2 + 0 = 1 + 1 + 1 = 1 + 0 + 2 = 0 + 3 + 0 = 0 + 2 + 1 = 0 + 1 + 2 = 0 + 0…

前に書いたものを少し書き直します。 マージ法（Merge algorithm）は、ソートされた二つの列を合体して一つのソートされた列を作るアルゴリズムです。（「マージ法」という用語はあまり使われていないようです） 原理は非常に簡単です。例えば次のような列が…