Problem 203

まず例として8列目までのパスカルの三角形を考える.

              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
1  7   21  35   35  21   7   1

ここには12個の異なる整数1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35が含まれる.
任意の素数の二乗がある整数nを割り切らないとき,その数をsquarefreeであると呼ぶ.
今挙げた12個の整数の中でsquarefreeでない数は4と20だけであり,squarefreeな数の合計は105となる.
51列目までのパスカルの三角形に含まれる整数のうち,squarefreeな数の合計を求めよ.
(gmpのおかげで)簡単だった.420ms.
といっても51列目までのパスカルの三角形なんて51 * 51のmatrixに格納できるし,無駄な分含めたって要素数は2601しかないし,これといって難しい点はない.素直にやって解ける.

library(gmp)
## make Pascal's triangle
pascal.tri <- function(n){
  m <- matrix(0, nrow=n, ncol=n)
  m[,1] <- 1
  for(i in 2:n){
    m[i, 2:n] <- m[i-1, 1:(n-1)] + m[i-1, 2:n]
  }
  return(m)
}

## sum of squarefree nums
sum.squarefree <- function(n){
  r <- unique(as.vector(pascal.tri(n)))
  r <- r[r != 0]
  sum.sq <- 0
  for(i in r){
    if(all.equal(unique(table(as.numeric(factorize(i)))), 1) == TRUE)
      sum.sq <- sum.sq + i
  }
  return(sum.sq + 1)
}
as.character(sum.squarefree(51))