c21coterie @ ウィキ

c21coterie @ ウィキ内検索 / 「プロジェクトオイラー問９７」で検索した結果

• プロジェクトオイラーを楽しむページIndex
  ...ラー問９５ プロジェクトオイラー問９７ プロジェクトオイラー問９９ プロジェクトオイラー問１００直感的に解いたけどなぜこれでいいのか証明できてない プロジェクトオイラー問１０２ プロジェクトオイラー問１０４ プロジェクトオイラー問１０５ プロジェクトオイラー問１０８ プロジェクトオイラー問１１０ プロジェクトオイラー問１１２ プロジェクトオイラー問１１３ プロジェクトオイラー問１１４ プロジェクトオイラー問１１５ プロジェクトオイラー問１１６ プロジェクトオイラー問１１７ プロジェクトオイラー問１１８ プロジェクトオイラー問１１９ プロジェクトオイラー問１２０ プロジェクトオイラー問１２１ プロジェクトオイラー問１２３ プ...
• プロジェクトオイラー関係
  プロジェクトオイラー問い1～10 プロジェクトオイラー問い11～20 プロジェクトオイラー問い21～30 プロジェクトオイラー問い31～40 プロジェクトオイラー問い41～50 プロジェクトオイラー問い51～60 プロジェクトオイラー問い61～70 プロジェクトオイラー問い71～80 プロジェクトオイラー問い81～90 プロジェクトオイラー問い91～100 プロジェクトオイラー問い101～110 プロジェクトオイラー問い111～120 プロジェクトオイラー問い121～130 雑記・日記2へ戻る。 掲載を後回しにしている問い 66,69,80
• プロジェクトオイラー解説index
  プロジェクトオイラー解説ページ ここではプロジェクトオイラーの問題を気が向いた問題から解説をしていきます。 最良の解説とはいきませんが基本的に大体１分ルール満たせるレベルの解説はのせていくつもりです。 解説満足度は、自分なりにどれだけ納得できる解説を行えたかと記述ミスをどれだけチェックしたかと記述の進捗率の３点の総合的な％表示したものです。 プロジェクトオイラー解説問1 解説満足度70％ プロジェクトオイラー解説問2 解説満足度80% プロジェクトオイラー解説問3 解説満足度70% プロジェクトオイラー解説問4 解説満足度70％ プロジェクトオイラー解説問5 解説満足度75％ プロジェクトオイラー解説問6　解説満足度60％ プロジェクトオイラー解説問7　解説満足度70％ プロジェクトオイラー解説問8　解説満足度70％ ...
• プロジェクトオイラー問１２０
  Problem 120 「自乗で割った余り」 † (a-1)＾n+(a+1)＾n を a＾2 で割った余りを r と定義する. 例えば, a=7, n=3 の時, r=42 である 6＾3 + 8＾3 = 728 ≡ 42 mod 49. n が変われば r も変わるが, a=7 の時 r の最大値 rmax は 42 であることがわかる. 3 ≤ a ≤ 1000 において, Σ rmax を求めよ. 解法 ｎ乗を展開してa^2で割ると残るのはnが奇数なら末尾のan+1とan-1 偶数なら1+1だけです。 奇数の時だけ考えて an+1とan-1を足すと２anとなります ｎは奇数なのでｎが増加すると 2a,6a,10a,,,と増加します。 a^2-2を4で割った余りが1か３なら2anはa(a-1)を作れます。 そうでないなら2anはa(a-2)...
• プロジェクトオイラー問９７
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2097 Problem 97 「大きな非メルセンヌ素数」 † 100万桁を超える初めての素数は1999年に発見された. これはメルセンヌ素数であり, 2＾6972593-1 である. 実際, 2,098,960桁ある. それ以降も, より多くの桁になるメルセンヌ素数 (2p-1の形の数) が他にも発見されている. しかし, 2004年に, 非常に大きな非メルセンヌ素数が発見された. これは2,357,207桁の数であり, 28433×２＾7830457+1である. この素数の末尾10桁を答えよ. 解法 モード演算の中で計算すれば高速に求まります。 まあＰｒｏｌｏｇなんで２＾7830457+1を直接求めてもいいんですけれ...
• プロジェクトオイラー問６２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2062 Problem 62 「立方数置換」 † 立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である. 立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ. 解法 ３乗の数字を小さいほうから試していき、数字を辞書順で並べ替えたものを基準に集計していきます。 例えば345002なら002345が一つ見つかったとそれぞれ集計していきます。 最初に5個Hitした辞書順があればそれが答えです。 集計で新しい辞書順が出て...
• プロジェクトオイラー解説問8
  Problem 8 「数字列中の最大の積」 † 以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか. データが多いので問題の詳細はリンク先を読んでください。 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%208 解法 おそらくファイル読み込みの演習だと思います。 文字列やファイル読み込みは言語によって雑多な違いがあり統一的な話はできません。 まず1000文字の数字列をテキストファイルに保存し、このファイルの中身を文字列型に読み込んでいきます。 まず1000文字の数字を文字列として一行ずつ読み込み、 読み込んだ行strとしてstrAll+=strのように読み込み1000文字の文字列とします。 ...
• prolog勉強プロジェクトオイラー321～330
  プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ。 Problem 321 「カウンタの交換」 † チェッカーの駒を入れ替えるパズルを題材にとった数学の問題。 問題の詳細はリンク先参照のこと。 http //odz.sakura.ne.jp/projecteuler/index.php?Problem%20321 解放　只今考え中。 30分ほど紙の上で色々試行錯誤した結果。 最小入れ替え回数はたぶん青のチェッカーの枚数をｎ枚として。 n^2+2nで最小入れ替え回数が与えられこれが三角数なので適当な自然数ｍをとって。 n^2+2n=m*(m+1)/2 を満たす自然数ｎ、ｍの組となる。 整理すると 7/4=2(n+1)^2-(m+1/2)^2 という2次曲線上の整数解の組を小さいものから求めよという問題となる。 パズルに見せかけて実態...
• プロジェクトオイラー問２６
  http //projecteuler.net/problem=26 Problem 26 「逆数の循環節 その1」 † 単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる. 1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 = 0.125 1/9 = 0.(1) 1/10 = 0.1 0.1(6)は 0.166666... という数字であり, 1桁の循環節を持つ. 1/7 の循環節は6桁ある. d 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ. 解法 オイラーのファイ関数によれば 1/pが循環するということはフェルマーの小定理によれば必ず...
• プロジェクトオイラー問６９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2069 Problem 69 「トーティエント関数の最大値」 † オイラーのトーティエント関数, φ(n) [時々ファイ関数とも呼ばれる]は, n と互いに素な n 未満の数の数を定める. たとえば, 1, 2, 4, 5, 7, そして8はみな9未満で9と互いに素であり, φ(9)=6. n互いに素な数φ(n)n/φ(n) 2112 31,221.5 41,322 51,2,3,441.25 61,523 71,2,3,4,5,661.1666... 81,3,5,742 91,2,4,5,7,861.5 101,3,7,942.5 n ≤ 10 では n/φ(n) の最大値は n=6 であることがわかる. n ≤ 1,0...
• prolog勉強プロジェクトオイラー111～120
  プロジェクトオイラーという数学問題の掲載されたサイトの問題を堀江伸一さんがPrologで解くページ。 Prolog言語の特徴。 配列はない、ｓｔｄコンテナにあたるものはもちろんない。 何があるかっていうとリストしかない。 凄く不便。 しかも破壊的代入がない、そのため動的計画法と物凄く相性が悪い、破壊的代入を前提としたデータ構造とも相性が悪いというか現実的な計算量で実装できない物が多数。 基本ローカル変数しかないから変数が増える問題では関数（Prologでは厳密に述語といい関数とわけて考える）の引数が凄いことになる。 引数を減らすと、解集合を巨大なリストで得てそこから一番いい解を探すような富豪プログラムになる。 利点はバックトラックがあるくらい、このバックトラックという機能は論理的処理には向いており、このためマサチューセッツ工科大学でも論理枠でPrologの講義が一応行われて...
• プロジェクトオイラー問９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%209 Problem 9 「特別なピタゴラス数」 † ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a b c で以下の式を満たす数の組である. a^2 + b^2 = c^2 例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である. a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する. これらの積 abc を計算しなさい. 解法 原始ピタゴラス数を求める公式はWikiにある通りです。 原始ピタゴラス数の三辺 a+b+cが1000の約数になればそれを1000/(a+b+c)倍した三角形が答えです。 C++ならｍとｎの２重ループとすると...
• プロジェクトオイラー問７２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2072 Problem 72 「分数の数え上げ」 † nとdを正の整数として, 分数 n/d を考えよう. n d かつ HCF(n,d)=1 のとき, 真既約分数と呼ぶ. d ≤ 8について真既約分数を大きさ順に並べると, 以下を得る 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8 この集合は21個の要素をもつことが分かる. d ≤ 1,000,000について, 真既約分数の集合は何個の要素を持つか? 解法 オイラーのファイ関数をエラトステネスの...
• プロジェクトオイラー問１２９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20129 Problem 129 「レピュニットの非整除性」 † 1のみからなる数をレピュニットという. R(k) を長さ k のレピュニットとする. 例えば, R(6) = 111111 となる. GCD(n, 10) = 1 なる正の整数 n が与えられたとき, R(k) が n で割り切られるような k が常に存在することが示せる. A(n) をそのような k の最小のものとする. 例えば, A(7) = 6, A(41) = 5 となる. A(n) の値が10を超える最小の n は17である. A(n) の値が100万を超える最小の n を求めよ 解法 111、、、111を９倍すると999、、、999...
• プロジェクトオイラー問２７
  Problem 27 「二次式素数」 † オイラーは以下の二次式を考案している n＾2 + n + 41. この式は, n を0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40 のとき 40＾2 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる. また, n = 41 のときは 41＾2 + 41 + 41 であり明らかに41で割り切れる. 計算機を用いて, 二次式 n＾2 - 79n + 1601 という式が発見できた. これは n = 0 から 79 の連続する整数で80個の素数を生成する. 係数の積は, -79 × 1601 で -126479である. さて, |a| 1000, |b| 1000 として以下の二次式を考える (ここで |a| は絶対値) 例えば |11| = ...
• プロジェクトオイラー問９９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2099 Problem 99 「最大のべき乗」 † 指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 3^7 = 2187 であることが確かめられる. しかし, 632382^518061 519432^525806 を確認することは非常に難しい (両者ともに300万桁以上になる). 各行に1組が書かれている1000個の組を含んだ22Kのテキストファイル base_exp.txt から, 最大の数が書かれている行の番号を求めよ. 注 ファイル中の最初の二行は上の例である. 解法 Ｌｏｇを使っても十分答えが出るよう...
• プロジェクトオイラー問９２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2092 Problem 92 「桁の2乗による連鎖」 † 各桁の2乗を足し合わせて新たな数を作ることを, 同じ数が現れるまで繰り返す. 例えば 　　44 → 32 → 13 → 10 → 1 → 1 　　85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 のような列である. どちらも1か89で無限ループに陥っている. 驚くことに, どの数から始めても最終的に1か89に到達する. では, 10,000,000より小さい数で89に到達する数はいくつあるか. 解法 まずは素朴で低速な方法。 999万9999を変換しても567にしかなりません１回変換すると１０００万...
• プロジェクトオイラー問９１
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2091 Problem 91 「整数座標における直角三角形」 † 原点Ｏと２つの整数点(x,y)、ｘ、ｙは0から５０までの数。 で何個直角三角形が描けるか答える問題。 解法 点Ａを定めたらＯＡと直角でＡを通る直線状の点だけを検討します。 それだけでパッと答えが出ます。 原点が直角になる場合だけ特別扱いしてアセプトとなります。 sum([],0) -!. sum([X|Xs],Result) -sum(Xs,Re),Result is Re+X. points([X,Y]) - between(0,50,X), between(0,50,Y), X+Y 0. calc1(_,0,_,_,50) -!. calc1(0...
• プロジェクトオイラー問９５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2095 Problem 95 「友愛鎖」 † ある数の真の約数とは, それ自身を除く約数すべてである. 例えば, 28 の真の約数は 1, 2, 4, 7, 14 である. これらの約数の和は 28 に等しいため, これを完全数と呼ぶ. 面白いことに, 220 の真の約数の和は 284 で, 284 の真の約数の和は 220 となっており, 二つの数が鎖をなしている. このため, 220 と 284 は友愛数と呼ばれる. さらに長い鎖はあまり知られていないだろう. 例えば, 12496 から始めると, 5 つの数の鎖をなす. 12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 ...
• prolog勉強プロジェクトオイラー121～130
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ どうでもいい雑記。 今日宮沢賢治のやまなし　という作品を読んだ。 自然描写力が圧倒的、作画が一流のアニメを見た後のような読後感があった。 コードはページの下のほうに掲載。 コードを見てもらう前に競技プログラムの世界の話を少し書いておきます。 競技プログラムとは数学の問題のようにプログラムの問題が出題されそれを解くことを競う競技で国際的な大会も常時開催されていたりします。 ふつうはN月M日の１６時に出題され１８時までに回答を出題したかたのみ採点のように制限時間付となりますが、過去問題や問題集だけを扱ったサイトもあります。 プロジェクトオイラーは問題集サイトになります。 ここで問題を解くプログラムの話をします。 プログラムの世界では書いたプログラムをコードと呼びます。 競技プログラムの...
• prolog勉強プロジェクトオイラー1～10
  プロジェクトオイラーの問題を堀江伸一こと私がＰｒｏｌｏｇで解くページ。 プロジェクトオイラーの問題は問題番号が小さいものほど簡単で問題番号が大きいものは非常に難しくなります。 この辺は最初なので中学生プログラマでも挑戦できるレベルの問題が並ぶ。 Problem 1 「3と5の倍数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%201 1000未満の３か５の倍数になっている自然数の合計を答えよ 解法 数式で解くのが正しいけれどサイトの趣旨、数学の問題をプログラムで特に合わせて末尾再帰で記述。 mod_n(N,N) - member(R,[3,5]), N mod R= =0, !. mod_n(_,0) -!. search(1000,Ans) -!,write...
• オイラープロジェクト321～330
  問い324 以下の問題があります。 3x3xn の塔を 2x1x1 のブロックで埋める場合の数を f(n) とする。 ブロックは好きな方向に回転することができる；しかし、塔自身を回転・反転等させたものは区別して数える。 たとえば（q=100000007 として）： f(2) = 229, f(4) = 117805, f(10) mod q = 96149360, f(10^3) mod q = 24806056, f(10^6) mod q = 30808124. f(10^10000) mod 100000007 を求めよ。 問題の原文サイトはこちら。 http //projecteuler.net/problem=324 プロジェクトオイラーというサイトで数学の問題をプログラムで解こうという練習問題を扱ったサイトです。 自分で考え出した...
• 雑記・日記2
  ここはこのサイトの管理人こと堀江伸一さんの個人的な雑記、日記　勉強記録を雑多に集めたページです。 当サイトの小学生レベルの創作物に関する言い訳 勉強記録一覧 リンク　→会津大学オンラインジャッジコード記録 会津大学オンラインジャッジの解答コードでこちらへ来た方はリンク先へどうぞ、私のコードが掲載されています。 一応少数の問題でコード実行速度一位を取ったコードもあるのですこしは参考になるかもしれません(ご近所さんのある方はＡＯＪでコード実行速度一位とるなんて馬鹿でもできる笑いもの　ぷぷぷ　とか言ってました。世間的なＡＯＪの評価ってそんなものかもしれません)。 会津大学オンラインジャッジ復習 ここより以下は本当に個人的な雑記ですので気にしないでください。 もしも結婚できたら子供に言ってみたいこと ネットで好みのイラスト収集 新ギレン...
• プロジェクトオイラー問１３０
  Problem 130 「素数桁レピュニットと同じ性質を持つ合成数」 † 1からのみなる数をレピュニットと呼ぶ. R(k)で長さkのレピュニットを表す. 例えばR(6) = 111111である. GCD(n, 10) = 1 となる正整数 n について, 必ず正整数 k が存在し n が R(k) を割り切ることが証明できる. A(n) でそのような最小の k を表す. 例 A(7) = 6. A(41) = 5. 5より大きい素数 p について, A(p) が p - 1 を割り切ることが知られている. p = 41 のときには, A(41) = 5 であり, 40は5で割り切れる. 非常に少ないのだが, 合成数においても上が成立する場合がある. 最初の5つの例は 91, 259, 451, 481, 703 である. GCD(n, 10) = 1 か...
• prolog勉強プロジェクトオイラー21～30
  プロジェクトオイラーの問題をPrologで解くページ。 創価学会の皆さまから小学校の算数までしかできないと言われている堀江伸一さんがこのページのコードを書いているようです。 Problem 21 「階乗の数字和」 † http //projecteuler.net/problem=21 10000以下の友愛数の和を求めよという問題。 そのまま定義通り計算するだけです。 複数の関数で一つの関数を表現するＰｒｏlogて独特。 yakusuu_sum(1,_,1,Sum,Sum) -!. yakusuu_sum(N,M,1,Sum,Sum1) -N M*M,!,Sum1 is Sum*(N+1). yakusuu_sum(N,M,Multi,Sum,Result) - 0= =N mod M,!, N1 is N//M, Multi1 is Multi*M+1, ya...
• プロジェクトオイラー問６
  Problem 6 「二乗和の差」 † 最初の10個の自然数について, その二乗の和は, 1^2 + 2^2 + ... + 10^2 = 385 最初の10個の自然数について, その和の二乗は, (1 + 2 + ... + 10)^2 = 3025 これらの数の差は 3025 - 385 = 2640 となる. 同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ. 解法 数学の公式を使えば一行で答えが出ますが。 せっかくプログラム言語があるのだし逐次的に求めてみましょう。 再帰で足す数Nを1ずつ足す数を増加させながら２乗の和と普通の和を足して、最後に普通の和を２乗してその差分をとれば答えです。 calc(Stop,Stop,Sum1,Sum2,Ans) -!, Ans is Sum1*Sum1-Sum2. calc(N,Sto...
• プロジェクトオイラー問２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%202 Problem 2 「偶数のフィボナッチ数」 † フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 数列の項の値が400万以下の, 偶数値の項の総和を求めよ. 解法 漸化式を使った解法。 再帰で自然に記述できます。 賢い解法はこちらを参照のこと。 http //bach.istc.kobe-u.ac.jp/lect/ProLang/org/euler-002.html isAdd(N,0) -N mod 2= =1,!. isAdd(N,N) -!. ...
• プロジェクトオイラー問１
  Problem 1 「3と5の倍数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%201 10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる. 同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ. 解法 条件を満たす数のリストを得てそれを集計する方法。 okNum(N) -N mod 3= =0,!. okNum(N) -N mod 5= =0,!. numListCreate(N) - between(1,999,N), okNum(N). sum([],0) -!. sum([X|Xs],Result) -sum(Xs,Re),Resul...
• オイラープロジェクトカンニング履歴
  会津大学オンラインジャッジの問題とおなじくカンニングして解いたオイラープロジェクトの問題のリスト。 数学の問題集を扱ったサイトなので調べものして数学の知識を身につけながら解くのが正道な気がするが、一応出来るだけ自力で解きたいところ。 なのでカンニングして解いた問題のリストを掲載。 問い12 問題を解く方法がよくわからず掲示板で質問。 コードまで書いてもらうもコードの読解や原理がよくわからず考え中。 問い25 フィナボッチ数が１０００桁になるのは数列の何個目か？ 単純に1000ケタを超えるまでフィナボッチ数列を計算して解こうと挑戦。 ほとんどコードを書いたことがないＬｉｓｐで解こうと考え、初心者レベルのコードを記述してみて実行時エラー。 掲示板でloop中の（が一つ多いでのでsetqのあたりが余分に関数と解釈されてると指摘を受けそれを修正してアセプト。 修...
• prolog勉強プロジェクトオイラー71～80
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 と書きましたが、下記リンク先サイトの方が私のコードよりずっと賢いのでそちらを参考にした方がよいです。 http //d.hatena.ne.jp/nineties/20110119 プロジェクトオイラーについては私のサイトよりこの人のサイトの方がずっと賢いです。 問い75はブロコット木を使えば早くなるとか、76や77は分割数と見るより、1～99までのコインを組み合わせたり素数を組み合わせる動的計画法とみるなど。 読めば目からうろこな発想でかかれています。 物事や問題をシンプルな話に変換できる能力、リンク先の人は私から見れば尊敬に値します。 プロジェクトオイラーの問題は問題番号が大きいほど難しくなるのですが、頭の悪い私でも問題番号100以下の簡単な問題なら解けます。 しかし同じ簡単な問題を解く...
• プロジェクトオイラー問４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%204 Problem 4 「最大の回文積」 † 左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である. では, 3桁の数の積で表される回文数の最大値を求めよ. 解法 まずは数字を一桁ごとのリストに変える述語toList。 リストが左右対称であるかをしらべる述語palindromeを書きます palindrome(List,[],List) -!. palindrome(List,[X|Rest],RevList) - palindrome(List,Rest,[X|RevList]). toList(0,[]) -!. toL...
• プロジェクトオイラー問７
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%207 Problem 7 「10001番目の素数」 † 素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である. 10001 番目の素数を求めよ. 基本はsqrt(N)まで試し割って割り切れる数が見つかればその数は素数でない。 でなければ素数と判定します。 本当や１以下の取り扱いや２や素の倍数の判定が必要ですが、問題の性質から奇数だけを考えてコードをくみます。 not_prime(N) - between(1,N,N1), Div is N1*2+1, (Div*Div N- !,fail;true), N mod Div= =0, !. is_prime(N...
• プロジェクトオイラー問３
  Problem 3 「最大の素因数」 † 13195 の素因数は 5, 7, 13, 29 である. 600851475143 の素因数のうち最大のものを求めよ. 解法 1ずつ増やしながらためし割りしていけば素数のときだけ割ることができます。 コードではたとえばｐで割れたらdiv述語でｐで割れるだけ割ってから次に進みます。 数字Nの素因数はN=p1^a1*p2^a^*,,,*pn^anですが、ｐiで割り切れば、piはｎから完全に消えます。 それ以外の素因数は消えません。 なので小さいほうから試しても素数以外で割ることがないということになります。 Prologは導出木と等価ですが、その分杓子定規な記述になります。 実際今回のコードを教科書的に記述してみましたがコードが膨らんでいますね。 Prologでは細部でコードを短くするのではなく、賢い導出木と...
• プロジェクトオイラー問い51～60
  問い51 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2051 　*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる. 　56**3の第3桁と第4桁を同じ数で置き換ることを考えよう. この5桁の数は7つの素数をもつ最初の例である 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である 　56003は, このような性質を持つ最小の素数である.　 　桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注 連続した桁でなくても良い) 解法 100万までの素数をvectorに格納し、各素数それぞれについて*文字にチェンジした全パタ...
• プロジェクトオイラー問８
  Problem 8 「数字列中の最大の積」 † 以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか. 詳細はリンク先を参照してください。 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%208 まず１０００桁の数字を文字列リストとしてわたし、文字列リストを48引いて数字に戻します。 あとは文字列リストの先頭５桁の掛け算を試しながら大きいほうをTempAnsとして残して、先頭を一つずつ短くしながらsearchして、サイズ4になったら計算終了で値を返します。 max(A,B,A) -A B,!. max(_,B,B) -!. search([_,_,_,_],Ans,Ans) -!. search([A,B,C...
• プロジェクトオイラー問５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%205 Problem 5 「最小の倍数」 † 2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である. では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか. 解法 機械的に考えるならlcm(1,2,3,,,,20)ですのでそのまま実装します。 手計算で考えると 1,2,3、、、で割れる数と考えていくと。 1で最初その数は１． 2でその数は２． 3でそのかずは３． 4でその数は２＾２で割れるのだから、２が二つ、３が一つ素因数として必要、だから4*3＝12. 5でその数は2＾２　３　5で割れないとダメだから2＾2*3*5....
• プロジェクトオイラー問１９
  http //projecteuler.net/problem=19 Problem 19 「日曜日の数え上げ」 † 次の情報が与えられている. 1900年1月1日は月曜日である. 9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである. 2月は28日まであるが, うるう年のときは29日である. うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない. 20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になるのは何回あるか? 解法 問題のほうで日数計算に必要なデータが提示されているので、出題の意図を読んでそれをつかって計算するのが正しいと思いますが。 ツェラーの公式で手抜きしました。 zellers(Y,M,D,Result) - (M 3 ...
• プロジェクトオイラー問４０
  Problem 40 「チャンパーノウン定数」 † 正の整数を順に連結して得られる以下の10進の無理数を考える 0.123456789101112131415161718192021... 小数第12位は1である. dnで小数第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 を求めよ. 解法 一桁は９個めまで ２桁は１８０+9個めまで ３桁は２７００+１８０+9個めまで続き以下同様です。 例えば3000なら２８８９個めの４桁の中に答えがあり、 ４桁は4つ数字が延々ならぶので(111-1)/4+1000の数字の中に目的のポイントがあり。 そのポイントの数字の中の(p-1) mod 4桁目が答えとなります。 calcP(P,[S|_],Keta,ReNum,Re...
• プロジェクトオイラー問１２
  Problem 12 「高度整除三角数」 † 三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... となる. 最初の7項について, その約数を列挙すると, 以下のとおり. 1 1 3 1,3 6 1,2,3,6 10 1,2,5,10 15 1,3,5,15 21 1,3,7,21 28 1,2,4,7,14,28 これから, 7番目の三角数である28は, 6個以上の約数をもつ最初の三角数であることが分かる. では, 500個以上の約数をもつ最初の三角数はいくつか. 解法 三角数はD=n(n+1)/2で、約数の個数はDを小さいほ...
• プロジェクトオイラー問２５
  http //projecteuler.net/problem=25 Problem 25 「1000桁のフィボナッチ数」 † フィボナッチ数列は以下の漸化式で定義される Fn = Fn-1 + Fn-2, ただし F1 = 1, F2 = 1. 最初の12項は以下である. F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 144 12番目の項, F12が3桁になる最初の項である. 1000桁になる最初の項の番号を答えよ. 解法 フィナボッチ数列の近似式と対数計算から求めます。 式から求めるのは少しめんどくさいですね。 fina(N,Result) - Result is ...
• プロジェクトオイラー問１８
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2018 Problem 18 「最大経路の和 その1」 † 以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる. 3 7 4 2 4 6 8 5 9 3 この例では 3 + 7 + 4 + 9 = 23. 以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ. 詳細はリンク先参照のこと。 解法 一段ずつの動的計画法で片が付きます。 max(A,B,A) -A B,!. max(_,B,B) -!. calcCol([D],[X,Y],AddDX,[AddDY]) - !, write([X,Y,D]), AddDY is D+Y, Ad...
• プロジェクトオイラー問２９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2029 Problem 29 「個別のべき乗」 † a^bで 2 =a,b =100を考えるとき重複を排除すると何通りの数が作れるか？ 解法 とりあえずプルートゥーズな方法で実装してみました。 全部求めて重複削除、それだけです。 calc(C) - between(2,100,A), between(2,100,B), C is A^B. main29 - findall(PowAB,calc(PowAB),PowABs), list_to_set(PowABs,PowABs1), length(PowABs1,Ans), write(Ans).
• プロジェクトオイラー問４６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2046 Problem 46 「もうひとつのゴールドバッハの予想」 † Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した. 9 = 7 + 2×12 15 = 7 + 2×22 21 = 3 + 2×32 25 = 7 + 2×32 27 = 19 + 2×22 33 = 31 + 2×12 後に, この予想は誤りであることが分かった. 平方数の2倍と素数の和で表せない最小の奇合成数はいくつか? 解法 小さい数から試していきます。 i=2から初めてiを1ずつ増加させます。 iが平方数ならiとi以下の素数個々との和全部をstd setに入れます。 ...
• プロジェクトオイラー問７５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2075 Problem 75 「1通りの整数直角三角形」 † ある長さの鉄線を折り曲げたときに1通りの直角三角形を作る最短の長さは12 cmである. 他にも沢山の例が挙げられる. 12 cm (3,4,5) 24 cm (6,8,10) 30 cm (5,12,13) 36 cm (9,12,15) 40 cm (8,15,17) 48 cm (12,16,20) それとは対照的に, ある長さの鉄線 (例えば20cm) は整数長さで折ることができない. また2つ以上の折り曲げ方があるものもある. 2つ以上ある例としては, 120cmの長さの鉄線を用いた場合で, 3通りの折り曲げ方がある. 120 ...
• プロジェクトオイラー問７４
  http //projecteuler.net/problem=74 Problem 74 「桁の階乗による連鎖」 † 145は各桁の階乗の和が145と自分自身に一致することで有名である. 1! + 4! + 5! = 1 + 24 + 120 = 145 169の性質はあまり知られていない. これは169に戻る数の中で最長の列を成す. このように他の数を経て自分自身に戻るループは3つしか存在しない. 169 → 363601 → 1454 → 169 871 → 45361 → 871 872 → 45362 → 872 どのような数からスタートしてもループに入ることが示せる. 例を見てみよう. 69 → 363600 → 1454 → 169 → 363601 (→ 1454) 78 → 45360 → 871 → 4536...
• プロジェクトオイラー問４４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2044 Problem 44 「五角数」 † 五角数は Pn = n(3n-1)/2 で生成される. 最初の10項は 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ... である. P4 + P7 = 22 + 70 = 92 = P8 である. しかし差 70 - 22 = 48 は五角数ではない. 五角数のペア Pj と Pk について, 差と和が五角数になるものを考える. 差を D = |Pk - Pj| と書く. 差 D の最小値を求めよ. 解法 http //d.hatena.ne.jp/inamori/20100214/p2 三平方の定理と結びつける解...
• プロジェクトオイラー問１０
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2010 Problem 10 「素数の和」 † 10以下の素数の和は 2 + 3 + 5 + 7 = 17 である. 200万以下の全ての素数の和を求めよ. 解法 小さい数から試します、N=2は既知として与え、３以上の数Nが素数ならそれを足す処理とします。 素数判定はsqrt(N)までのためし割りでは速度が出ません。 それまで得られた1500以下の数の素数リストで試し割ることで少しだけ速度をあげます。 素数リストを作るときappendを使っています。 appendは効率が悪いという話がありますが、1500以下の素数リスト程度の長さなら気にするほどではないでしょう。 not_prime(N,Primes) - mem...
• プロジェクトオイラー問１６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2016 Problem 16 「累乗の各桁の和」 † 2＾15 = 32768 であり, これの各桁の和は 3 + 2 + 7 + 6 + 8 = 26 となる. 同様にして, 2＾1000 の各桁の和を求めよ. 解法 ２＾1000を計算して各桁の和をとるだけです。 何か賢い方法はあるのでしょうか？ calc(0,0) -!. calc(X,Result) - Add is X mod 10, X1 is X//10, calc(X1,Re), Result is Re+Add. main16 - X is 2^1000, calc(X,Ans), write(Ans).
• プロジェクトオイラー問５３
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2053 Problem 53 「組み合わせ選択」 † 12345から3つ選ぶ選び方は10通りである. 123, 124, 125, 134, 135, 145, 234, 235, 245, 345. 組み合わせでは, 以下の記法を用いてこのことを表す 5C3 = 10. 一般に, r ≤ n について nCr = n!/(r!(n-r)!) である. ここで, n! = n×(n−1)×...×3×2×1, 0! = 1 と階乗を定義する. n = 23 になるまで, これらの値が100万を超えることはない 23C10 = 1144066. 1 ≤ n ≤ 100 について, 100万を超える nCr は...
• プロジェクトオイラー問３７
  Problem 37 「切り詰め可能素数」 † 3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3). 右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ. 注 2, 3, 5, 7を切り詰め可能な素数とは考えない. 解法 切り詰め可能な素数は最後は必ず、2,3,5,7となります。 逆に考えると右を削るの逆操作を考えると、右に付け足すと考えても目的の数は手に入ります。 そして幸運なことに一桁目を素数から初めて永遠に右に付け足すことはできません。 ２桁以上が手に入ったら左を全て削れるか試して合格した数を答えとします。 ね、簡単でしょ？...
• @wiki全体から「プロジェクトオイラー問９７」で調べる

更新順にページ一覧表示 | 作成順にページ一覧表示 | ページ名順にページ一覧表示 | wiki内検索