X



トップページ数学
1002コメント551KB
コラッツ予想がとけたらいいな その2
■ このスレッドは過去ログ倉庫に格納されています
0652132人目の素数さん2018/10/25(木) 00:10:59.36ID:3G32divF
懸賞かかってなくてもコラッツとけたら年収1000万の職につけないかなぁ?
0654132人目の素数さん2018/10/27(土) 00:52:40.01ID:NYHShEyu
証明は出来たのですか?
完全に素人質問で悪いのですが、証明の全容をここに載せたら盗まれる可能性があるのではないでしょうか?
arXivに上げるなどして正式に発表したほうがいいのでは…と思ってしまいます。
0657132人目の素数さん2018/10/27(土) 10:44:44.71ID:sjLLdu9W
    / ̄`Y  ̄ヽ、
   / / / / l | | lヽヽ
  / / // ⌒  ⌒ヽ
  | | |/  (●) (●)
  (S|| |   ⌒ ・ィ  ヽ  芸能人が吹き替えに挑戦というのは
  | || |   ト-=-ァ ノ
  | || |   |-r 、/ /|
  | || | \_`ニ'_/ |
    (( ( つ ヽつ、
      . 〉    i ))
      (__ノ^(_)


    / ̄`Y  ̄ヽ、
   / / / / l | | lヽヽ
  / / // ⌒  ⌒ヽ
  | | |/  (●) (●)
  (S|| |   ⌒ ・ィ  ヽ  許せないという気持ちが分かる
  | || |   ト-=-ァ ノ
  | || |   |-r 、/ /|
  | || | \_`ニ'_/ |
     ⊂/ ⊂ )
      i    ヽ
   (( (_)^ヽ.__) )) 👀
Rock54: Caution(BBR-MD5:1341adc37120578f18dba9451e6c8c3b)
0658132人目の素数さん2018/10/27(土) 17:09:07.82ID:4wEgV5jN
この証明の鍵は、star変換によってコラッツ列の無限性を維持しつつ元の整数を小さくできるとする主張にあります。
しかし変換の定義から そのようなことが常に可能とは思えない というのが私の直感です。

まず確認ですが、star変換によって割数列に負の項が出てくることを許しているわけではない ですよね?
各chapterを一読しましたが、『計算上は合う』というコメントもあり判然としません。
プログラムを読めば分かるのかもしれませんが素人なのでお許しを。

[chapter3より引用]
> 変換後のコラッツ値が、負数や分数になるものを禁止すれば、
> この変換は、3の倍数から3の倍数に写ります。
> これで得られる割数列を 「拡張完全割数列」 と呼ぶ事にします。

割数列の定義から負の項は存在できません。
たとえ最終計算が合っていたとしても、2を掛ける操作はコラッツ列の生成ルールにはありませんから、
負の項が出現するような変換は許されません。『拡張列』としてそれを 考えるだけ なら構いませんが、
拡張列から元の整数を復元する操作を統一的に行うことは許されないはずです。
0659righ1113 ◆OPKWA8uhcY 2018/10/27(土) 18:14:31.31ID:q47UWgiA
>>658
詳細なコメントありがとうございます。
すぐには答えられないので、じっくり考えてみます。
0660132人目の素数さん2018/10/27(土) 19:27:37.82ID:4wEgV5jN
例を挙げておきます。

[Chapter7より]
> コラッツ値がcである無限項の割数列を仮定して、コラッツ値が小さくなるようなstar変換を施します。

ここで筆者は、0(mod9)である36t+9なる整数に対しE[2,-4](y=x/12−3/4)を施すと変換後は3t<36t+9になると主張する。
t=1とすれば、36t+9の割数列は[3,2,3,4]であり、E[2,-4]をそのまま施すと[2,-1,2,3,4]となり負の項が現れる。
この第2項『-1』を『2を掛ける操作』と解釈すれば、[2,-1,2,3,4]が表す整数は確かに3tになる。
しかしコラッツのルールに『2を掛ける操作』は存在しないので、本問題でそのような解釈はできない(※)。
3tに対応する割数列はコラッツのルールで一意に決まる[1,4]であり[2,-1,2,3,4]ではない。
コラッツのルールに則れば、
 『負の項を持つ割数列に対応する整数は存在しない』
としか言えない。

(※)
負の項を持ちうる拡張割数列を元の整数に対応づける解釈を行うことは
・2で割る、2を掛ける、3を掛けて1を足すという3つの操作を別のルールに則って行う。
・各操作後の値は整数とは限らない。
このような拡張されたコラッツ問題を考えることに相当する。
その拡張されたルールを前提とすれば、[1,4]と[2,-1,2,3,4]は共に3tに対応する。
言えるのはこれだけのように思える。
0664righ1113 ◆OPKWA8uhcY 2018/10/30(火) 18:48:13.22ID:kWJk14TU
>>658,660
以下3つをおこなえば良いのではないかと考えています。

◆定義1 拡張コラッツ予想
6t+3(t≦0)を用意する。(ここからコラッツ操作すれば通常のコラッツ予想になる)
一度コラッツ操作を施したものをαとおく。
6t+3から1~3回star変換をおこなう。
そこから拡張コラッツ操作をおこなう。αに戻ったところで通常のコラッツ操作に切り替える。
これを拡張コラッツ予想と名付ける。
※拡張コラッツ操作
コラッツ値xに対し、(3x+1)/2^pを施す。pは割数列の初項(0や負も取りうる)。

◆定理1
あるコラッツ値(一度コラッツ操作したものをα)からstar変換したものを、
2回拡張コラッツ操作すると、αに戻る

◆定理2
拡張コラッツ予想が真 ⇒ コラッツ予想も真
0665righ1113 ◆OPKWA8uhcY 2018/11/01(木) 23:53:32.36ID:JDsMJ7mn
◆定理1
あるコラッツ値(一度コラッツ操作したものをα)からstar変換したものを、
2回拡張コラッツ操作すると、αに戻る

・1つのパターン
x=9t+3 [3, *,...]
を1回コラッツ操作すると、(3(9t+3)+1)/8 = (27t+10)/8 になります。

xに A[6,-4] y=(4/3)x-7 でstar変換すると
12t-3 [6, -1, *,...] になります。
拡張コラッツ操作1回目で (3(12t-3)+1)/2^6 = (9t-2)/2^4
拡張コラッツ操作2回目で (3((9t-2)/2^4)+1)2
 = (27t+10)/8 になって二つは一致します。

残りはGitHubでやります。
0666righ1113 ◆OPKWA8uhcY 2018/11/01(木) 23:56:34.87ID:JDsMJ7mn
◆定理2
拡張コラッツ予想が真 ⇒ コラッツ予想も真

star変換したものから拡張コラッツ操作を繰り返すと、
定理1より、全ての6t+3から遷移するαと同じものが、
欠けることなく得られます。
よって、拡張コラッツ予想が真ならば、
後方を共有する、通常のコラッツ予想も真になります。
0667132人目の素数さん2018/11/03(土) 10:40:12.37ID:0X36i8df
>>664-666
その方針でこの問題が簡単化されるとは思いませんが。
righ1113さんの腕の見せ所ですね。
がんばってください。
0668righ1113 ◆OPKWA8uhcY 2018/11/03(土) 10:58:34.66ID:zGxL77aT
ありがとうございます。
頑張ります!
0673132人目の素数さん2019/04/20(土) 06:08:45.05ID:qXeTVoFa
自然数xに対してコラッツ展開に似た数列collatz_array(x)を次のようなrubyプログラムで定義する。

def collatz_array(x)
if(x==1)
then
return []
elsif(x%2==0)
return [0]+col(x/2)
else
return [1]+col((x*3+1)/2)
end
end

collaz_array(x)をビット列とみなして2進数の整数に直したものをcollatz_number(x)とする。

collatz_numberはrubyプログラムで次のように定義される。

def collatz_number(x)
res=0;
x.each_with_index{|v,i|res+=v*(2**i)}
return res
end


3の倍数でない、かつx==collatz_number(x)となるような自然数xは存在するか?
0674132人目の素数さん2019/04/20(土) 06:11:30.83ID:qXeTVoFa
ちょっと言ってることがおかしいかもしれない。
ようするにコラッツ展開に対する不動点みたいなものはあるか?という話をしたいのだが
0676132人目の素数さん2019/04/20(土) 06:24:30.09ID:qXeTVoFa
朝の6時にスレチェックかよwすげえw
まあ俺も人のこと言えないけどwお疲れ様です。
0677132人目の素数さん2019/04/20(土) 06:30:30.11ID:qXeTVoFa
新たな不動点が見つかったら新たなループが見つかるみたいな方向に持っていけたらベストなんだけど。
まあまだぼんやりしたイメージがあるだけです。
0678132人目の素数さん2019/04/20(土) 07:07:33.52ID:qXeTVoFa
うーん、collatz_arrayの停止条件がx==1だとあんまり意味のない議論になってしまうかもしれないorz
0679righ1113 ◆OPKWA8uhcY 2019/04/20(土) 08:32:56.05ID:gsPKCWwo
x==collatz_number(x)をチェックすると
3*2^tは該当するみたい。そりゃそうか。

あと、「先頭nビットが一致する」だと意味ないかな?
0680132人目の素数さん2019/04/20(土) 08:52:09.89ID:qXeTVoFa
>>679
意味ないかどうかはまだわかりませんが、先頭nビットについては>>528のような割とはっきりした規則性があるようなので、
規則性の見えなくなる後ろのほうのビットのふるまいを何とかできないかという思いはあります。
0681132人目の素数さん2019/04/20(土) 08:53:34.80ID:qXeTVoFa
あ、でもnを増やしていったらなんか出てくるんだろうか?
0682132人目の素数さん2019/04/20(土) 09:20:18.07ID:qXeTVoFa
ちなみに勢いで書いちゃったけど仮に不動点が見つかったとして、それをどう生かせばいいかまだ全然見えてませんw
0683132人目の素数さん2019/04/20(土) 09:23:37.92ID:qXeTVoFa
不動点というキーワードでコラッツ展開をみたときに、
ちょうど3が不動点になっていたのでこれが1,4,2のループを表しているのでは?
という思い付きというか期待から書き込んでしまいました。
0684132人目の素数さん2019/04/20(土) 10:25:47.50ID:kQapNYTQ
コラッツ展開は01の無限列なので2-進整数に対応させるのはどうだろう
整数は2-進整数に埋め込めるし、コラッツ展開は2-進整数に自然に拡張できる

以下、簡略表記として左を下位、繰り返しを()で括る、とすると
0=(0)…
-1=(1)…
はコラッツ展開が自身と一致する

1=1(0)… のコラッツ展開は (10)…
(10)…は×3で(11)… = -1 なので
(10)…のコラッツ展開は 1(0)… で元に戻る
0685132人目の素数さん2019/04/20(土) 10:44:40.51ID:2B/xzIiP
見捨てられた過疎スレかと思ってたら
意外とそうでもないのか
0686132人目の素数さん2019/04/20(土) 12:02:57.09ID:2B/xzIiP
2進整数とやらを標準ライブラリで持ってるプログラム言語はありますか?
0687righ1113 ◆OPKWA8uhcY 2019/04/20(土) 12:48:56.09ID:gsPKCWwo
>>686
Mapleにありそうだけど
Mapleってフリーじゃないもんね
0688132人目の素数さん2019/04/20(土) 13:09:40.55ID:kQapNYTQ
無限桁の2進数みたいなものだから、プログラムで扱うのは難しいのでは?

有限桁以降が繰り返しのものに限定すれば扱えるのかな
(10)…と-1/3、(100)…と-1/7、みたいに、
理論上は(分母の素因数に2を含まない)有理数に対応するはず
0689132人目の素数さん2019/04/20(土) 13:21:28.65ID:qXeTVoFa
とりあえず、2-進整数の厳密な定義ってどこかにあります?
四則演算とかも含めて。
0690132人目の素数さん2019/04/20(土) 13:27:40.12ID:qXeTVoFa
ハスケルは遅延評価があるんでしたっけ?
ルビーにもあったかな?
0691righ1113 ◆OPKWA8uhcY 2019/04/20(土) 13:45:31.66ID:gsPKCWwo
>>690
Haskellはデフォルトで遅延評価です。
Rubyも遅延評価がありそうですが、僕は詳しくないです。
0692132人目の素数さん2019/04/20(土) 13:52:34.74ID:qXeTVoFa
2-進整数、使えそうなら使いたいですね
でも2-進整数にしちゃうと不動点のアイディアをどう扱えばいいかわからなくなるかなぁ?
0693132人目の素数さん2019/04/20(土) 14:00:26.66ID:kQapNYTQ
とりあえずwikipediaよりp進数(p-adic number)
https://ja.m.wikipedia.org/wiki/P%E9%80%B2%E6%95%B0
「定義」の最後にあるp進整数環でpが2のものを考えてるんですが、付値やら完備化や、専門的過ぎてたぶんわけわからんと思います

計算だけなら「略式の解説」のこの辺
> 整数側に無限桁加えたもの、例えば …1246328.125 のようなものが p 進数であると解釈できる。
> p 進数の中でも、小数点以下がない …1246328 のようなものは p 進整数と呼ばれるものに対応する。
> p 進数同士の足し算、引き算、掛け算は、p 進表記の有理数における通常のアルゴリズムを自然に無限桁に拡張することで得られ、割り算は掛け算の逆演算として定義される。
0696132人目の素数さん2019/04/20(土) 15:43:16.25ID:qXeTVoFa
まともにやるとクソ難しそうなのでとりあえずコラッツ展開を分数で表現してみた

def collatz_rational(x)
l=x.length
res=0r
x.reverse.each_with_index{|v,i|res+=v*(1/2r)**(i+1)}
res+=((1/2r)**l)*1/3r
return res
end

def collatz_rational_array(x,l)
res=[]
(0...l).each{|i|
if(x>=1/2r)
then
x-=1/2r
res<<1
else
res<<0
end
x*=2r
}
return res.reverse
end

(1..1000).each{|x|
a=collatz_array(x)
l=a.length
r=collatz_rational(a)
b=collatz_rational_array(r,l)
if(a!=b)
then
print "#{x} #{r} #{a} #{b}\n"
end
}
0697132人目の素数さん2019/04/20(土) 15:48:17.01ID:qXeTVoFa
でも分数にしたところで不動点のアイディアとどう結び付けていいかわからぬw
まあもともと不動点はそれほど目があるアイディアじゃないかもだけど
0701132人目の素数さん2019/04/20(土) 18:15:52.88ID:qXeTVoFa
スタートは不動点だったはずだが脱線してしまったなw
うーん、どうしよう
0702righ1113 ◆OPKWA8uhcY 2019/04/20(土) 18:43:16.20ID:gsPKCWwo
不動点ではないですが、
x == collatz_number(collatz_array(y))
y == collatz_number(collatz_array(x))
のように、相互に参照しあっているものを考え中です。
ちゃんとしたものは後日upします。
https://i.imgur.com/7VUP2CA.jpg
0703132人目の素数さん2019/04/20(土) 19:51:06.44ID:kQapNYTQ
2-進整数の計算についての補足

桁が繰り返しである2-進整数に限ると、
繰り返しが1で埋まれば-1であることを利用して
以下のように有理数との対応がわかります
(1)…=-1/(2^1-1)
(10)…=-1/(2^2-1)
(100)…=-1/(2^3-1)

途中から繰り返す場合についても、例えば
1(100)…=1+2(-1/7)=5/7
のようになります

そして、このようなものに限ると有理数としての加減乗除でまったく問題なかったりします
循環小数=有理数、みたいなもんですね
0704132人目の素数さん2019/04/20(土) 21:01:20.91ID:qXeTVoFa
不動点ということは繰り返し処理をかけても変わらないということですが、
コラッツ展開に対してさらにそのコラッツ展開を求めることに何の意味があるのかが不明瞭なのが現状痛いですね。
そこに何らかの意味が見いだせればもう少し面白くなるのですが
0705righ1113 ◆OPKWA8uhcY 2019/04/21(日) 01:05:53.95ID:eAsDk9Da
特に何か得られた訳ではないですが、upします。

https://github.com/righ1113/CollatzMod/tree/master/190421

気がついた事は、(不動点じゃないですが)
例えばxが17~31の奇数の区間で、コラッツ展開先頭5ビットが1~31の奇数を、
コラッツ3x+1と3x-1で分けあうことです。
0706righ1113 ◆OPKWA8uhcY 2019/04/21(日) 01:27:22.72ID:eAsDk9Da
>>705
書いてから思ったのですが、
>>528と関連があるのかどうか、というところですかね。
0707132人目の素数さん2019/04/21(日) 07:54:17.77ID:npoMZDGj
負数の3x+1問題は実質3x-1問題(x→-x)なので
負数側の結果がスライドしてきている、と考えればよいのかなと
0708132人目の素数さん2019/04/21(日) 21:02:50.26ID:pvqV4cbN
コラッツ展開が長さnの循環列
⇔xに対し「x→(3x+1)/2」または 「x→x/2」の変換をある順番でn回行ってxに等しくできる
⇔0≦∃k≦n, ∃y∈Z, ((3^k)x+y)/2^n=x.
これは有理数の範囲で一つの解をもつ
0709132人目の素数さん2019/04/21(日) 21:18:37.12ID:58cJHsba
すいません、不動点はあまり実りがなさそうなので撤退します。申し訳ない。
今1〜2^nのコラッツ展開の先頭nビットを並べてコラッツ展開のkビット目にどのようなパターンが表れるかというのを見ようかと思ってます。
07127082019/04/22(月) 06:24:26.02ID:xqP02tmi
p進体Q_pにおいて、分母がpで割り切れない有理数はp進整数環Z_pに含まれることが知られている
(フェルマーの小定理より任意の素数q≠pに対してp^(q-1)≡0(mod q) なので、-1/qのp進展開がq-1桁の循環になる)

コラッツ問題の有理数への拡張は、Z_2への拡張と考えたほうが実は自然なのでは?
というところで2-進整数ネタも一休み
また週末かなー
0713righ1113 ◆OPKWA8uhcY 2019/04/26(金) 08:31:01.99ID:RlIUNLEW
コラッツ展開のコラッツ展開をいくつか計算してみましたが、いまいちでした。
https://github.com/righ1113/CollatzMod/blob/master/190421/%E3%82%B3%E3%83%A9%E3%83%83%E3%83%84%E5%B1%95%E9%96%8B_2-%E9%80%B2%E6%95%B4%E6%95%B0.xlsx
-1, 0, 1だけが特別で、(>>684
これ以外の数は、コラッツ展開を施すごとに、どんどん複雑になっていくようです。
「3x-1」シートは、3x-1にして負値を計算したものです。
0714132人目の素数さん2019/04/26(金) 20:39:33.09ID:xTZynMFI
繰り返したら元に戻るとか、そういうことはない感じですかね
フーリエ変換に対する逆変換みたいなものが見つからないか、というのは今のところ夢想かなあ
0715132人目の素数さん2019/04/26(金) 20:57:44.06ID:xTZynMFI
>520
の補題を自分の中で整理してたらこうなった。

写像f: Z→Zを次で定義する.
x∈Z に対し,
f(x)=x/2 (x∈0+2Z)
f(x)=(3x+1)/2 (x∈1+2Z)
このとき, 0≦n∈Z, x, y∈Z に対して次が成り立つ.

x-y∈(2^n)Z ⇒ 0≦∃m≦n, s.t.
(2^n)(f^n(x)-f^n(y))=(3^m)(x-y).

(超略証)nに関する帰納法.
定義から0と1の場合がOK.
1とkをあわせてk+1の場合が示される.
0716righ1113 ◆OPKWA8uhcY 2019/04/26(金) 22:52:24.34ID:edmDBtkV
>>714
繰り返したら元に戻るとか、
小さくなる、とかだったら良かったですけどね。
0717132人目の素数さん2019/04/27(土) 17:46:18.20ID:PhPZ0MkR
>715 に引き続き, >521 を代数学風に整理.

前述(>715)のf, x∈Z, 0≦i∈Zに対し x_i=f^i(x)+2Z で定まる Z/2Zの列{x_i}(i≧0)を「xのコラッツ展開」と呼ぶことにする.

x,y∈Zとそのコラッツ展開{x_i},{y_i}について次が成り立つ.
x-y∈(2^n)Z⇔x_i=y_i (0≦∀i≦n).

系. コラッツ展開は単射.
0718132人目の素数さん2019/05/08(水) 21:48:28.23ID:U/58yMQ3
コラッツ展開はかなりいい線いってるとは思うが、次の一歩が難しい?
0719132人目の素数さん2019/05/08(水) 22:07:04.85ID:U/58yMQ3
例えばxのコラッツ展開のyビット目がxのサイズの多項式時間で求まれば大きな前進と言える?
0720132人目の素数さん2019/05/08(水) 22:10:31.84ID:U/58yMQ3
ここでいうxのサイズっていうのは自然数xに対してそれを表すのに必要なビット数log(x)のことね
0721righ1113 ◆OPKWA8uhcY 2019/05/09(木) 06:34:48.07ID:ysyHHFnM
>>719
入力サイズに対して、
コラッツ操作で何回2で割るかが分からないので、
難しいと思います。

特殊な場合だと、
2^n±1は、コラッツ展開のnビット目までを
多項式(定数?)時間で求められます。
0722132人目の素数さん2019/05/09(木) 07:08:14.74ID:+tHX/zWL
個人的には

・Z(有理整数環)→(Z/2Z)の列 で単射になる
・>521の性質から、Z_2(2-進整数環)上にwell-definedに拡張できる
(環Zと素イデアル2Zの話が環Z_2と素イデアル2Z_2の話になるだけで、まったく同じロジックが展開できる)
・Z_2上全射(よって全単射)になる

ということでZ_2上で考えたらなんか出てこないかなー、とは。

コラッツ展開がループ
→一次方程式の解
→Q∩Z_2
とか。

なお、p-進整数環については、射影極限を経由するルートの方がわかりやすいかもしれません。
0723132人目の素数さん2019/05/09(木) 08:06:12.63ID:+tHX/zWL
1ビットでも違うとそこから先は別物というか、カオス的な振る舞いをしますね
2で割ることで折りたたまれたフラクタル構造といいますか……
0724righ1113 ◆OPKWA8uhcY 2019/05/09(木) 08:26:35.55ID:c2RXSWlw
ところで、
>>684から書いている2-進整数とは少し違うものが英語版Wikipediaにあった。
https://en.wikipedia.org/wiki/Collatz_conjecture
の"Iterating with odd denominators or 2-adic integers"

例えば、コラッツ展開(1011001)のループを考える。
このコラッツ展開の長さn=7で、"1"の個数m=4。
"1"のビット位置k_0,...k_(m-1)は、0, 2, 3, 6。
これらを元に、
(3^(m-1)*2^k_0 + ... + 3^0*2^k_(m-1))/(2^n - 3^m)
を計算すると、151/47になる。
この数を分数でコラッツ操作すると、
151/47 → 250/47 → 125/47 → 211/47 → 340/47 → 170/47 → 85/47 → 151/47 → ...
となって、確かにループしている。偶奇のコラッツ展開とも一致している。

(10)からは1が得られるし、(110)からは-5が得られる。
一つのループから一つの有理数が得られるようだ。

これも2-進整数って言うのかなあ。
0725132人目の素数さん2019/05/09(木) 18:33:29.57ID:+tHX/zWL
2-進整数環Z_2においては、2Z_2の元でなければ可逆元となるので、47の逆元が2-進整数として存在します。
151/47と書くより151・47^-1と書く方が実情を正しく表現しているかもしれません。

また、加法・乗法は有理整数環上のものが延長されているので、分母が奇数の有理数についてはそのまま有理数として計算しても問題が発生することはありません。
0726righ1113 ◆OPKWA8uhcY 2019/05/09(木) 18:39:46.62ID:ysyHHFnM
ありがとうございます。
よく分かってないですが……
精進しますm(_ _)m
0727132人目の素数さん2019/05/09(木) 19:13:07.75ID:yA5UfL3f
じゃあxのコラッツ展開のyビット目をもとめるのはNP困難か?
だったらどう?
0728132人目の素数さん2019/05/09(木) 19:57:09.94ID:+tHX/zWL
分母が47の2-進整数は、
2^23-1 = 8388607 = 47×178481
であることから、
47^-1 が繰り返しが23桁の2-進整数となることがわかります。

具体的には
23桁の (11…1) = -1
であることから、
23桁の (10…0) = -1 × 47^-1 × 178481^-1
両辺に -1, 178481 をかけるという手順で求まります。
07297272019/05/09(木) 20:16:04.29ID:19c66qNB
NP困難がむりでも素因数分解とかグラフの同型問題とかに帰着出来たら一定の成果と言えると思う。
0730132人目の素数さん2019/05/09(木) 20:21:22.85ID:19c66qNB
あれ、逆か?
素因数分解とかグラフの同型問題をコラッツに帰着できるか?
かな
0731132人目の素数さん2019/05/09(木) 21:52:30.09ID:19c66qNB
自然数xのコラッツ展開のxビット目、すなわちコラッツ展開の対角線に着目したら何か出てこないだろうか?
0732132人目の素数さん2019/05/09(木) 22:16:54.60ID:19c66qNB
巨大数探索スレでは対角線というのは非常に注目されていて
ゲーデルの不完全性定理とかにもでてくる有用な概念らいしぞ。
0733132人目の素数さん2019/05/09(木) 22:21:31.00ID:19c66qNB
例えば自然数xのコラッツ展開のyビット目をcollatz_bit(x,y)と置くとき、
collatz_bit(x,y)をxとyとcollatz_bit(z,z)で表すことが可能であれば、
本質的にコラッツの問題は対角線だけ着目すればいいという結論が出るかもわからない。
そうなったらちょっとすごい。
0735132人目の素数さん2019/05/11(土) 00:46:16.20ID:fcymDsY6
>>717 の x-y∈(2^n)Z という式をみて、ユークリッドの互除法みたいにどんどん小さくしていけないかなぁとふと思った。
0740前786 ◆5A/gU5yzeU 2019/07/31(水) 22:27:24.78ID:IpAiLCvW
覗いてみたらコラッツ展開が注目されてて嬉しい。
コラッツ展開については私も色々考えていますが、>>544で書いた通り 3x+1 に限らず任意の px+q (p,q は奇数) で同様のことができるので、
3x+1 の特殊性をどう出すかが悩みどころ。

>>738
プログラムのことは良くわかりませんが、定理7-2 では 0 の全ての拡張完全割数列が有限項であることを示しているのですか?
0741righ1113 ◆OPKWA8uhcY 2019/07/31(水) 23:12:25.82ID:MdqshjyU
>>740
お久しぶりです。
最近プログラムに大きく手を入れたのですが、そこちょっと引っかかっていました。
示せてないです……
0742righ1113 ◆OPKWA8uhcY 2019/07/31(水) 23:36:04.76ID:MdqshjyU
1つ前のバージョンでは、レベルというものを導入していて、
『レベル2の』0の全ての拡張完全割数列が有限項であること
は実際に計算できたので、それを証明としていました。
0743前786 ◆5A/gU5yzeU 2019/08/01(木) 18:21:35.97ID:VR/ErDyu
>>741
やはりそうですか…。
了解です。

ついでに添削

ch01
・コラッツ予想
>コラッツ操作をおこなう数を 「コラッツ値」 と呼ぶことにする。
既に同じ意味で「初期値」という言葉が使われているので「初期値」で統一してはどうでしょうか。
「コラッツ値」を残すにしても、『初期値のことを「コラッツ値」とも呼ぶ』などと定義した方が意味がはっきりします。

・定義1-1
これも分かりにくいので、
自然数 n を初期値としてコラッツ操作を連続して行ったとき、各操作において 2 で割った回数を並べてできる数列を n の割数列と呼ぶ。
とか。
有限列になる場合、無限列になる場合もここではっきりさせておくべき。
また、「コラッツ列」が未定義なので付け加えるか表現を変えるか。

・定義1-2
>初期値が3の倍数の…
上で提案した定義に則るなら「初期値が」は不要。
このままにしたければ定義1-1を「初期値が n の割数列」に変更。

・3の倍数だけ調べれば良い
「コラッツ逆操作」が未定義。

ch02
・定義2-1
>A[6,-4] or B[1,-2]をつける
「つける」では通じないので、
有限または無限数列 [a_1, a_2, a_3, ...] を数列 [6, a_1-4, a_2, a_3, ...] に写す変換を A[6,-4] と書く。
とか。
また、この時点ではまだ完全割数列を完全割数列に写すことが示されていないので、
その旨を削るか、書くとすれば「すぐ後で示すが」などと書き加えた方がいいと思います。

(重要)
・全ての3の倍数の奇数は、完全割数列で表わされる
ある数が完全割数列で表わされる、という文言がそもそもおかしいですが、
なにより 3 の倍数の割数列が完全割数列であるというのは完全割数列の定義そのもので、ここで示されることではありません。。
タイトルを何かしら変えるべきでしょう。ここで示されているのは
「star変換は完全割数列を完全割数列に写す」
「任意の完全割数列は、ある完全割数列にstar変換を施したものとして得られる」
です。
0744righ1113 ◆OPKWA8uhcY 2019/08/01(木) 18:38:18.77ID:mFTghELa
>>743
添削ありがとうございます。
すごく有難いです。
0745前786 ◆5A/gU5yzeU 2019/08/01(木) 18:51:35.06ID:VR/ErDyu
(重要)
ch03
コラッツ値が非負整数にならないものは禁止するのかしないのかはっきりさせて下さい。
禁止するならば、定義3-1は
n≧0 を 3 の倍数とする。整数列 [a_1, a_2, ...] が n の拡張完全割数列であるとは、
ある 3 の倍数 n'≧0 が存在して
・n' の割数列に、0 や負数が現れることも許してstar変換を有限回施すと数列[a_1, a_2, ...] が得られ、かつ
・n' に対応するコラッツ値の変換を施すと n が得られる
を満たすことを言う。
ってところですかね。

(重要)
ch04
「拡張コラッツ予想」とありますが、これは操作を定義しているだけで予想になっていません。
「拡張コラッツ操作」などと呼ぶべきでしょう。また、ここでも「1回の操作」をはっきり定義しておくといいでしょう。
拡張コラッツ予想とは
任意の拡張完全割数列は有限項である。
とかでしょうか。

あとはプログラムが分からないのでパスで
0746righ1113 ◆OPKWA8uhcY 2019/08/10(土) 16:30:41.61ID:WEEBIQI2
>>743
プログラムを変更して、
帰納法のbase caseは、『(拡張でない)完全割数列が有限項』を示せば良いようにしました。
0の完全割数列は[]と定義するので、有限項です。
0748righ1113 ◆OPKWA8uhcY 2019/08/17(土) 09:46:57.28ID:/+c7d2Vv
すみません、2~3日まってください。
0749righ1113 ◆OPKWA8uhcY 2019/08/18(日) 20:20:16.33ID:/T55OTnz
すみません、もうしばらく時間をください。
0750righ1113 ◆OPKWA8uhcY 2019/08/21(水) 08:04:36.17ID:1YNIVvH6
GitHubのWikiとprogram3は直しかけです。

証明の流れは以下です。

@まず、二つの述語を用意します。
FirstLimited x : xの完全割数列は有限長である
AllLimited x  : xの完全割数列および拡張完全割数列達は全て有限長である
示したい命題は、x -> FirstLimited x です。   ---(a)

A次に、パースの法則の述語論理版を用意します。
"∀x::nat. ¬(∀z::nat. (P z -> Q z))
  -> (∀z::nat. (P z -> Q z) -> (∀n::nat. P n))
   -> P x"
これは定理証明支援系Isabelleで自動証明したので間違いないと思います。

B(∀z::nat. (P z -> Q z) -> (∀n::nat. P n))
のP, QにFirstLimited, AllLimitedを代入したものを証明します。
無限降下法はやめて、整礎帰納法を使います。

C (x -> FirstLimited x -> AllLimited x) は、排中律により真か偽のどちらかです。
・真の場合
  これとBを使って(a)が証明できます。
・偽の場合
  これとBとパースの法則を使って(a)が証明できます。
■ このスレッドは過去ログ倉庫に格納されています

ニューススポーツなんでも実況