エイドリアンさんが、No.80806 - 2022/02/08(Tue)で質問された問題です。
実験したところ、スッキリした式になりそうですが、いろいろ考えましたがうまい解法が見つかりません。
視点を変えると目から鱗のような問題かなと思いますので、少し表現を変えて再掲させてもらいます。
予測が正しければネットで見つかりそうですが見当たりません。何かヒントでも頂ければ嬉しいです。
（問題）らすかるさんの指摘で補正しました。
自然数nが与えられたとき
既約分数p/q（p,q は互いに素な自然数)で、0＜p/q＜1かつn/q の小数部が0.5以上になるようなものの個数をnで表せ。
n=1,2,3,...,13 について計算したところ n^2 個になります。
例えば、n=5 のとき
q=2,3 と 5+1=6≦q≦5*2=10 が条件を満たします。
それぞれのqについてp/qが既約分数となるpの個数は
qと互いに素なq以下の自然数の個数ですから、
求める既約分数の個数は1+2+2+6+4+6+4=25=5^2 個となります。
任意の自然数nについてもn^2個になるでしょうか？
（元の質問）
https://www2.rocketbbs.com/11/bbs.cgi?id=yosshy&mode=res&resto=80806
|
No.80942 - 2022/02/16(Wed) 00:08:47
| ☆ Re: 既約分数の個数 / らすかる | | | とりあえずプログラムを作って調べたところ、n≦3000では成り立っていました。
よって確かに成り立つようなので少し考えてみたのですが、着眼点の見当がつかず…
# ところで、「既約分数p/q」ですとp=q+1やp=2q+1なども含んで無限個になって
# しまいますので、p＜qあるいはp/q＜1などと書いておいた方が良いと思います。
|
No.80943 - 2022/02/16(Wed) 03:00:47 |
| ☆ Re: 既約分数の個数 / IT | | | らすかるさん 回答ありがとうございます。
条件p/q＜1を書き洩らしていました。（原題では0≦p/q≦1)
(p,q)をプロットして、縦横斜めに見てみましたが、n^2個になる理由がなかなか見つかりません。
|
No.80944 - 2022/02/16(Wed) 07:04:38 |
| ☆ Re: 既約分数の個数 / IT | | | ネットで下記の公式を見つけました。これを使って解決しました。
（公式）自然数nについてΣ(k=1,n)[n/k]φ(k)=n(n+1)/2 （φ(k)はオイラーのトーシェント関数、[ ]はガウス記号）
φ(k)：自然数k に対して、1 から k までの自然数のうち k と互いに素なものの個数
（証明）
n×nの表{A(i,k)}(1≦i,k≦n)を考える。
kがiの約数のとき A(i,k)=Φ(k),その他は0とします。
縦（列）の計、横（行）の計を考えると
Σ(i=1,n)A(i,k)=[n/k]Φ(k)
Σ(k=1,n)A(i,k)=i
{A(i,k)}全体の和はΣ(k=1,n)[n/k]Φ(k)=Σ(i=1,n)i=n(n+1)/2
|
No.80949 - 2022/02/16(Wed) 20:14:55 |
| ☆ Re: 既約分数の個数 / IT | | | 1≦q≦nについて
[2n/q]-2[n/q]は、
n/q の小数部が0.5以上のとき ＝1、それ以外のとき ＝0となります。
したがって、
Σ(q=1,n){[2n/q]φ(q)-2[n/q]φ(q)}は、
1≦q≦nのうちn/q の小数部が0.5以上となるqを分母とする１以下の既約分数の個数となります。
よって、元の問題の条件を満たす既約分数の個数は
Σ(q=1,n){[2n/q]φ(q)-2[n/q]φ(q)}+Σ(q=n+1,2n)φ(q)
=Σ(q=1,2n)[2n/q]φ(q)-2Σ(q=1,n)[n/q]φ(q)
(公式より)
=2n(2n+1)/2-2n(n+1)/2
=n^2
|
No.80951 - 2022/02/16(Wed) 20:42:46 |
|
