Rでオイラーのφ関数の列挙

自然数nに対して、1からnまでの自然数の中でnと互いに素であるものの個数をで与えることとしたとき、このをオイラーのφ関数(オイラーのトーシェント関数：Euler's totient function)と呼ぶ(cf.オイラーのφ関数 - Wikipedia)。
具体的にの値を1から10まで求めると以下のようになる。

• 
• 
• 
• 
• 
• 
• 
• 
• 
• 

Wikipediaの記述そのままだが、性質としては以下の様なものがある。

• pを素数とした時、
• 
• 互いに素である2数m、nについて、である
• 以上の性質より、nの素因数分解が
  • 
• と与えられているとき、
  • 

つまり、nとnに含まれる素因数が分かればを求めることができる。nに対し、全ての素因数について(p-1)/pを掛けていけば良い。1からnまでの全ての値で試し割りする必要はない。
一つの値について求めたいのであれば、gmpパッケージのfactorizeを使って以下のようにすれば簡単に求められる。

library(gmp)
euler.phi <- function(n){
  p <- unique(as.numeric(factorize(n)))
  n * prod((p - 1)/p)
}

10まで求めてみると

> sapply(1:10, euler.phi)
 [1] 1 1 2 2 4 2 6 4 6 4

一つ一つではなく、リストとして欲しい場合があるだろう。上述のように、nをベースとして(p-1)/pをかけて行けば良いのだから、エラトステネスの篩を使えばよい。

limit <- 1e4
# eulerのphi関数の列挙
phi <- 1:limit
for(p in 2:limit){
  if(phi[p] == p){                      # pが素数のとき
    phi[seq(p, limit, p)] <-            # pの倍数に対して
      phi[seq(p, limit, p)] * (p-1)/p   # (p-1)/pを掛ける
  }
}

プロットするとこんな感じである。

なお、プロットにあたってはhttp://kosukebp.blogspot.jp/2011/12/blog-post_06.htmlで知ったdensColsを使った。