面白い問題おしえて~な@数学板 数論20050603221531

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問題

37 名前:132人目の素数さん[sage] 投稿日:2005/06/03(金) 22:15:31
>>22の「良い数」の定義を
「いくつかの正整数の和」から「いくつかの互いに異なる正整数の和」にするとどうなるか

22 とは、良い数1?

解答

46 名前:132人目の素数さん[sage] 投稿日:2005/06/15(水) 20:50:15
>>37
やっとできた・・・一週間かかった。
 
補題1
 
長さ12の3つの正の整数列a1i,a2i,a3iがあって以下をみたす。
・∑a1i=∑a2i=∑a3i=203904。
・∑1/(a1i)=(1/2)∑1/(a2i)=(1/3)∑1/(a3i)=256/3289
・aijの2'部分はすべて相異なる。特に
 aij2^u=akl2^v⇒u=v、i=k、j=l。
・aijは9の倍数であるか5の倍数。
・aijは15の倍数でない。
・aijは7の倍数でない。
(ここで正の整数nの2'部分とは2と互いに素なnの約数のなかで最大のものである。)
 
証明)
a1=(45 1035 99 55 117 65 6435 1287 715 148005 29601 16445)
a2=(9 207 495 55 585 65 6435 1287 715 148005 29601 16445)
a3=(5 115 495 99 585 117 6435 1287 715 148005 29601 16445)
とおけばよい。

47 名前:132人目の素数さん[sage] 投稿日:2005/06/15(水) 20:50:36
補題2
 
任意の整数nについて長さ18の整数列aiが存在し以下をみたす。
・∑bi2^(i-1)≡n (mod 203904)。
・bi=49 or 6。
 
証明)
まず203904=2^7・3^2・59なので(203904,43)=1。よって整数mを
43m+6(2^18-1)≡n (mod 203904)、0≦m<203904となるようにとれる。
mの2進展開をm=∑ci2^(i-1) (i:1~18)とするときbi=43ci+6と定める。
明らかにbi=49 or 6。さらに
∑bi2^(i-1)=∑(43ci+6)2^(i-1)=43m+6(2^18-1)≡n (mod 203904)。
 
補題3
 
任意の正の整数nについて長さがN=[log(2)n+1](=2進展開したときの桁数)の
数列ciが存在して以下を満たす。
・∑ci2^(i-1)=n。
・ci=1,3。
・ciの第N項は1。
 
証明)nの2進展開の桁数に関する帰納法。nの2進展開が1桁のときはn=1なのであきらか。
N桁未満で成立すると仮定してnがN桁の整数とする。nが2べきならあきらか。
nが2べきでないとする。n-2^Nは正の整数だから帰納法の仮定を適用して
長さMがN-1以下の数列diを
・∑di2^(i-1)=n-2^N
・di=1,3
・diの第M項は1
と選ぶ。M=N-1ならaiをci=di(i<N)、cN=1とさだめればよい。M<N-1のときは
ci=di(i<M)、cM=3、ci=1(i>M)と定めればよい。

48 名前:132人目の素数さん[sage] 投稿日:2005/06/15(水) 20:50:58
補題4
 
任意の正の整数nに対して正の整数の列diが存在し以下を満たす。
・diはすべて相異なる。
・∑di=203904n。
・∑1/di=512/3289。
・diは9の倍数であるか5の倍数。
・diは15の倍数でない。
・diは7の倍数でない。
 
証明)a1i、a2i、a3iを補題1において構成した数列とする。
nにたいして補題3を適用してciを補題3でのべられた条件をみたすようにとる。
その長さをNとおく。長さ12Nの2重数列eij(1≦i≦N,1≦j≦12)を以下のようにさだめる。
eij=a1j2^(i-1) (if ci=1、i≠N)、eij=a3j2^(i-1) (if ci=3)、eNj=a2j2^(N-1)
この2重列eijを適当にならべてdiとする。これが要求された条件を満たすことは容易。
 
補題5
 
任意の整数nに対し正の整数列eiが存在し以下を満たす。
・eiはすべて相異なる。
・∑ei≡n (mod 203904)、∑ei≦49(2^18-1)。
・∑1/(ei)=1/6。
・eiの2'部分は3か7か21。
 
証明)biを補題2において構成した列とする。その長さをNとして
2重列fij(1≦i≦N,j=1,2)を以下でさだめる。
fi1=42・2^(i-1)、fi2=7・2^(i-1) (if bi=49)、fi1=6・2^(i-1)、fi2=0 (if bi=6)
fijの0でない項をならべたものをeiとすれば要求された条件をみたす。

49 名前:132人目の素数さん[sage] 投稿日:2005/06/15(水) 20:51:33
補題6
長さ10の正の整数の列fiが存在して以下をみたす。
・fiはすべて相異なる。
・∑fi=3696。
・∑1/fi=1-512/3289-1/6。
・fiは9の倍数でも5の倍数でもないか、15の倍数であるか、7の倍数である。
・fiの2'部分は3でも7でも21でもない。
 
証明)
fiを以下のように定めればよい。
fi=(92, 77, 1380, 420, 910, 345, 105, 91, 35, 70, 13, 156, 2)

定理7
 
49(2^18-1)+3696より大きい任意の整数nに対してxiが存在し以下を満たす。
・xiはすべて相異なる。
・∑xi=n。
・∑1/xi=1。
 
証明)補題4、補題5、補題6より容易。

59 名前:47[sage] 投稿日:2005/06/17(金) 08:22:18
>>47の補題3まずかった。証明したかったのは
各桁が1か3である2進展開みたいなもんで最高位が1であるものがとれる
といいたかった。まあそのようによんでちょ。

61 名前:132人目の素数さん[sage] 投稿日:2005/06/20(月) 17:36:47
>>59
補題3が後でどう使われてるかまだ良く見てないから、
見当違いかもしれないけど、
∑ci2^(i-1) は 2k+1 か 2k+3 になるから、
偶数はできなくない?

64 名前:132人目の素数さん[sage] 投稿日:2005/06/22(水) 01:29:08
>>37
4731203 以上の整数は >>37 の意味で良い数と言える
(>>46-49見た後知恵 + PCで探索)

集合 S,T,U,C を
S={3,5,7,9,11,15,42,45,110}, T={3,5,7,9,11,26,33,42,45,143},
U={1,2,3,6}, C={3,114,247} とする。
Σ[x∈S]x = 247, Σ[x∈T]x = 324, Σ[x∈S]1/x = Σ[x∈T]1/x = 1,
Σ[x∈U]x = 12, Σ[x∈U]1/x = 2, Σ[x∈C]x = 364, Σ[x∈C]1/x = 9/26。

n を 4731203(=52*2^13+4305219) 以上の勝手な整数とする。
n = 52*2^p + m + 4305219 (p≧13, 0≦m<52*2^p) と書ける。
gcd(4*246,13*323)=1 なので、中国剰余定理より、適当な整数 a,b により
m + 4*246*13*323 = 4*246a + 13*323b (a≧0, 0≦b<4*246) とできる。
以上から n = 4(13*2^p-1+246a) + 13(13*2^10-1+323b) + 364 と書ける。
p≧13, m<52*2^p から a<2^p を言うのは簡単。

0≦k≦p-1 に対して
A[k] = { 4*2^k*x | x∈S } (a の2進展開に 2^k が現れるとき),
A[k] = {4*2^k} (それ以外)、A[p] = { 4*2^p*x | x∈U } とする。
A[k] (0≦k≦p) が全て互いに素であることはすぐ分かる。
A = ∪[k=0,p] A[k] とすれば、
Σ[x∈A]x = 4(13*2^p-1+246a), Σ[x∈A]1/x = 1/2。

同様に、0≦k≦9 に対して
B[k] = { 13*2^k*x | x∈T } (b の2進展開に 2^k が現れるとき),
B[k] = {13*2^k} (それ以外)、B[10] = { 13*2^10*x | x∈U } として、
B = ∪[k=0,10] B[k] とすれば、
Σ[x∈B]x = 13(13*2^10-1+323b), Σ[x∈B]1/x = 2/13。

A,B,C が互いに素であることはすぐ分かる。
X = A∪B∪C とすれば、Σ[x∈X]x = n, Σ[x∈X]1/x = 1。

69 名前:132人目の素数さん[] 投稿日:2005/06/23(木) 21:43:39
>>37解決したみたいなんだけどせっかくだし
だれか>>37の意味での“最大のよくない数”計算してみてくれん?

70 名前:132人目の素数さん[sage] 投稿日:2005/06/23(木) 22:51:19
>>69
>>37 の意味での良くない数リスト
(探索範囲 n≦2000。自信ないから、誰か追試頼む)

2,3,5,6,7,8,9,12,13,14,15,16,17,18,19,20,21,23,25,26,27,28,
33,34,35,36,39,40,41,42,44,47,48,49,51,56,58,63,68,70,77

71 名前:132人目の素数さん[sage] 投稿日:2005/06/23(木) 23:04:56
訂正 やっぱいきなりバグってた

2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,22,23,25,26,27,28,29,
33,34,35,36,39,40,41,42,44,46,47,48,49,51,56,58,63,68,70,72,77

72 名前:132人目の素数さん[sage] 投稿日:2005/06/23(木) 23:46:20
>>70-71
乙。いまんとこの最良評価4731203未満まではまだまだ差があるけどいけそう?

73 名前:132人目の素数さん[sage] 投稿日:2005/06/24(金) 21:40:25
>>72
ちょっと卑怯だけど、下の補題(PCで確認した)を認めれば、
n≧155 なら n は >>37 の意味で良い数。

補題) 155≦n≦822 のとき n を 4 の倍数でない相異なる
自然数に分割してその逆数の和を 1 にできる

定理) n≧155 のとき n は >>37 の意味で良い数

まず n≧718 とする。
n = a[0] + 4b, a[0]∈{8,27,29,34} とできる。

155(4^(p-1)-1)/3 + 4*4^(p-1) ≦ b < 155(4^p-1)/3 + 4*4^p となる p(≧2) を選び、
c = b - {155(4^(p-1)-1)/3 + 4*4^(p-1)} とすれば、0≦c<167*4^(p-1) なので
c = Σ[k=1,p-1] c[k]*4^(k-1) (0≦c[k]<4*167) とできる。
a[k]=c[k]+155 (1≦k≦p-1), a[p]=4 とすれば結局
n = Σ[k=0,p] a[k]*4^k (155≦a[k]≦822=4*167-1+155 for 1≦k≦p-1)
と書ける。

a[0] を分割して逆数の和を 2/3 にできる
(8=2+6, 27=2+10+15, 29=2+9+18, 34=3+6+10+15)。
補題より、1≦k≦p-1 に対して、a[k]*4^k を分割して逆数の和を 1/4^k にできる。
a[p]*4^p を 4^p+3*4^p と分割すれば、逆数の和を 1/(3*4^(p-1)) にできる。
a[k]*4^k (0≦k≦p) は全て 4^k の倍数であって、
4^(k+1) の倍数でない自然数に分割されたので、
分割されてできた自然数には重複がない。
以上から、n(≧718) を相異なる自然数に分割して逆数の和を
2/3 + (Σ[k=1,p-1]1/4^k) + 1/(3*4^(p-1) = 1 にできる。

補題より、明らかに 155≦n≦717 の n は良い数なので、
上と併せて n≧155 のとき n は良い数。

74 名前:132人目の素数さん[sage] 投稿日:2005/06/24(金) 23:41:16
>>73
>a[p]*4^p を 4^p+3*4^p と分割すれば、逆数の和を 1/(3*4^(p-1)) にできる。
 
これおかしくね?4^p=4^(p-1)+3・4^(p-1)と分割すると逆数和は
1/4^(p-1)+1/(3・4^(p-1))=(4/3)(1/4^(p-1))=1/(3・4^(p-2)
じゃね?

75 名前:132人目の素数さん[sage] 投稿日:2005/06/25(土) 00:14:18
>>74
>a[p]=4 とすれば

例)
n=743
a[0]=27, p=2, b=179, c=8, c[1]=8, a[1]=163, a[p]=a[2]=4

743 = 27 + 4*163 + 4^2*4
= (2+10+15) + 4(2+6+9+10+15+22+99) + 4^2(1+3)
= 2+10+15 + 8+24+36+40+60+88+396 + 16+48

76 名前:132人目の素数さん[sage] 投稿日:2005/06/25(土) 00:29:34
>>75
ああ、なるほどわかった。
>n = Σ[k=0,p] a[k]*4^k (155≦a[k]≦822=4*167-1+155 for 1≦k≦p-1)
この後ろの部分の条件でa[p]はまえの構成で4ときまってるんだな。
でその4を1+3と分割すると。ならあとは全部あってる気配が。
ということは結局+>>71で完全に終了?すばらしい。

77 名前:132人目の素数さん[sage] 投稿日:2005/06/25(土) 01:12:57
>>76
>>70 とかもっと上のほうでミスってるのも自分だから、
プログラムに頼ってる部分はあまり…

しかしこの問題は>>37のオリジナル?

(あと、見ればわかるとおり>>73は>>46-49の、
無限に大きくなる部分を等比数列に押し込むって
アイデアを借用してる)