ryamadaのコンピュータ・数学メモ

2019-12-01

素数とベン図

素数ベン図

自然数 n 種類が作る $2^n$ カテゴリを２次元平面の領域分割として表す方法がベン図
どんなnでもうまい方法が見つかる(見つけやすい)わけではなく、素数はうまい方法があるという(こちら)
まず、nが素数の場合、 $2^n-2=2(2^{n-1}-1)$ がnで割り切れるという。

library(primes)

n <- 1:100
p <- which(is_prime(n)) # 素数はどれ？
n. <- n[p]
N <- 2^n
N. <- 2^n.
a <- (N-2)/n
a. <- (N.-2)/n.

my.is.integer <- function(a,k=-10){ # 整数かどうかを判定する関数
	(abs(a)-floor(abs(a))) < 10^k
}

all(my.is.integer(a))
all(my.is.integer(a.)) # 素数の場合はそろって整数

$2^n-1$ と素数の関係には別の側面もあって、メルセンヌ数と言うのがあって、その中には素数が結構、含まれることが知られている。ちなみに $2^n-1$ が素数のとき、nも素数だという。ただし素数nに対して $2^n-1$ が素数であるとは限らない
さて、この $2^n-2$ をn等分した数は、 $2^n$ 通りの場合のうちの全0,全1を除いた場合の $1\n$ 画分になる
その画分をポセットにすることが、ベン図の描き方の発見に利用されるという
実際、その画分の要素数は、nからi個を取る場合をn等分したものを足し合わせたものとなるので、 $\sum_{i=1}^{n-1} \begin{pmatrix} n \\ i \end{pmatrix}/n$ と分けられる
ベン図表示の検出にあたっては、このように分けるn対称な取り合わせを構成することを通じて行う。そのような取り合わせはGreene-Kleitman successor ruleというもので発見できるらしい(こちら)