ハミング数とは5を超える素因数を持たない正整数のことである.
小さい方からいくつか示すと,1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15...がハミング数である.
10^8未満の正整数のうちハミング数は1105個ある.正整数のうち,nを超える素因数を持たないような数のことをタイプnの一般化ハミング数と呼ぶことにしよう.
よって,上述のハミング数はタイプ5の一般化ハミング数である.10^9未満の正整数のうち,タイプ100の一般化ハミング数はいくつあるか.
1分30秒.
## list of prime numbers limit <- 100 slimit <- sqrt(limit) sieve <- logical(limit) sieve[1] <- TRUE sieve[seq(4, limit, 2)] <- TRUE for(i in seq(3, slimit, 2)) if(!sieve[i]) sieve[seq(i*2, limit, i)] <- TRUE plist <- (1:limit)[!sieve] ## count generalised Hamming numbers of type 100 limit <- 1e9 pll <- length(plist) count <- 1 countham <- function(n = 1, i = 1){ if(n >= limit) return(0) count <<- count + 1 for(j in i:pll) Recall(n*plist[j], j) return(0) } countham() count