約数関数

約数関数（やくすうかんすう、英: divisor function）は、自然数 n を変数とする関数で、n の全ての約数を整数乗した数の総和を値にとるものである。 自然数 n に対して、約数関数 σx(n) とは、n の約数 d の x 乗和を値に取る関数である： σ x ( n ) = ∑ d | n d x {\displaystyle \sigma _{x}(n)=\textstyle \sum \limits _{d|n}d^{x}} 特に、x = 0 のとき σ0(n) は n の約数の個数を表し、d(n) や τ(n) と表されることもある。x = 1 のとき σ1(n) は n の約数の総和であり、単に省略して σ(n) と表す場合もある。 また、約数関数 σx(n) のk階反復を σ x k ( n ) := σ x ( ⋯ ( σ x ⏟ k ( n ) ⋯ ) {\displaystyle {\sigma _{x}}^{k}(n):=\underbrace {\sigma _{x}(\cdots (\sigma _{x}} _{k}(n)\cdots )} と書く。例えば σ x 2 ( n ) = σ x ( σ x ( n ) ) , σ x 3 ( n ) = σ x ( σ x ( σ x ( n ) ) ) {\displaystyle {\sigma _{x}}^{2}(n)=\sigma _{x}(\sigma _{x}(n)),\quad {\sigma _{x}}^{3}(n)=\sigma _{x}(\sigma _{x}(\sigma _{x}(n)))} である。 k = 1 、x = 1 のときはどちらもそれぞれ省略して、σ(n) = σ1(n)（k=x=1の場合）、σ2(n)（k=2,x=1の場合）などと表記する場合もある。 σ0(n) の値は、小さい順に次のようになる： 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4 …（オンライン整数列大辞典の数列 A000005） σ1(n) の値は、小さい順に次のようになる： 1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24 …（オンライン整数列大辞典の数列 A000203） σ2(n) の値は、小さい順に次のようになる： 1, 5, 10, 21, 26, 50, 50, 85, 91, 130, 122, 210, 170, 250, 260 …（オンライン整数列大辞典の数列 A001157） 例えば n = 15 では、 d(15) = σ0(15) = 10 + 30 + 50 + 150 = 4, σ(15) = σ1(15) = 11 + 31 + 51 + 151 = 24, σ2(15) = 12 + 32 + 52 + 152 = 260 p を素数とすると、p の約数は 1 と p の 2個のみであるから d(p) = 2, σ(p) = p + 1 となる。また、n を自然数とすると、pn の約数は 1, p, p2, …, pn の n + 1個なので d(pn) = n + 1, σ(pn) = (pn+1 − 1)/(p − 1) となる。 d(n) および σ(n) は n = 1 のとき最小値 1 をとる。d(n) = n の解は n = 1, 2 の 2 個のみであり、σ(n) = n の解や d(n) = σ(n) の解は n = 1 のみである。n ≥ 3 では 2 ≤ d(n) < n < σ(n) が成り立つ。 約数関数 σx(n) は乗法的関数（英: Multiplicative function）であるが、完全乗法的関数（英語版）ではない。 gcd ( a , b ) = 1 ⟹ σ x ( a b ) = σ x ( a ) σ x ( b ) . {\displaystyle \gcd(a,b)=1\Longrightarrow \sigma _{x}(ab)=\sigma _{x}(a)\sigma _{x}(b).} n を素因数分解して以下の式の形で表す。 n = ∏ i = 1 r p i a i {\displaystyle n=\textstyle \prod \limits _{i=1}^{r}{p_{i}}^{a_{i}}} ここで r は n の素因子の個数、pi はその中で i 番目に小さい素因子、ai は素因数分解で現れる各素因子の指数部である。ここから σ x ( n ) = ∏ i = 1 r p i ( a i + 1 ) x − 1 p i x − 1 ( x ≠ 0 ) {\displaystyle \sigma _{x}(n)=\textstyle \prod \limits _{i=1}^{r}{\frac {{p_{i}}^{(a_{i}+1)x}-1}{{p_{i}}^{x}-1}}\quad (x\neq 0)} が導かれる。これは σ x ( n ) = ∏ i = 1 r ∑ j = 0 a i p i j x = ∏ i = 1 r ( 1 + p i x + p i 2 x + ⋯ + p i a i x ) {\displaystyle \sigma _{x}(n)=\textstyle \prod \limits _{i=1}^{r}\sum \limits _{j=0}^{a_{i}}{p_{i}}^{jx}=\prod \limits _{i=1}^{r}(1+{p_{i}}^{x}+{p_{i}}^{2x}+\cdots +{p_{i}}^{a_{i}x})} と同値である。x = 0 のときは σ 0 ( n ) ≡ d ( n ) = ∏ i = 1 r ( a i + 1 ) {\displaystyle \sigma _{0}(n)\equiv d(n)=\textstyle \prod \limits _{i=1}^{r}(a_{i}+1)} となる。例えば n = pq （p, q は素数）とすると、σ(n) = (1 + p)(1 + q) = n + p + q + 1, d(n)=(1 + 1)(1 + 1) = 4 となる。 約数関数から導き出される数列 a n = σ ( a n − 1 ) {\displaystyle a_{n}=\sigma (a_{n-1})} はその初期値によって異なる発散の仕方をする。( a1 = 1 を除く) 例. a1 = 2 のとき 2, 3, 4, 7, 8, 15, 24, 60, 168, 480, … (オンライン整数列大辞典の数列 A007497) a1 = 5 のとき 5, 6, 12, 28, 56, 120, 360, 1170, 3276, … (オンライン整数列大辞典の数列 A051572) a1 = 16 のとき 16, 31, 32, 63, 104, 210, 576, 1651, 1792, … (オンライン整数列大辞典の数列 A257349) この初期値は 2, 5, 16, 19, 27, 29, 33, 49, 50, 52, 66, 81, 85, 105,… (オンライン整数列大辞典の数列 A257348) オイラーは約数関数が以下のように表されることを示した。 　　 σ 1 ( n ) = σ 1 ( n − 1 ) + σ 1 ( n − 2 ) − σ 1 ( n − 5 ) − σ 1 ( n − 7 ) + σ 1 ( n − 12 ) + σ 1 ( n − 15 ) − . . . = ∑ i = 1 ∞ ( − 1 ) i + 1 ( σ 1 ( n − 1 2 ( 3 i 2 − i ) ) + σ 1 ( n − 1 2 ( 3 i 2 + i ) ) ) {\displaystyle {\begin{aligned}\sigma _{1}(n)&=\sigma _{1}(n-1)+\sigma _{1}(n-2)-\sigma _{1}(n-5)-\sigma _{1}(n-7)+\sigma _{1}(n-12)+\sigma _{1}(n-15)-...\\&=\sum _{i=1}^{\infty }{(-1)^{i+1}}\left(\sigma _{1}\left(n-{\frac {1}{2}}(3i^{2}-i)\right)+\sigma _{1}\left(n-{\frac {1}{2}}(3i^{2}+i)\right)\right)\end{aligned}}} なおこの数式で、 n < 0 {\displaystyle n<0} のとき σ 1 ( n ) = 0 {\displaystyle \sigma _{1}(n)=0} とし、 σ 1 ( 0 ) = n {\displaystyle \sigma _{1}(0)=n} とする。 約数関数の母関数はランベルト級数（英語版）である。 ∑ n = 1 ∞ n a x n 1 − x n = ∑ n = 1 ∞ ∑ m = 1 ∞ n a x m n = ∑ n = 1 ∞ x n σ a ( n ) {\displaystyle \sum _{n=1}^{\infty }{\frac {n^{a}x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }\sum _{m=1}^{\infty }n^{a}x^{m\,n}=\sum _{n=1}^{\infty }x^{n}\sigma _{a}(n)} 約数関数は以下の三角関数を用いた式で表すこともできる。 σ x ( n ) = ∑ μ = 1 n μ x − 1 ∑ ν = 1 μ cos ⁡ 2 π ν n μ {\displaystyle \sigma _{x}(n)=\sum _{\mu =1}^{n}\mu ^{x-1}\sum _{\nu =1}^{\mu }\cos {\frac {2\pi \nu n}{\mu }}} またゼータ関数 ζ(s) とは ∑ n = 1 ∞ σ a ( n ) n s = ζ ( s ) ζ ( s − a ) {\displaystyle \sum _{n=1}^{\infty }{\frac {\sigma _{a}(n)}{n^{s}}}=\zeta (s)\zeta (s-a)} という関係式をもつ。 σ(n)の増加の割合は以下の式で表される。 lim sup n → ∞ σ ( n ) n   log ⁡ log ⁡ n = e γ {\displaystyle \limsup _{n\rightarrow \infty }{\frac {\sigma (n)}{n\ \log \log n}}=e^{\gamma }} γ はオイラー定数である。 また、d(n)の増加の割合は以下の式で表される。 lim sup n → ∞ log ⁡ d ( n ) log ⁡ log ⁡ n log ⁡ n = log ⁡ 2 {\displaystyle \limsup _{n\rightarrow \infty }{\frac {\log d(n)\log \log n}{\log n}}=\log 2} 実際、左辺の上極限記号内の分数の値が最大となるのは n = 6983776800 {\displaystyle n=6983776800} のときで、その値は 1.0660186 … {\displaystyle 1.0660186\ldots } であることが知られている。 特に、任意の ε > 0 に対して、d(n) = o(nε) が成り立つ。 σ ( n ) < e γ n log ⁡ log ⁡ n {\displaystyle \sigma (n)<e^{\gamma }n\log \log n\,} 　(n > 5040) が真であるならリーマン予想も真であることが証明されている。つまりこの不等式を満たさない最大の数が 5040 であり、5041 以上の全ての自然数がこの不等式を満たすならばリーマン予想は真である。もしリーマン予想が偽ならこの不等式を満たさない n は無数に存在する。 x=0～21についてのσx(n)の値はオンライン整数列大辞典に数列として掲載されている。 σ(n) < 2n を満たす n を不足数、σ(n) = 2n を満たす n を完全数、σ(n) > 2n を満たす n を過剰数という。 6, 28, 496 などが完全数として知られている。偶数の完全数全体はメルセンヌ素数 2p − 1 に対して 2p−1(2p − 1) と表されるもの全体と一致することが知られている。奇数の完全数が存在するかどうかは古くからの数論の未解決問題として有名である。 完全数が 2n−1 × (2n − 1) で表せることからある数 n とその約数の和 σ(n) との積が完全数となる場合がある。この完全数を含む n × σ(n) の数列は 1, 6, 12, 28, 30, 72, 56, 120, 117, 180, 132, 336, 182, 336, 360, 496, …である。(オンライン整数列大辞典の数列 A064987) このほかにも、約数関数、特に約数の和の関数 σ(n) の値に関しては多くの概念が考察され、多くの未解決問題が提示されている。いくつかの例を挙げる。 σ(n) = 2n − 1 を満たす n を概完全数といい、σ(n) = 2n + 1 を満たす n を準完全数という。概完全数は 2 の累乗（1 も含む）が知られているが、それ以外に存在するかどうか知られていない。準完全数は存在するかどうか未だに分かっていない。準完全数が存在するならば、それは奇数の平方数でなければならないことが知られている。 σ(n) = kn (k:整数) を満たす n を k-倍完全数という。例えば 120 は3倍完全数である。現在知られている倍積完全数は n = 1(このとき、k = 1)を除いて全て偶数である。1 以外に奇数の倍積完全数が存在するか否かは知られていない。 σ(σ(n)) = 2n を満たす n を超完全数という。偶数の超完全数はメルセンヌ素数 2p − 1 に対して、2p−1 と表されるもの全体と一致することが知られている。奇数の超完全数が存在するか否かは知られていない。奇数の超完全数が存在するならば、それは平方数で少なくとも2つの相異なる素因数を持たなければならないことが知られている。 超完全数は 2, 4, 16, 64, 4096, 65536, 262144,…である。 (オンライン整数列大辞典の数列 A019279) σ(n) = σ(m) = n + m を満たす相異なる数 n, m の組を友愛数という。(n, m) = (220, 284)などがそれである。友愛数が無限に存在するか否かは知られていない。 それと対照的に、 σ(n) = σ(m) = n + m + 1 を満たす相異なる数 n, m の組を婚約数という。(n, m) = (140, 195)などがそれである。婚約数は無限に存在するか否かは証明されていない。 d(n) = d(n + 1) を満たす n は無数に存在することが証明されている。 (例 : n = 2, 14, 21, 26, 33, 34, ･･･(オンライン整数列大辞典の数列 A005237)) d(n) = d(n + 1) = d(n + 2) を満たす n は33, 85, 93, 141, 201, 213, 217, 230, …である。(オンライン整数列大辞典の数列 A005238)中央の数の数列はオンライン整数列大辞典の数列 A169834を参照。 d(n) = d(n + 1) = d(n + 2) = d(n + 3) を満たす n は242, 3655, 4503, 5943, 6853, 7256, …である。(オンライン整数列大辞典の数列 A006601) 5連続で約数の個数が同じ数の最初の数は 11605, 12855, 13782, 19142, 21494, 28374,…である。(オンライン整数列大辞典の数列 A049051) 6連続で約数の個数が同じ数の最初の数は 28374, 90181, 157493, 171893, 171894,…である。(オンライン整数列大辞典の数列 A049052) 7連続で約数の個数が同じ数の最初の数は 171893, 180965, 647381,…である。(オンライン整数列大辞典の数列 A049053) 約数の個数が同じ連続整数の最初の数は 1, 2, 33, 242, 11605, 28374, 171893, 1043710445721, 2197379769820 (オンライン整数列大辞典の数列 A006558)、9連続整数まであることが知られている。 ゼータ関数 リーマン予想 不足数-完全数-過剰数 友愛数