失礼いたします。
知人から数年前に教わったのですが、知人も私もなぜこうなるなのか今に至るまで全くわかりません。どうか理由を御教示くださいませ。もしくは反例をご教示ください。
m, n をともに非負整数とします。
p を正の奇数とします。
二変数関数 f を以下のように定めます。
f(m, n) = m(n +2) +((n +2)(n +3))/2
例えば p を 15 とします。
( * を乗法記号とします。 )
f(6, 0) = 6*(0 +2) +((0 +2)*(0 +3))/2 = 15
f(3, 1) = 3*(1 +2) +((1 +2)*(1 +3))/2 = 15
f(0, 3) = 0*(3 +2) +((3 +2)*(3 +3))/2 = 15
ですので
p = 15 = f(m, n)
となるような m, n の組み合わせは 3通りあるわけです。
さて、p = f(m, n)となるような m, n の組み合わせの個数を F(p) とします。
F(15) = 3
ということになります。
理由がわからず不思議なのですが、
F(p) = 1
ならば、 p は素数のようなのです。
理由もしくは反例についてご教示を頂ければと存じます。
|
No.69051 - 2020/08/16(Sun) 22:52:42
| ☆ Re: 謎いのでご教示ください / IT | | | 正しいですね。対偶が正しいことを示します。
正の奇数pが合成数のとき,pの最小の素因数をqとすると、
p=qr,3≦q≦r,(q,rは奇数)とおける。
このとき(p-3)/2,r-(q+1)/2は非負整数, q-2≧1である。
f((p-3)/2,0)＝p､f(r-(q+1)/2,q-2)=p なので
F(p)≧2となる。
# (m,n)=((p-3)/2,0),(r-(q+1)/2,q-2)は天下り的に書いていますが、
m(n+2)+((n+2)(n+3))/2=(m+(n+3)/2)(n+2)=qr をにらみつけて見つけたものです。
F(1)＝0も示す必要がありました。
これは,f(0,0)=3 で f(m,n) がm､nについて増加関数であることから言えますね。
|
No.69052 - 2020/08/16(Sun) 23:45:11 |
| ☆ Re: 謎いのでご教示ください / WIZ | | | 本質問の回答ではないですが、p が奇素数なら F(p) = 1 であることが示せます。
m, n を非負整数、p を奇数である自然数の素数とします。
n+2 > 0 なので、
m(n+2)+(n+2)(n+3)/2 = p
⇒ m = p/(n+2)-(n+3)/2
となります。
(1)
n が奇数であると仮定すると、(n+3)/2 が整数なので、p/(n+2) も整数でなくてはなりません。
p は素数で、n+2 は 1 より大きい p の約数だから、p = n+2 となることが必要です。
よって、m = 1-(n+3)/2 < 1-(1+3)/2 < 0 となって不合理です。
(2)
n が偶数であると仮定すると、ある非負整数 a が存在して、n = 2a とおけます。
m = p/(2a+2)-(2a+3)/2 = (1/2)(p/(a+1)+2a+3)
⇒ 2m = p/(a+1)-2a-3
上記から、p/(a+1) は整数でなければなりません。
(2A)
a+1 = p つまり a = p-1 の場合、
2m = p/p-2(p-1)-3 = -2p < 0
となって不合理です。
(2B)
a+1 = 1 つまり a = 0 の場合、
2m = p/1-2*0-3 = p-3
⇒ m = (p-3)/2, n = 2*0 = 0
以上から、p が奇素数なら f(m, n) = p の解は m = (p-3)/2, n = 0 の1通りしかなく、F(p) = 1 と言えます。
|
No.69067 - 2020/08/17(Mon) 19:29:53 |
| ☆ Re: 謎いのでご教示ください / IT | | | p が奇素数なら F(p) = 1 であることの、少し書き方が違う証明。
pを奇素数とします。
m, n を非負整数でp=f(m,n)とすると、
p=m(n+2)+((n+2)(n+3))/2=(m+(n+3)/2)(n+2)
nが奇数のとき
nは1以上で、m+(n+3)/2 は2以上の整数、n+2は3以上の整数なのでpは合成数となり不適。
nが偶数のとき
n=2k(kは非負整数)とおける。
p=(m+(2k+3)/2)(2k+2)=(2m+2k+3)(k+1)
pは素数なので k+1=1,2m+2k+3=p
∴k=0,m=(p-3)/2,n=0
よってF(p)＝1
|
No.69070 - 2020/08/17(Mon) 20:21:28 |
| ☆ Re: 謎いのでご教示ください / URHANL | | | ITさま、WIZさま。
長年の胸のつかえが取れました。実に爽快な面持ちです。この度はまことに有り難うございました。
ITさま。
># (m,n)=((p-3)/2,0),(r-(q+1)/2,q-2)は天下り的に書いていますが、
>m(n+2)+((n+2)(n+3))/2=(m+(n+3)/2)(n+2)=qr をにらみつけて見つけたものです。
このあたり、私にはとても思い付けそうにありません。痺れました。
また、対偶を証明しようなどとも全く気がつきません。
勉強になります。有り難うございました。
WIZさま。
>本質問の回答ではないですが、p が奇素数なら F(p) = 1 であることが示せます。
あっ、こちらも証明可能なのでしたか。 奇素数なる p でもって片端から F(p) を求めるべく、あやうく実験を始めるところでした。 お恥ずかしいことです。
当方、数学音痴なのだなあと改めて溜め息がでます。
ITさま、WIZさま。
WIZさま、ITさま、の証明を拝見いたしまして、考え込んだ末に以下のような考えに辿り着きました。
p = f(m, n) = m(n +2) +((n +2)(n +3))/2
k を非負整数とします。
n = 0 のとき
p = f(m, 0) = 3 +2m
n = 2k +1 のとき
p = f(m, 2k +1) = (2k +3)(k +2 +m)
n = 2k +2 のとき
p = f(m, 2k +2) = (k +2)(2k +5 +2m)
となります。
n = 2k +1 でも n = 2k +2 でも p は合成数であることがわかります。
従いまして p が奇素数であるためには、n = 0 が必要です。
p = f(m, 0) = 3 +2m
のみが許される形ですが、このとき、 p の値が具体的に与えられれば m がユニークに定まります。
以上より p が奇素数であれば、F(p) = 1 となります。
なお、
f(m, n) = m(n +2) +((n +2)(n +3))/2
は、どこから出てきた形かと申しますと、これは n を非負整数としたときに、連続する(n +2)個の正の自然数の和となっています。
ITさま、WIZさまの証明によりまして以下がわかりました。
3 以上の奇数 p について、 p が2個以上の個数の連続した正の自然数の和として表現する方法をただ一通り有することと、 p が素数であることとは同値です。
お二方とも、大変有り難うございました。
|
No.69071 - 2020/08/17(Mon) 21:29:01 |
| ☆ Re: 謎いのでご教示ください / IT | | | ＵＲＨＡＮＬさん、すっきりした証明ですね。
私は、「f(m,n)=m(n+2)+((n+2)(n+3))/2=(m+(n+3)/2)(n+2)
=(2m+1+n+2)(n+2)/2 とすると見通しがいいかも」と書き込もうとしていたところですが、
あっさりＵＲＨＡＮＬさん方式で場合分けするのが良いですね。
|
No.69073 - 2020/08/17(Mon) 22:30:24 |
| ☆ Re: 謎いのでご教示ください / WIZ | | | > 3 以上の奇数 p について、 p が2個以上の個数の連続した正の自然数の和として
> 表現する方法をただ一通り有することと、 p が素数であることとは同値です。
私は個人的に数論(初等整数論)に興味があるので、上記はとても興味深いですね!
3 以上の奇数である自然数は k を自然数として 2k+1 = k+(k+1) という表現を持つ訳ですが、
奇数合成数である自然数は上記以外の表現も持つ。
今思えは、以下の様な証明も可能ですね。
n を奇数合成数である自然数、p ≧ 3, q ≧ 3 を n の因数とし、n = pq とする。
p-(q-1)/2 から p+(q-1)/2 までの連続する q 個の自然数の和は、
(p-(q-1)/2)+(p-(q-1)/2+1)+・・・(p-1)+p+(p+1)+・・・+(p+(q-1)/2)
= Σ[i=p-(q-1)/2, (q-1)/2]{i}
= q{2(p-(q-1)/2)+(q-1)*1}/2
= pq
q ≧ 3 なので上記は3連続以上であり、2連続の n = k+(k+1) とは別の表現である。
よって、n が奇数合成数である自然数ならば表現数 F(n) > 1 である。
|
No.69084 - 2020/08/18(Tue) 10:15:14 |
| ☆ Re: 謎いのでご教示ください / IT | | | たしかに、ｐを中心としたｑ（奇数）個の連続整数の和＝ｐｑ という事実を使うのが見通しが良いですね。
|
No.69089 - 2020/08/18(Tue) 19:36:32 |
| ☆ Re: 謎いのでご教示ください / URHANL | | | ITさま、WIZさま。有り難うございます。
お二人のお話をお聴きしまして思ったことを少々申し上げたく存じます。
35以下の奇数を n ごとに分類してみました。
n+2=2; 3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35
n+2=3; 9,15,21,27,33
n+2=4;
n+2=5; 15,25,35
n+2=6; 21,27,33
n+2=7; 35,
例えば p=15 では、 15 を素因数分解した 3 と 5 とに注目いたしますと、n=0 は奇数ですから度外視しておきまして他には
n+2=3 と n+2=5 とで、15 が登場しております。
また p=35 では、 35 を素因数分解した 5 と 7 とに注目いたしますと、n=0 は奇数ですから度外視しておきまして他には
n+2=5 と n+2=7 とで、35 が登場しております。
ですので、ITさまが、69073の投稿でおっしゃった、
>f(m,n)=m(n+2)+((n+2)(n+3))/2=(m+(n+3)/2)(n+2)
>=(2m+1+n+2)(n+2)/2 とすると見通しがいいかも
は、故あることと存じます。 nの偶奇により場合分けが出ますが期待通りと存じます。
※ n+2 が偶数ならばその半分の数の倍数が並んでいます。
n+2=6; 21,27,33
一方、 n+2 が奇数ならばその数の倍数が並んでいます。
n+2=5; 15,25,35
ところで、 p=15 や p=35 と異なりまして、p=9 ですとn+2=3にしか登場しないのは、ある意味当然、ある意味不思議な気がいたします。
（数学音痴なものでして）
|
No.69097 - 2020/08/18(Tue) 20:51:33 |
| ☆ Re: 謎いのでご教示ください / URHANL | | | とある合成数の素因数のうち最小のものを発見するためのアルゴリズムとして試し割り法があります。
素因数分解しようとする整数 N を小さい順に素数で割ってみて、割り切れるかどうかを調べる手法です。
ここまでご教示頂いたことを元に試し割り法の変種がありうると判明しましたのでご報告いたします。
（実用上では計算量を減らす役には立ちません。）
具体例をひとつ。
合成数 9991 の最小の素因数を探索します。
素数3で割る前に三角数 (3*4)/2=6 を 9991 から減じて 9985 を得ます。この 9985 が 素数3で割りきれるかどうか検査します。
以下同様に下記のリストに従って処理していきます。
3, 6, 9985
5, 15, 9976
7, 28, 9963
11, 66, 9925
13, 91, 9900
17, 153, 9838
19, 190, 9801
23, 276, …
29, 435, …
31, 496, …
37, 703, …
41, 861, …
43, 946, …
47, 1128,…
53, 1431, …
59, 1770, …
61, 1891, …
67, 2278, …
71, 2556, …
73, 2701, …
79, 3160, …
83, 3486, …
89, 4005, …
97, 4753,(9991-4753)/97
101,5151, …
103,5356,(9991-5356)/103
(9991-4753)は97で割りきれますので、9991の最小の素因数は97です。
割り算の計算量だけを考えますと、２進法で最大でも高々１/２ビットだけ省力化になりますが、三角数の作成やそれを n から減じる手間を考えますと差し引き得にはなっていません。
ただただ、試し割り法にはバリエーションがありうるというお話しです。
|
No.69462 - 2020/09/08(Tue) 22:38:57 |
|
