PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 164 / 連続3桁の和は9以下

どの連続した3桁の和も9以下のような20桁の数(先頭は0ではない)はくつあるか?

Problem 164 - Project Euler


たとえば123の次の桁には0~4が続きますが,これを「下2桁が23の数から下2桁が30, 31, 32, 33, 34の数ができる」ととらえて連立漸化式にもちこむと,何十個もの数列が必要になります。そこで,軽くグラフ理論を使ってみました。

まず和が9以下の3つの数の組を作ります(myList1)。たとえば{1, 2, 3}という組ができますが,これを
「12の後に3が続いてよい」=「12から23ができる」
ととらえて有向グラフの種 {12→23} を作ります(myList2)。

一応図示してみますが,頂点が55個と多すぎてよくわかりません。

f:id:variee:20170426011010p:plain

myList2 を隣接行列 m に直して,行列の積で処理します。


題意をみたす数はこの行列の成分の和として求められます。ただし,最初の10行は00~09からはじまる数に対応しているので除かないといけません。

m は3桁の数の個数を与え,m^2 は4桁の数の個数を与え,……なので20桁の数なら m^18 を考えればいいことになります。

以上をまとめたものがこちらです。グラフを経由して漸化式を処理するとは自分でも意外でした。