euler

Problem 26

1000以内の数に対して 1 / nを求めたときに最も長い幅の循環少数になる nを求めろという問題。素数以外の数は素因数分解したときの一番でかいサイズの 素数に依存するのではないかと思うので、対象は素数のみとする。 方針は wikipediaあたりを参考に決定。 …

Problem 25

フィボナッチ数列で 1000桁を越える一番初めの数字は何かという 問題。楽勝じゃんって思ってやったら 30桁ぐらいで答えがでなく なって調べてみたら、整数値に収まってなかった。なのでbigintを使う。 #!/usr/bin/perl use strict; use warnings; use bigint…

Problem 24

0から9の数字で順列を作って 1000000番めに大きい数を求めろという問題。 先頭が 0でも問題ないっていうのでだいぶ楽になったのかな〜と思います。 単純な方法だと単に 0123456789 から 9876543210まで数えていく方法だろうけど、 面倒なので楽な方法を考え…

Problem 22

ファイルから名前を読んでそれぞれスコアを付けて、その合計を求めろという 問題。名前が二重引用符でくくられてるのが微妙にやらしいけど、それ以外は簡単。 #!/usr/bin/perl use strict; use warnings; print "Answer is ", p22(), "\n"; # Answer is 8711…

Problem 23

過剰数の和で表せない数の合計を求めろという問題。上限がわかっているので、 配列を使ってといてみた。若干 Lisp風に考えてみたかなって思ったけど、全然 そんなことはないかな。約数の和を求めるのは過去の資源を再利用。 #!/usr/bin/perl use strict; use…

Problem 21

10000までの友愛数の総和を求めろという問題。ものすごく単純な方法は即効でかけたけど 遅かったので、Wikipediaの約数の項目を参考に修正しました。そしたらいくらか早くなりました。 キャッシュの機能をつけたらもう少し早くなりそうな気がしますが、それ…

Problem 20

1000の階乗で各桁を和を求めろという問題。10になる組み合わせを省いて いったら大した数にならないのかな〜って考えたんだけど、全然そんなこと ありませんでした。なので定番の配列を使って多倍長整数演算を行う手法で 解決しました。これだとせいぜい数百…

Problem 19

日本語を見たときは意味がわからなかったけど、月の初め、つまり1901年から 2000年の終わりまでの間に 1日が日曜日の月が何回あるかって問題。 モジュール番と数え上げる版を書いてみた。まあ大学一年生でやりそうな問題かな。 #!/usr/bin/perl use strict; …

Problem 18

何番やっているのかわからなくなってきたけど、18番。 時間がかかるであろうっていうのとそうでないを書いてみた。 時間がかかるってやつは 67番だと再帰使い過ぎでエラーになりますね。 #!/usr/bin/perl use strict; use warnings; my $depth = 15; my $m…

Problem 16

さすがに手を抜きすぎですね。真面目に考えます。 #!/usr/bin/perl use strict; use warnings; use bigint; my $num = 2 ** 1000; my @a = split //, $num; my $sum = 0; map {$sum += $_;} @a; print "$sum\n";

Problem 15

15問目。20*20の区画で最短距離の個数を求めろという問題。 公式に当てはめたら一瞬で解けた。こんなんでいいのかと逆に心配になった。 #!/usr/bin/perl use strict; use warnings; print "Answer is ", p15(20, 20), "\n"; sub p15 { my ($length, $width) …

Problem 14

14問目。コラッツ数列(?)で100万以内の数字で最も数列が長くなるものを求める。 普通に解くと1分強かかってしまったので、すべての数列の長さを記録しておき、 数字が記録していた数になったら、記録した数にそれまでの回数を加算するという ことにしました…

Problem 13

13問目。ちなみに11問目は面倒そうなので後回し。 今回の問題は 50桁の数値の加算を100回してその上位 10桁を求めろっていう問題。 Perlモジュールの bigintっていうのを使えば普通のたし算で解けてしまうのであまり 勉強にはなりそうにないので、一応配列使…

Problem 12

12問目。三角数を求めて行ってその約数の個数が 501個を越える初めの数は何かという 問題。普通に約数を数えていくと時間がかかりすぎるので、wikipediaに書いていた約数の 個数を求める公式を利用。 nが x^a * y^bと素因数分解されるとき nの約数の個数は (…

Problem10

なんとか10問目。8問目で作った素数判定関数をそのまま利用。 11秒ぐらいかかりましたね。当っているのかな? #!/usr/bin/perl use strict; use warnings; my @primes; print "sum of prime number below 2 million is ", p10(2000000), "\n"; # answer is 1…

Problem9

9問目。三平方の定理を満たす a, b, cの合計が 1000になる唯一組み合わせを 見つけろという問題。wikipediaによると一応定理はあるみたいですね。要検討。 a,b,cの順番で数字が大きくないといけないので、aは333未満, bは500未満ぐらいに なるんですかね。 #…

Problem8

すごく長い数字の列において連続する 5つの数の積が最も大きくなるものを求めろ。 素直に 5個抽出して 1つずつ積を求めるという具合で。0を含んだら無視するとかに すると多少早くなるんですかね。 #!/usr/bin/perl use strict; use warnings; my $str = "73…

Problem 7

10001個目の素数を求めろという問題。調べたら素数に関するMath::Prime::XSというモジュールが あってその中の is_primeという関数を使ってみたんだけど 10分ぐらい待っても答えがでません でしたね。一応 core2duo 1.8GHzぐらいなんですけど。ある数以下の…

Problem 6

100までの自然数に関して 2乗の和と和の2乗の差を求めろ。難しくはないですね。 #!/usr/bin/perl use strict; use warnings; my ($sum_of_square, $square_of_sum) = p6(100); # 25164150 print "difference is ", ($square_of_sum - $sum_of_square), "\n";…

Problem 5

5問目。1から20までのすべての整数で割り切れる数の最小値を求めろ。 たぶん 1から20の最小公倍数を求めれば答えになるでしょう。リストからポップして 最小公倍数をどんどん求めていく。aとbの最小公倍数は a * b / (aとbの最大公約数)に なるそうなので、…

Problem 4

4問目。3桁の数の掛け算で上から読んでもしたから読んでも同じ数になるもののうち 最大値を選べという問題。それなりに perlらしく解答できたのかな?値を配列で返しても よかったけど、面倒なので文字列で返した。ちなみに 4桁だと 99000099 = 9999 * 9901 …

Problem 3

素因数の最大値を求める問題。問題の数値が大きいからそれなりに時間がかかりますね。 なんでかは知らないけど、素因数は目的の数の二乗根より小さいのでそれで計算時間を短縮。 #!/usr/bin/perl use strict; use warnings; print "max prime factor is ", p…

Problem 2

2問目。問題を見たときに偶数の項のことを偶数番目の項と思ったんだけど、英語を 見ると even-valued termsになっているので値が偶数の項みたいです。 #!/usr/bin/perl use strict; use warnings; print "sum is ", p2(4000000), "\n"; # 4613732 sub p2 { m…

Problem1

結構 http://odz.sakura.ne.jp/projecteuler/index.php?Project%20Euler が流行っているようなので便乗して頑張る。使用言語は基本 Perlで。 #!/usr/bin/perl use strict; use warnings; print "input number >>> "; chomp( my $num = <STDIN>); print "sum is ", p</stdin>…