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

Project Euler 171

プロジェクトオイラー http://projecteuler.net/index.php Q171. 各桁の自乗和が自乗になる数で1020より小さいものの総和の最後の9桁。 自乗和のほうから考える。20桁までなので、20*9*9以下の自乗数を考えればよい。それぞれについて、自乗による分割を求め…

Project Euler 170

プロジェクトオイラー http://projecteuler.net/index.php Q170. 省略 最大のものを探せ、ということなので、9876543210から探索していけばよい。頭が5以上なら2分割しかありえないことがわかる。2つに分けた数の最大公約数を得て、その約数で割る。

Project Euler 169

プロジェクトオイラー http://projecteuler.net/index.php Q169. 1025を2のべきで分割する方法の個数。ただし、1もOK、同じ数は2つまで。 普通に、再帰で書ける。大きい数から使っていき、それがあと何回使えるかで関数にする。2m以下しか使えないとき、2m+2…

Project Euler 168

プロジェクトオイラー http://projecteuler.net/index.php Q168. 142857の7を前に持ってきて714285とすると、元の数が約数になるようなnの10 < n < 10100の総和の最後の5桁。 dを元の数の最後の桁の数字、mを桁数とすると、 10m-1d+(n-d)/10 = ((10m-1)d+n)/…

Project Euler 166

プロジェクトオイラー http://projecteuler.net/index.php Q166. 4×4のマス目に0〜9を置いて、縦・横・斜めの和がそれぞれ等しくなる場合の数。 まず、4隅に数字を置く。そして、あと5つ数字を置けばマス目が埋まってすべて等しくなるかが判定できる。4隅は…

Project Euler 163

プロジェクトオイラー http://projecteuler.net/index.php Q163. 省略 三角形内の点を生成する。その点から伸びる線を2本選ぶ。一方の線上で三角形内の点から伸びる線と他方の線との交点を求める。それが三角形内ならカウントする。

Project Euler 165

プロジェクトオイラー http://projecteuler.net/index.php Q165. 与えられた疑似乱数で発生させた5000本の線分の真の交点の個数 ただ交点を求めていくだけ。同じ交点は重複して数えないので、setにaddしていく。しかし、3300本目くらいからメモリが足りなく…

Project Euler 164

プロジェクトオイラー http://projecteuler.net/index.php Q164. 20桁で最初が0でなく、連続する3桁を足していずれも9以下になる自然数の個数 n桁で最後の2桁が決まった連続する3桁を足していずれも9以下になる自然数の個数を求める漸化式を作る。

Project Euler 162

プロジェクトオイラー http://projecteuler.net/index.php Q162. 16桁の16進数で、0・1・Aを1つ以上含み、かつ最初が0でない数の個数を16進数で表せ 最初が0でないという条件を取り除くと簡単。これを求めておき、最初の数字で場合わけする。

Project Euler 160

プロジェクトオイラー http://projecteuler.net/index.php Q160. f(n)をn!の0を除く最後の5桁とする。f(1012)を求めよ。 nまでの5で割り切れる数を除いて、かつ2の因子を5つまで取り除いた積をg(n)とする。例えば、 g(6) = 1 * (2/2) * 3 * (4/4) * (6/2) = …

Project Euler 159

プロジェクトオイラー http://projecteuler.net/index.php Q159. 自然数の各桁の和をとり、さらにそれが1桁になるまでそれを繰り返す。この値をDRと呼ぶ。例えば、467→17→8。自然数nを積の形に書いて、その因子のDRの合計の最大をmdrs(n)とする。1 < n < 100…

Project Euler 158

プロジェクトオイラー http://projecteuler.net/index.php Q158. 26個のアルファベットから違う文字n個を持ってきて並べる。そのとき"bacdef"のように辞書順に並んでいない部分が1箇所だけの文字列の数をp(n)とする。最大のp(n)。 アルファベットは分かりに…

Project Euler 157

プロジェクトオイラー http://projecteuler.net/index.php Q157. 1/a + 1/b = p/10nの1 ≤ n ≤ 9での解の個数 比較的平易な問題だが、1 ≤ n ≤ 9というのがよくわからなかった。これは、例えば、 1/2 + 1/5 = 7/10 1/2 + 1/5 = 70/100 これらは別の解というこ…

Project Euler 154

プロジェクトオイラー http://projecteuler.net/index.php Q154. (x + y + z)200000の係数で、それが1012の倍数である個数 n = m + k + lとして、n!/m!k!l!が係数となる。それが2と5を12個以上含めばよい。 5の個数は、[n/5] + [n/52] + ... - ([k/5] + [k/5…

Project Euler 151

プロジェクトオイラー http://projecteuler.net/index.php Q151. 省略 封筒の状態とその状態を取る確率を計算していく。最初にA2〜A5の紙が1枚ずつ入っている。それが確率1である。次の状態は、どの紙を取るかで変わってくる。しかし、それぞれの状態の確率…

Project Euler 150

プロジェクトオイラー http://projecteuler.net/index.php Q150. 決められた疑似乱数(リンク先参照)を三角形状に並べたとき、同じ向きの小三角形内の和の最小 和を見ていくとき、頂点を決めてそこから下に三角形を広げて和を取っていく。 ここで、一列和を…

Project Euler 148

プロジェクトオイラー http://projecteuler.net/index.php Q148. パスカルの三角形の最初の10億列の中で7で割り切れない項の個数 n!が含んでいる7の個数は、 [n/7] + [n/72] + ... nCkが含んでいる7の個数は、 [n/7] - [k/7] - [(n-k)/7] + [n/72] - [k/72] …

Project Euler 147

プロジェクトオイラー http://projecteuler.net/index.php Q147. 47×43の長方形の中に、それに平行あるいは45度傾いた長方形を置く。そのような長方形の数と、元の47×43の長方形が収まる平行な長方形に収まる長方形の数の和。 辺の長さをM,Nとすると、 平行…

Project Euler 147

プロジェクトオイラー http://projecteuler.net/index.php Q147. 47×43の長方形の中に、それに平行あるいは45度傾いた長方形を置く。そのような長方形の数と、元の47×43の長方形が収まる平行な長方形に収まる長方形の数の和。 辺の長さをM,Nとすると、 平行…

Project Euler 145

プロジェクトオイラー http://projecteuler.net/index.php Q145. ある正整数で、それとそれを10進で逆にした数の和の全ての桁が奇数のとき、reversibleと呼ぶ。10億未満のreversibleな数の個数。 桁数が偶数のとき、どの桁も反転した数字と足して奇数で、繰…

Project Euler 140

プロジェクトオイラー http://projecteuler.net/index.php Q140. GnをG1 = 1、G2 = 4、Gk = Gk-1 + Gk-2、AG(x) = xG1 + x2G2 + x3G3 + ...とする。 n = AG(x)が自然数であるxが有理数であるようなnの30番目。 Q137と同じようにすると、 (5A + 7)2 - 5m2 = 4…

Project Euler 137

プロジェクトオイラー http://projecteuler.net/index.php Q137. Fnをフィボナッチ数列としたとき、AF(x) = xF1 + xF2 + xF3 + ...とする。 n = AF(x)が自然数であるxが有理数であるようなnの15番目。 (1 - x - x2)A = x Ax2 + (A - 1)x - A = 0 D = (A - 1)…

Project Euler 136

プロジェクトオイラー http://projecteuler.net/index.php Q136. 自然数nについて、自然数x,y,zが等差数列になっていて、x2 - y2 - z2 = nを満たすとする。このような解が1つだけある7500万より小さいnの個数。 注意深く調べると、pを素数として、nは4の剰余…

Project Euler 135

プロジェクトオイラー http://projecteuler.net/index.php Q135. 自然数nについて、自然数x,y,zが等差数列になっていて、x2 - y2 - z2 = nを満たすとする。このような解が10ある100万より小さいnの個数。 d = y - zとして、 (z + 2d)2 - (z + d)2 - z2 = n (…

Project Euler 134

プロジェクトオイラー http://projecteuler.net/index.php Q134. 素数p1とその次の素数p2に対して、p1をお尻にした数でp2で割り切れるものが、p1が5以上で必ずある。例えば、p1=19,p2=23なら、1219が23で割り切れる。p1が5から100万までについてのその最小の…

Project Euler 133

プロジェクトオイラー http://projecteuler.net/index.php Q133. 1がk個続く整数をR(k)と表す。R(10n)の形の因数になりえない100万未満の素数の総和。 これはひっかけだ。最初「なりうる」だと思った。 素数pについて、kを2から見ていき、最初に2と5の因数し…

Project Euler 131

プロジェクトオイラー http://projecteuler.net/index.php Q131. n3 + pn2が立方数となりうる素数pの100万以下の個数 n3 + pn2 = (n + k)3 (p-3k)n2 - 3k2n - k3 = 0 D = 4pk - 3k2 判別式が平方数だから、 4pk - 3k2 = m2 3m2 + (3k-2p)2 = 4p2 ここで挫折…

Project Euler 129

プロジェクトオイラー http://projecteuler.net/index.php Q129. 1がk個続く数R(k)を考える。例えば、R(6) = 111111。これらをnが最初に割り切れるのがR(k)だとしたとき、A(n) = kと書く。A(n)が最初に100万を超えるn。 問題を見たとき途方もない計算だと思…

Project Euler 128

プロジェクトオイラー http://projecteuler.net/index.php Q128. 自然数を1から正六角形状のスパイラルに並べる。このとき、配置された数nと隣の6つの数との差のうちの素数の数をPD(n)とする。PD(n)=3となる2000番目のnは? 座標を、上にx、そこから左60°にy…

Project Euler 126

プロジェクトオイラー http://projecteuler.net/index.php Q126. 立方体のブロックを直方体状に並べる。そのブロックを最低限覆うようにブロックを並べたときのブロックの増分、さらにそのブロックを覆うようにブロックを並べたときの増分、...を考える。こ…