まず例として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))