互いに素な数を数える (3)

間が空いてしまいました。こういうその場の思いつきでやってみただけの話は一気に書かないと、だんだんやる気が薄れてきますね。

復習

こんな記号を定義したのでした。U は Unit の頭文字をとってます。

$U(n) = \{x \mid 0 < x < n,\; \gcd(n, x)\}$
$U(n, d, i) = \{x \mid in/d < x < (i+1)n/d,\; \gcd(n, x) = 1\}$

で $| U(n, d, i) |$ をどうやったら求められますか、という問題でした。

d = 2 のときと、d = 3 で n が素数のときを前にやりました。今回は、それよりは少し難しいけどそこそこ簡単なケースをやってみます。

d = 3 かつ n が 4 で割り切れる場合

n = 4k とすると、なんかこんな感じになってます。

$0 \overbrace{ < \cdots < }^{|U(2k, 3, 0)|} {2k \over 3} \overbrace { < \cdots < }^{|U(2k, 3, 1)|} {4k \over 3} \overbrace{ < \cdots < }^{|U(2k, 3, 2)|} 2k \cdots$

もっと伸ばしてみると

$0 \underbrace{\overbrace{ < \cdots < }^{|U(2k, 3, 0)|} {2k \over 3} \overbrace { < \cdots < }^{|U(2k, 3, 1)|}}_{U(4k, 3, 0)} {4k \over 3}$
$\qquad \underbrace{\overbrace{ < \cdots < }^{|U(2k, 3, 2)|} 2k \overbrace{ < \cdots < }^{|U(2k, 3, 3)|}}_{U(4k, 3, 1)} {8k \over 3}$
$\qquad \qquad \underbrace{\overbrace { < \cdots < }^{|U(2k, 3, 4)|} {10k \over 3} \overbrace{ < \cdots < }^{|U(2k, 3, 5)|}}_{U(4k, 3, 2)} 4k = n \cdots$