Problem 148 - もうカツ丼はいいよな

Problem 148 - Project Euler

パスカルの三角形の最初の7行に含まれる数のなかに7で割り切れるものが無いことは簡単に確認できる。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
しかし、最初の100行まで調べると、5050ある数のうち7で割り切れない数は2361個しかない。
パスカルの三角形の最初の10億( $10^9$ )行までに含まれる数のうち、7で割り切れない数はいくつあるか。

パスカルの三角形について、2で割り切れる数を白、そうでないものを黒で塗りつぶすとシェルピンスキーのギャスケットと呼ばれる図形が得られる(cf. シェルピンスキーのギャスケット - Wikipedia)。
同様に、ある整数nで割り切れる数を白、割り切れない数を黒として塗り分けてもシェルピンスキーのギャスケットのような自己相似的な図形が得られる。
このとき、1つの三角形にそれより1段階だけ小さい、中が空でない三角形は $\sum_{i=1}^{n}i$ 個だけ含まれる。
今回はn=7だから、1+2+3+4+5+6+7=28を基本単位とした繰り返し図形が得られる。
パスカルの三角形の最初の1000行について7で割った余りを元に塗り分けをし、Rでプロットしたものを次に示す(ちなみに始点は左下で、下の方に寄った形になっている)。黒い部分が0で割り切れる値に相当する。

ここに見える三角形に含まれる7で割り切れない数の個数を数える時、三角形が完全な形をしていれば苦労はない。問題は右はじの微妙な部分にある。
ここでプロットのx軸近辺に注目すると、7を基本単位とした繰り返しが見えてくるだろう。
そこで1000を7進数展開すると、2626になる。
そしてx軸に沿って三角形を数えると、最大のものが2個、その次の大きさのものが6個、その次の大きさのものが2個、その次の大きさのもの(数1つに対応)が6個であることがわかる(最後のは見えないかもしれないが)。すなわち、7進数展開により三角形の個数が数えられる。
この辺からちょっと分かりにくくなるが、まず右端、一番小さい三角形から数えよう。
右端には(1+2+3+4+5+6)個の数を含む半端なサイズの三角形が沢山くっついている。そして、その半端なサイズの三角形は、(2+1) * (6+1) * (2+1)個ある。
同様に(1+2)個の二番目に小さな三角形(数28個からなる)を含む半端なサイズの三角形が右端にくっついている。
同様に…
と、言葉で説明するとどうしたって分かりにくいのでRのコードで書く。

# 1000を7進数展開すると2626
# 1000行のパスカルの三角形に含まれる7で割り切れない数は…
(28^0)*sum(1:6) * (2+1) * (6+1) * (2+1) + 
(28^1)*sum(1:2) * (6+1) * (2+1) +
(28^2)*sum(1:6) * (2+1) +
(28^3)*sum(1:2)

とまあこんな感じに7進数展開した数から答が求められる。7進数展開する関数と、上に示した規則通りに式を作る関数を用意すればおしまい。

to.sep.d <- function(n){
  sep <- 0
  pow <- 0
  while(n > 0){
    sep <- sep + (10^pow * n %% 7)
    pow <- pow + 1
    n <- n %/% 7
  }
  sep
}
count <- function(n){
  sep <- rev(as.numeric(unlist((strsplit(as.character(to.sep.d(n)), "")))))
  ans <- 0
  for(i in 1:(length(sep)-1)){
    if(sep[i] == 0) next
    ans <- ans + (28^(i-1)) * sum(1:sep[i]) * prod(sep[(i+1):length(sep)] + 1)
  }
  ans + 28^(length(sep)-1) * sum(1:sep[length(sep)])
}
as.character(count(1e9))