問題
37 名前：１３２人目の素数さん[sage] 投稿日：2005/06/03(金) 22:15:31
>>22の「良い数」の定義を
「いくつかの正整数の和」から「いくつかの互いに異なる正整数の和」にするとどうなるか
解答
46 名前：１３２人目の素数さん[sage] 投稿日：2005/06/15(水) 20:50:15
>>37
やっとできた･･･一週間かかった。
補題１
長さ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 名前：１３２人目の素数さん[sage] 投稿日：2005/06/15(水) 20:50:36
補題２
任意の整数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の２進展開を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)。
補題３
任意の正の整数nについて長さがN=[log(2)n+1](=2進展開したときの桁数)の
数列ciが存在して以下を満たす。
･∑ci2^(i-1)=n。
･ci=1,3。
･ciの第N項は1。
証明)nの２進展開の桁数に関する帰納法。nの２進展開が１桁のときは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 名前：１３２人目の素数さん[sage] 投稿日：2005/06/15(水) 20:50:58
補題４
任意の正の整数nに対して正の整数の列diが存在し以下を満たす。
･diはすべて相異なる。
･∑di=203904n。
･∑1/di=512/3289。
･diは9の倍数であるか5の倍数。
･diは15の倍数でない。
･diは7の倍数でない。
証明)a1i、a2i、a3iを補題１において構成した数列とする。
nにたいして補題３を適用してciを補題３でのべられた条件をみたすようにとる。
その長さを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)
この２重列eijを適当にならべてdiとする。これが要求された条件を満たすことは容易。
補題５
任意の整数nに対し正の整数列eiが存在し以下を満たす。
･eiはすべて相異なる。
･∑ei≡n (mod 203904)、∑ei≦49(2^18-1)。
･∑1/(ei)=1/6。
･eiの2'部分は3か7か21。
証明)biを補題２において構成した列とする。その長さをNとして
２重列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 名前：１３２人目の素数さん[sage] 投稿日：2005/06/15(水) 20:51:33
補題６
長さ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)
定理７
49(2^18-1)+3696より大きい任意の整数nに対してxiが存在し以下を満たす。
･xiはすべて相異なる。
･∑xi=n。
･∑1/xi=1。
証明)補題４、補題５、補題６より容易。
59 名前：47[sage] 投稿日：2005/06/17(金) 08:22:18
>>47の補題３まずかった。証明したかったのは
各桁が1か3である2進展開みたいなもんで最高位が１であるものがとれる
といいたかった。まあそのようによんでちょ。
61 名前：１３２人目の素数さん[sage] 投稿日：2005/06/20(月) 17:36:47
>>59
補題3が後でどう使われてるかまだ良く見てないから、
見当違いかもしれないけど、
∑ci2^(i-1) は 2k+1 か 2k+3 になるから、
偶数はできなくない？
64 名前：１３２人目の素数さん[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 名前：１３２人目の素数さん[] 投稿日：2005/06/23(木) 21:43:39
>>37解決したみたいなんだけどせっかくだし
だれか>>37の意味での“最大のよくない数”計算してみてくれん？
70 名前：１３２人目の素数さん[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 名前：１３２人目の素数さん[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 名前：１３２人目の素数さん[sage] 投稿日：2005/06/23(木) 23:46:20
>>70-71
乙。いまんとこの最良評価4731203未満まではまだまだ差があるけどいけそう？
73 名前：１３２人目の素数さん[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 名前：１３２人目の素数さん[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 名前：１３２人目の素数さん[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 名前：１３２人目の素数さん[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 名前：１３２人目の素数さん[sage] 投稿日：2005/06/25(土) 01:12:57
>>76
>>70 とかもっと上のほうでミスってるのも自分だから、
プログラムに頼ってる部分はあまり…
しかしこの問題は>>37のオリジナル？
（あと、見ればわかるとおり>>73は>>46-49の、
無限に大きくなる部分を等比数列に押し込むって
アイデアを借用してる)
