{1,...,i}からn個をとった上位t個の和がsになるのは, t個全部がiの場合とt個のうちk個(0<=k<=t-1)がiの場合がある.
t個のうちk個がiになる場合は, 「{1,...,i-1}からn-k個をとった上位t-k個の和がs-ikになる並び」にk個のiをねじ込むとできる.
t個が全部iになる場合はi*t == sの場合しかなくて, 「{1,...,i-1}からn-k個をとった並び」にk個のiをねじ込むとできる.
また, n-k個の並びにk個のiをねじ込む仕方は ${_{n-k+1} \mathrm{H} _k = {_n \mathrm{C} _k}}$ 通りある

よって
$f(1,n,t,t) = 1$
i*t == sのとき $f(i,n,t,s) = \sum_{k=0}^{t-1} {_n\mathrm{C}_k} f(i-1,n-k,t-k,s-ik) + \sum_{k=t}^{n} {_n\mathrm{C}_k} (i-1)^{n-k}$
i*t != sのとき $f(i,n,t,s) = \sum_{k=0}^{t-1} {_n\mathrm{C}_k} f(i-1,n-k,t-k,s-ik)$

高速化のためにメモ化したり, i*t < sのときは必ず0なので打ち切ったりする.

Project Euler 293

10^9未満のadmissible numberのリストを作成して, それぞれに対してpseudo-Fortunate numberを求める.

i番目の素数を含むadmissible numberのリストをf(i)とする. 便宜的にf(1)=[1]とすると
i+1番目の素数をpとして
f(i+1) = f(i-1).map{|n| n*p }+f(i-1).map{|n| n*p^2 }+...+f(i-1).map{|n| n*p^m }
ただし, n*p^m < 10^9 <= n*p^(m+1)
でadmissible numberが求められる.

pseudo-Fortunate numberは素直に素数のリストを引くか, 2ずつ増やして素数判定を行って調べる.
チェビシェフの定理によれば任意の自然数nについてn+1 < p < 2(n+1)を満たす素数pが必ず存在するから
sqrt(2*10^9)までの素数表があれば十分足りる.

Project Euler 315

nの各桁の総和をsum(n)とする. (sum(123) = 1+2+3 = 6)
数nの右からi桁目を $n_i$ とする. $123_1 = 3, \, 123_2 = 2, \, 123_3 = 1, \, 123_4 = _$
数字dを表示するとき点灯するセグメントの本数をnum_seg(d)とする. ただし, num_seg(_) = 0とする.
数字dを数字eに変更するコスト(dとeの異なるセグメントを消灯,点灯するコスト)をc(d,e)とする.
ただし, c(d,_) = dを消灯するコスト = numseg(d)とする.

サムの方法で, 既にnが表示されている状態から始めて数字根を表示しきるまでのコストをsams(n)とすると
$sams(n) = \sum_{i=1}^{L} numseg(n_i) + numseg(sum(n)_i) + sams(sum(n))$

マックスの方法で, 既にnが表示されている状態から始めて数字根を表示しきるまでのコストをmaxs(n)とすると
$maxs(n) = \sum_{i=1}^{L} c(n_i,sum(n)_i) + maxs(sum(n))$
ただし, Lはnの桁数.

nが1桁のとき, sams(n) = maxs(n) = nを消灯するコスト = numseg(n)

区間ふるいを使ってみた.

Project Euler 329

i回目のジャンプで鳴く鳴き声をs[i]とする.
s=[P,P,P,P,N,N,P,P,P,N,P,P,N,P,N]
s.length==15

位置iにいるカエルがs[j],s[j+1],...,s[14]と鳴く確率をf(i,j)
位置iにいるカエルがs[j]と鳴く確率をp(i,j)
とすると

f(i,14) = p(i,14)
j < 14のとき

f(1,j) = p(1,j)f(2,j+1)
f(500,j) = p(500,j)f(499,j+1)

1 < j < 500, j < 14のとき

f(i,j) = (1/2)p(i,j)f(i-1,j+1)+(1/2)p(i,j)f(i+1,j+1)

p(i,j)は
(iが素数かつs[j]=P)または(iが素数でないかつs[j]=N)のときp(i,j) = 2/3
それ以外のときp(i,j) = 1/3

Project Euler 345

割当問題なのでglpkで解いてみた.
http://gusek.sourceforge.net/gusek.html:GUSEKのサンプルについていたassign.modを流用できた.

Project Euler 371

3桁の数を合計が1000になるペアに分ける. 500と000だけは特別扱いする.
ペア1: [001,999]
ペア2: [002,998]
ペア3: [003,997]
...
ペア499: [499,501]
500, 000
すると勝ちの条件は

500が二回出る
既に出ているペアの片割れが出る(例えば, 既に012が出ているときに988が出る)

Q(k,t)を, k個のペアが出て500がt回出ている状態として状態遷移の仕方を考える
Q(k,0)の状態で

000が出る →Q(k,0)
500が出る →Q(k,1)
k個のペアの片割れが出る →勝ち
k個のペアの既に出た番号が出る →Q(k,0)
上記の他の番号が出る →Q(k+1,0)

Q(k,1)の状態で

000が出る →Q(k,1)
500が出る →勝ち
k個のペアの片割れが出る →勝ち
k個のペアの既に出た番号が出る →Q(k,1)
上記の他の番号が出る →Q(k+1,1)

f(k,t)を, 状態Q(k,t)から始めて勝つまでの期待台数とする.
f(k,t) = 1+P(000が出る)f(k,t)+P(500が出る)f(k,t+1)+P(k個のペアの既に出た番号が出る)f(k,t)+P(それ以外)f(k+1,t)
f(k,2) = 0
f(499,t) = 1+P(000が出る)f(499,t)+P(500が出る)f(499,t+1)+P(499個のペアの既に出た番号が出る)f(499,t)

これをf(499,1)から順に解いていってf(0,0)の値を求める.
f(499,1) = 1/{1-P(000が出る)-P(499個のペアの既に出た番号が出る)}
f(499,0) = {1+P(500が出る)f(499,1)}/{1-P(000が出る)-P(499個のペアの既に出た番号が出る)}
f(k,1) = {1+P(それ以外)f(k+1,t)}/{1-P(000が出る)-P(k個のペアの既に出た番号が出る)}
f(k,0) = {1+P(500が出る)f(k,1)+P(それ以外)f(k+1,0)}/{1-P(000が出る)-P(k個のペアの既に出た番号が出る)}

Project Euler 381

pを5以上の素数とする.

ウィルソンの定理より
$(p-1)! = -1 mod p$
$(p-2)! = (p-1)!(p-1)^(-1) = (-1)(-1)^{-1} = 1 mod p$
$(p-3)! = (p-2)!(p-2)^(-1) = -(2^{-1}) mod p$
$(p-4)! = (p-3)!(p-3)^(-1) = (2^{-1})(3^{-1}) mod p$
$(p-5)! = (p-4)!(p-4)^(-1) = -(2^{-1})(3^{-1})(4^{-1}) = -((2^{-1})^3)(3^{-1}) mod p$

p+1は偶数だから, 2^(-1) = (p+1)/2 mod p
p = 1 mod 3のときp=3m+1と表せるから, 3^(-1) = -m = -(p-1)/3
p = 2 mod 3のときp=3m+2と表せるから, 3^(-1) = m+1 = (p+1)/3

Project Euler 387

1〜12桁のright truncatable Harshad numberのリストを作って
そこからstrong Harshad numberであるものだけ取り出して
取り出したリストからstrong, right truncatable Harshad primeを作ればよい.

n桁のright truncatable Harshad numberはn-1桁のものの右端に一桁付け加えて作る.
strong, right truncatable Harshad primeはstrong, right truncatable Harshad numberの右端に一桁の奇数を付け加えて作る.

Project Euler 419

Look and Say Sequenceの性質であるCosmological Theoremを使う.

Conwayによると, Look and Say Sequenceの第8項以降の各項は92種類の基本元素に分割できて
基本元素の変化だけで, 全部の項が生成できる.
http://www.njohnston.ca/2010/10/a-derivation-of-conways-degree-71-look-and-say-polynomial/

例えば
第8項目の1113213211は11132と13211に分割できて, これ24番と39番に対応する.
24番の11132は83番の311312
39番の13211は9番の11131221
にそれぞれ変化して
第9項目の31131211131221 = (83番)(9番)になる.
83番の311312は45番の1321131112
9番の11131221は71番の3113112211
にそれぞれ変化して
第10項目の13211311123113112211=(45番)(71番)になる.
これ以降も同様にして基本元素の変化だけで表せる.

1の個数, 2の個数, 3の個数などは各基本元素の個数さえ分かれば順番は必要ないから
24番は1個の83番に遷移する
39番は1個の9番に遷移する
といった遷移の情報を持つ92行92列の遷移行列Mを作って, $M^{10^{12}-8}v$ を計算すればよい.
ただし, vは第8項の基本元素の個数を表現したベクトルで24番と39番が1個ずつある.

2015-10-30

Project Eulerのメモ

puzzle

Project Euler 151

A1の紙がa1枚, A2の紙がa2枚, ..., A5の紙がa5枚あるときから始めて, 封筒に紙が1枚だけ入っている回数の期待値を
$f(a_1,a_2,a_3,a_4,a_5)$ として漸化式を立てて, $f(1,0,0,0,0)$ を求める.
例えば紙の枚数が $(a_1,a_2,a_3,a_4,a_5)$ の日にA3の紙を手にとったら, 次の日の紙の枚数は $(a_1,a_2,a_3-1,a_4+1,a_5+1)$ になる.

Project Euler 158

左隣の文字より辞書順で後になる文字がちょうど1個
⇔
a,b,...,zを0,1,...,25に置き換えたとき
左隣の数より大きい数がちょうど1個
⇔
$a_1 \gt a_2 \gt \cdots \gt a_i \lt a_{i+1} \gt a_{i+2} \gt \cdots \gt a_n$
が成り立つこと
つまり

0,1,2,...,25からn個をとって
$a_1 \gt a_2 \gt \cdots \gt a_i \lt a_{i+1} \gt a_{i+2} \gt \cdots \gt a_n$ になるように2グループに分ける

仕方の数を数える.

高校の場合の数の問題に出てきそう.

Project Euler 169

2^0, ..., 2^kを2個ずつまで使ってsを作る組み合わせの個数を $f(k, s)$ として漸化式を立てて計算する.
$f(k,s) = f(k-1, s-2 \cdot 2^k) + f(k-1, s-1 \cdot 2^k) + f(k-1, s-0 \cdot 2^k)$
$f(k, s) = 0 \, (s < 0 \vee 2 \cdot (2^{k+1} - 1) < s)$

Project Euler 225

法mのもとでトリボナッチ数は循環するから循環するまで0が出てこない奇数を小さい順に列挙する.

Project Euler 239

包除原理. ちょうど3つの素数だけが正しい位置にある並びの個数を数える.

Project Euler 323

ガチャをコンプリートする回数の期待値の問題と同じ
nビットが立っている状態からスタートして32ビット全て立つまでのステップ数の期待値をE(n)とする.
漸化式を立てて, E(0)を求める.

Project Euler 435

$F_n(x)$ を閉じた式で表して, $F_n(x), F_{n-1}(x), F_{n-2}(x)$ の間の漸化式を立てて計算する.
コンパニオン行列を使って計算.

2015-10-26

組み合わせの個数を数える質問(yahoo知恵袋)

math

元の質問は, a,b,c,d,e,fの6文字から重複を許してn個選び,
選んだn個をそれぞれ2倍に複製した2n個を並べる並べ方の個数を求めたいとのこと.
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12151668017

例えば, n=3で最初に「aが1個とbが2個 (a,b,b)」が選ばれたら,
並べるときはそれぞれ2倍に複製してa,a,b,b,b,bを一列に並べる.

結論から書くと, n個選ぶときの並べ方の個数は
$3 \cdot 16^{n-1} + \left( 9^n-1 \right)/8 \cdot 4^{n-1} + 2^{2n-1}$
で求められる.
漸化式を立てて泥臭く求めたけれど, 以外に綺麗な形なので, エレガントな求め方がありそう.

数列A[i] = {a,b,c,d,e,f}として
A[1]=a,...,A[6]=fを表すとする.

f(n,k)でA[1],...,A[k]のk文字から重複を許してn個選んだときの並べ方の個数を表す.
つまり, f(n,6)の一般項を求めたい.

f(n,1) = 1
f(1,k) = k
はすぐ分かる.

また, A[1],...,A[k],A[k+1]のk+1文字から重複を許してn個選んだときの並べ方は
(1) n文字全部A[k+1]を選んだときの並び
(2) A[1],..,A[k]からm個選んでA[k+1]を(n-m)個選んだときの並び
(ただし, m=1,2,...,n)
に分けられる.

A[1],..,A[k]からm個選んでA[k+1]を(n-m)個選んだときの並びは
f(m,k)で数えた長さ2mの並びのそれぞれにA[k+1]を2(n-m)個挿入して作ることができる.
長さ2mの並びに2(n-m)個挿入する場合の数は ${_{2m+1}\mathrm{H}_{2(n-m)}} = {_{2n}\mathrm{C}_{2m}}$ 通りあるから
(1)の並びは1個
(2)の並びは各mに対して, ${_{2n}\mathrm{C}_{2m}} f(m,k)$ 個ずつある

よって並びの個数を求める漸化式は
$f(n,k+1) = 1 + \sum_{m=1}^{n} {_{2n}\mathrm{C}_{2m}} f(m,k)$
$f(n,1) = 1$
$f(1,k) = k$
となる

以下, ひたすらに一般項を計算する
$S(x)=\sum_{m=0}^{n}{_{2n}\mathrm{C}_{2m}} x^{2m}$ とすると,
$\left(1+x \right)^{2n} = \sum{m=0}^{n}{_{2n}\mathrm{C}_{2m}} x^{2m} + \sum{m=1}^{n}{_{2n}\mathrm{C}_{2m-1}} x^{2m-1}$
$\left(1-x \right)^{2n} = \sum{m=0}^{n}{_{2n}\mathrm{C}_{2m}} x^{2m} - \sum{m=1}^{n}{_{2n}\mathrm{C}_{2m-1}} x^{2m-1}$
より
$S(x) = \frac{(1+x)^{2n}+(1-x)^{2n}}{2}$
と表せる.

$f(n,2) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,1) = S(1) = 2^{2n-1}$
$f(n,3) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,2) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} 2^{2m-1} = \frac{1}{2} \left( 1 + S(2) \right) = \frac{1}{2} \left( 3^{2n}+3 \right)$
$f(n,4) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,3) = \frac{1}{4} \left(S(3) + 3S(1) \right) = \frac{1}{8} \left(4^{2n} + 4 \cdot 2^{2n} \right)$
$f(n,5) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,4) = \frac{1}{8} \left(S(4) + 4S(2) + 3 \right) = \frac{1}{16} \left(5^{2n} + 5 \cdot 3^{2n} + 10 \right)$
$f(n,6) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,5) = \frac{1}{16} \left(S(5) + 5S(3) + 10S(1) \right) = \frac{1}{32} \left(6^{2n}+6 \cdot 4^{2n} + 15 \cdot 2^{2n} \right)$
最後の式を整理して最初に書いた一般項が得られる.

次のf(n,7)は
(1/32)(S(6)+6S(4)+15S(2)+ 定数)という形だろうし, うまい規則がありそう.

2015-10-11

Maximaで巡回行列を作る.

math programming

$\left(\begin{array}{ccccc}1 & 2 & \ldots & n-1 & n \\2 & 3 & \ldots & n & 1 \\\vdots & \vdots & \ddots & \vdots & \vdots \\n & 1 & \ldots & n-2 & n-1\end{array}\right)$

を作る

f(n):=genmatrix(lambda([i,j],mod(i+j-2,n)+1),n,n);

ちなみに行列式は
$(-1)^{\frac{n(n+1)}{2}} (n^{n-1}) \frac{n+1}{2}$

2015-09-11

ProjectEuler 162

puzzle

包除原理の例題みたいな問題。

先頭から続く0は無視することだけ注意すればよい。

n桁の16進数xの個数は15*16^n個
f(prop) = 条件propを満たすn桁の16進数の個数
とすると

f(0を含む & 1を含む & Aを含む) = 15*16^n - f(0を含まない | 1を含まない | Aを含まない)]

包除原理より
f(0を含まない | 1を含まない | Aを含まない)=f(0を含まない)+f(1を含まない)+f(Aを含まない)
-f(0を含まない & 1を含まない)-f(1を含まない & Aを含まない)-f(Aを含まない & 0を含まない)
+f(0を含まない & 1を含まない & Aを含まない)

それぞれ
f(0を含まない) = 15^n
f(1を含まない) = f(Aを含まない) = 14*15^(n-1)
f(0を含まない & 1を含まない) = f(Aを含まない & 0を含まない) = 14^n
f(1を含まない & Aを含まない) = 13*14^(n-1)
f(0を含まない & 1を含まない & Aを含まない) = 13^n

したがって
f(0を含まない | 1を含まない | Aを含まない) = 15^n+2*14*15^(n-1)-2*14^n-13*14^(n-1)+13^n
f(0を含む & 1を含む & Aを含む) = 15*16^(n-1)-43*15^(n-1)+41*14^(n-1)-13^n