コラッツ予想がとけたらいいな

コラッツ予想がとけたらいいな at MATH

[前50を表示]
650:１３２人目の素数さん
16/10/20 20:13:42.76 6y9qoLIu.net
>局所的傾きが大域的傾きより大きいとすると

現状ここは真偽不明なんでしょうか？

651:righ1113 ◆OPKWA8uhcY
16/10/20 20:57:08.94 AWGNcB8y.net
URLﾘﾝｸ(drive.google.com)
局所的傾きが大域的傾きより大きくても小さくても問題ないという事です。

局所的傾き<大域的傾きの場合は、
ずれがlogx_0になって、これが3以上なら問題ないです。

局所的傾き>大域的傾きの場合は、
ずれがlogx_0より小さくなるので、検討が必要です。
これでも問題ない事を言ったのが、>>625です。

652:１３２人目の素数さん
16/10/25 21:40:30.29 cDC1fB5j.net
すまん。
やっぱ俺にはついていけないorz orz orz.
だれか頭の良い奴が来てくれればいいんだが。

653:righ1113 ◆OPKWA8uhcY
16/10/29 14:08:57.19 jW4H6xMA.net
アルティメットチャレンジ届きました。
思ってたより薄くて良い感じです。
パラパラとめくったところ、
自分の考察やコラッツパターンに似たものは無いですねえ。

654:１３２人目の素数さん
16/10/29 18:21:27.58 WZYdEPHx.net
アルティメットチャレンジとやらに載ってる現状出ている成果ってどんな感じ？

655:righ1113 ◆OPKWA8uhcY
16/10/29 20:17:19.13 jW4H6xMA.net
>>632
こんなところですかね。
(W1)5*2^60までは反例がない
(W2)非自明なループがあればその周期は10439860591以上、奇数周期では6586818670以上
(W3)無限に多くの正の整数nは、コラッツ操作で1にたどり着くまでに、少なくとも6.143lognステップかかる（(3x+1)/2でやる）
(W4)The positive integer n with the largest currently known value of C,
　　　　such that it takes Clogn iterations of the 3x+1 function T(x)（(3x+1)/2でやる） to reach 1,
　　　　is n=7219136416377236271195 with C ≒ 36.7169.　　　わかんねえ
(W5)　>>513
後は細かい成果がつらつらと載っているんですが、僕の頭じゃ追えないです。

656:righ1113 ◆OPKWA8uhcY
16/11/05 21:49:46.65 RZr/JMDK.net
これからやること
1.>>620-625の細切れCoq証明とpdf化
2.無限大に発散する方をぼんやり考える

2.だけど>>504を考えています。
（これを書いてくれた事はとてもありがたいです。自分ではとても思いつかなかった）
詳細は書けませんが、>>504から、
無限大に発散する初期値があれば、それは無限個存在するのか？などと思っております。

あと、「ランダムになりたがってる」の方のレスを読み返したりしています。

657:righ1113 ◆OPKWA8uhcY
16/11/14 23:14:49.45 kpU8w0wc.net
すいません休憩してます

658:１３２人目の素数さん
16/11/14 23:28:44.63 DedSNXWK.net
乙

659:１３２人目の素数さん
17/01/10 23:16:43.82 /EwYzUzP.net
グッドスタインの定理というのがあって
これはペアノ算術では証明も否定もできないらしいんだが
コラッツの予想もペアノ算術では証明も否定もできないとかあり得るんだろうか

660:１３２人目の素数さん
17/01/11 17:58:42.63 SHs9UIoK.net
当然あるけど、そっちの方向で成果があるのかどうかは知らない。

661:１３２人目の素数さん
17/01/11 18:57:35.84 JpjtJU9D.net
ペアノ算術で否定できなかったら
ループの反例はないと言えるかな

662:righ1113 ◆OPKWA8uhcY
17/01/11 21:09:59.90 0q3R6j84.net
そうなんですか!?

663:639
17/01/11 21:39:21.73 4dNkupCE.net
>>640
すまんｗ。俺も全然詳しくはないんだが
ループの反例があれば、それを具体的に示せばいいだけだからペアノ算術の範疇かなと思った。
然詳しくはないんだが

664:righ1113 ◆OPKWA8uhcY
17/01/12 17:15:06.15 wPu6fm6S.net
なるほど。

665:righ1113 ◆OPKWA8uhcY
17/01/12 20:05:52.30 l1WvgA7X.net
・ループがある→ペアノ算術で証明できる
・ペアノ算術で証明できない→ループはない
ですか。

666:639
17/01/12 21:42:31.87 LK/xnVvN.net
俺は全然詳しくないのであれだが、
ペアノ算術で証明できないと一口に言っても肯定が証明できないのか否定が証明できないのかで微妙に違うのかもしれん。
正直よくわからん。
誰か詳しい人help

667:righ1113 ◆OPKWA8uhcY
17/01/18 20:32:46.62 ZtV8agPE.net
ところで、面白いことを思いついたのでいいでしょうか。

停止性問題
URLﾘﾝｸ(ja.wikipedia.org)　と
不動点コンビネータfix f = f (fix f)を参考にして。

668:righ1113 ◆OPKWA8uhcY
17/01/18 20:36:37.46 ZtV8agPE.net
Af(xs)を、無限リストを引数に取り、コラッツ遷移が発散したら停止し、
そうでなければ走り続ける関数とします。
このとき、以下の関数Hは存在しません。
・Af(xs)の実行は停止する ⇒ H(Af,xs)はTrueを出力する。
・Af(xs)の実行は停止しない ⇒ H(Af,xs)はFalseを出力する。

Hが存在すると仮定して、
M(B(fix B))を、H(M,B(fix B))=TrueならM(B(fix B))自身は停止せず（無限リストを吐く）、
H(M,B(fix B))=Falseなら[1]を出力してM(B(fix B))を停止するプログラムとする。

・M(M(fix M))が停止したとすると、Mの定義よりH(M,M(fix M))=False。
　Hの定義より H(M,M(fix M))=FalseとなるのはM(M(fix M))が停止しないときのみなので、矛盾。
・M(M(fix M))が停止しないとすると、Mの定義よりH(M,M(fix M))=True。
　Hの定義より、H(M,M(fix M))=TrueとなるのはM(M(fix M))が停止するときのみなので、矛盾。

よってHは存在しない。⇒コラッツ遷移を上から押さえる関数を決定するプログラムは存在しない。
いかがでしょうか。

669:righ1113 ◆OPKWA8uhcY
17/01/18 20:41:25.02 ZtV8agPE.net
・ソース
module Collatz08 where

import Control.Monad.Fix

col :: Integer -> Integer
col 1 = 1
col x = if odd x then 3*x+1 else x `div` 2
af :: [Integer] -> [Integer]
af xs = concat $ map af' xs
af' :: Integer -> [Integer]
af' x = (\z -> z ++ [1])
$ takeWhile (1/=)
-- x*100を任意の関数にする
$ takeWhile (\y -> if x*100 > y then True else error "over!")
$ iterate col x

-- この関数が定義できない
h :: ([Integer] -> [Integer]) -> [Integer] -> Bool
h _ _ = False

m :: [Integer] -> [Integer]
m xs = if h m xs then [1..] else [1]

670:righ1113 ◆OPKWA8uhcY
17/01/18 20:45:22.64 ZtV8agPE.net
・実行結果
*Collatz08> af [1..]
[1,2,1,3,…,2158,1079*** Exception: over!
*Collatz08> h af [1..]
False
*Collatz08> m (m (fix m))
[1]
実際の挙動とは異なりますが、型が合っている事は確認できます。

671:１３２人目の素数さん
17/01/18 20:46:08.84 Lq/a7iIt.net
どこに「Ｈがコラッツ予想である」ことが使われてるのかさっぱりわからん。
これじゃコラッツの予想に関しては何も言えないはずと思うが？？？

672:righ1113 ◆OPKWA8uhcY
17/01/18 20:57:21.21 ZtV8agPE.net
コラッツ遷移を表したAfの停止性を求めるHが存在しないのだから、
コラッツ予想について言えると思うのですが……

673:１３２人目の素数さん
17/01/18 21:22:58.06 Lq/a7iIt.net
>>646のどこに偶数なら2で割り奇数なら3掛けて1足すというコラッツの要素が出てくるんだよ
Af(xs)で仮定してるのは「発散したら停止し、そうでなければ走り続ける関数」だけだろ？
発散するかどうかだけが問題でコラッツの特性は全く使われてないじゃん？

674:righ1113 ◆OPKWA8uhcY
17/01/18 21:33:37.02 ZtV8agPE.net
実際に>>647の（colの）ように実装したら
コラッツを使っていると言えるのではないでしょうか。

675:１３２人目の素数さん
17/01/18 21:47:07.57 Lq/a7iIt.net
col x = if odd x then 3*x+1 else x `div` 2
この部分をほかの式にしても同様の議論が成り立っちゃうんじゃないの？ってこと
同様の議論が成り立つなら特にコラッツの予想について特別なことが言えてるんじゃなくて
もっと一般的なことしか言えてないってことになると思った。

676:righ1113 ◆OPKWA8uhcY
17/01/18 21:49:16.50 ZtV8agPE.net
そうですか……
考え直してみます。

677:righ1113 ◆OPKWA8uhcY
17/01/20 14:00:43.87 +K/zZY0t.net
Afにはコラッツも例えばゴールドバッハもフェルマーの最終定理も含める事ができて、
フェルマーは停止しないからH(フェルマー)は定義できる。
一般のHが存在しないからといって、個別のH(コラッツ)やH(ゴールドバッハ)が存在しないとは言えないのですね。
ダメということで、ありがとうございました。

678:１３２人目の素数さん
17/01/24 14:04:30.35 3mMuxlu+.net
馬鹿の考え休むに似たり

個別の知識を振り回しても正しい議論はできない
「この議論にはコラッツ由来の性質が使われてないから何かがおかしい」
という嗅覚が働かない人間はスタートラインにも立てない
コラッツ予想に限らんがね
永遠に低レベルな領域をぐるぐる回り続けて間違え続けるだけ
時間の無駄だな

679:１３２人目の素数さん
17/01/24 15:51:15.37 jfCA33NU.net
>>656
人生は死ぬまでの暇潰しだからいいんだよ。そんなもんで。

680:１３２人目の素数さん
17/01/24 21:00:07.02 42SFrieH.net
でもちょっとした指摘で間違いを修正できたんなら>>1は見込みあるんじゃないか

681:righ1113 ◆OPKWA8uhcY
17/02/05 04:08:07.85 EG9feBO2.net
>>620-625の細切れCoq証明を書きます。
Require Import Arith.
Require Import Omega.
Require Import Rbase.
は共通です。

682:righ1113 ◆OPKWA8uhcY
17/02/05 04:11:34.06 EG9feBO2.net
>>621の前段
(** 1<(1+1/3x_0)…(1+1/3x_s-1)=2^t/3^s -> 3^s<2^t *)
Theorem t1:
forall (x_0 x_s multi s t :nat),
x_0=x_s -> x_s<>0 -> 3^s<>0 ->
3^s*multi > 1 ->
multi > 1 ->
2^t * x_s = x_0 * (3^s * multi) -> 2^t/3^s > 1.
Proof.
intros.
rewrite H in H4.
apply Nat.div_unique_exact in H4.
rewrite Nat.div_mul in H4.
assert(forall (a b:nat), a=b -> b=a).
intros.
omega.
apply H5 in H4.
apply Nat.div_unique_exact in H4.
rewrite H4 in H3.
auto.
auto.
auto.
auto.
Qed.

683:righ1113 ◆OPKWA8uhcY
17/02/05 04:13:20.79 EG9feBO2.net
>>621の後段
(** tlog2>slog3 -> (t-s)/s>log(3/2) *)
Variable log2 : nat -> nat.
Theorem t2:
forall (s t:nat),
s<>0 -> log2 2=1 -> t*log2 2 >= s*log2 3 -> t/s-1 >= log2 3 -1.
Proof.
intros.
rewrite H0 in H1.
ring_simplify in H1.
apply Nat.div_le_lower_bound in H1.
apply (Nat.sub_le_mono_r (log2 3) (t/s) 1) in H1.
auto.
auto.
Qed.

684:righ1113 ◆OPKWA8uhcY
17/02/05 04:16:31.21 EG9feBO2.net
>>622
(** 0=logx_0+s'log(3/2)-(t-s)/s*s' -> s'=logx_0/(t/s-log3) *)
Variable log2Z : Z -> Z.
Open Scope Z.
Theorem t3:
forall (x0 s t s':Z),
s <> 0 ->
t/s -log2Z 3 <> 0 ->
0=log2Z x0+s'*(log2Z 3 -1)-(t+(-1)*s)/s*s' -> s'=log2Z x0/(t/s-log2Z 3).
Proof.
intros.
rewrite (Z.div_add t (-1) s) in H1.
ring_simplify in H1.
apply (Zplus_minus_eq) in H1.
ring_simplify in H1.
apply (Zplus_minus_eq) in H1.
assert(forall (a b c:Z), -a=-b-c -> a=b+c).
intros.
omega.
assert(forall (a b:Z), -a*b = -(a*b)).
intros.
ring_simplify.
auto.
rewrite H3 in H1.
apply (H2 (log2Z x0) (s'*(t/s)) (-s'*log2Z 3)) in H1.
ring_simplify in H1.
rewrite <- (Zmult_minus_distr_l (t/s) (log2Z 3) s') in H1.
assert(forall (a b:Z), a*b=b*a).
intros.
ring_simplify.
auto.
rewrite H4 in H1.
apply Z.div_unique_exact in H1.
auto.
auto.
auto.
Qed.
Close Scope Z.

685:righ1113 ◆OPKWA8uhcY
17/02/05 04:19:07.94 EG9feBO2.net
>>625
(** [logx_0+slog(3/2)]-[logx_0]+1 > (s+1)log(3/2) -> 1 > log(3/2) *)
Variable up : nat -> nat.
Theorem t4:
forall (x0 s:nat),
(forall (x y z:nat), up(x)-up(y)+1>z -> x-y+1>z ) ->
up(log2 x0 + s*(log2 3 -1)) -up(log2 x0) +1 > (s+1)*(log2 3 -1) ->
1 > (log2 3 -1).
Proof.
intros.
apply (H (log2 x0 +s*(log2 3 -1)) (log2 x0) ((s+1)*(log2 3 -1))) in H0.
assert(forall (a b c:nat), a+b-a+1>c -> b+1>c).
intros.
omega.
apply H1 in H0.
ring_simplify in H0.
omega.
Qed.

686:righ1113 ◆OPKWA8uhcY
17/02/05 04:22:12.48 EG9feBO2.net
>>624の前段
(** [logXX_[s']]-[logY_[s']]=0 -> 1/2<(1+1/3x_0)…(1+1/3x_[s']-1)/k *)
Theorem t5:
forall (XX A multi k:nat),
(forall (x y z:nat), up(x+(log2 y)/z)-up((log2 y)/z)=0 -> 1<2*y/z ) ->
XX=A+(log2 multi)/k ->
up(XX)-up((log2 multi)/k)=0 -> 1<2*multi/k.
Proof.
intros.
rewrite H0 in H1.
apply H in H1.
auto.
Qed.

687:righ1113 ◆OPKWA8uhcY
17/02/05 04:27:02.00 EG9feBO2.net
>>624の後段
(** k<2*multi -> multi*100<271 -> k>=8 -> False *)
Theorem t6:
forall (k multi:nat),
k<2*multi ->
multi*100<271 ->
k>=8 -> False.
Proof.
intros.
omega.
Qed.

以上になります。

688:１３２人目の素数さん
17/02/05 22:36:02.10 DjTDoiGi.net
なるほどわからん

689:１３２人目の素数さん
17/02/05 22:43:20.93 DjTDoiGi.net
sとtの関係ってコラッツの式から出てくるんじゃなかったっけ？
コラッツの式はどこにあるんだろう

690:righ1113 ◆OPKWA8uhcY
17/02/06 02:56:10.14 xKTPqx0h.net
>>660の8行目の
2^t * x_s = x_0 * (3^s * multi) -> 2^t/3^s > 1.
なのですが、左の式を変形すると
x_s = x_0 * 3^s / 2^t * (1+1/3x_0)…(1+1/3x_s-1)
です。 (1+1/3x_0)…(1+1/3x_s-1)=multiです。
このようなこすい変形が随所に出てきます。
（そうしないと解けなかった）

691:１３２人目の素数さん
17/02/07 20:39:35.21 yLGcFgy0.net
仮定の一番初めのx_0=x_sというのはどこから来るんだっけ？
スマンなよく分かってなくて

692:righ1113 ◆OPKWA8uhcY
17/02/08 00:35:51.56 tAqU/1jS.net
もしループがあったら、という背理法を使っているので、
x_0=x_sです。

693:１３２人目の素数さん
17/02/08 20:39:47.83 1hvdQniB.net
なるほど
もうちょっと追ってみる

694:１３２人目の素数さん
17/02/10 20:27:23.32 4PWLgz5n.net
マリオメーカーはチューリング完全
URLﾘﾝｸ(www.ni) covideo.jp/watch/sm30573682

110ルールというのが面白い

695:righ1113 ◆OPKWA8uhcY
17/03/13 05:15:26.67 dJYUxFWr.net
コラッツパターンもチューリング完全、とか分かったら面白いのかなあ。

696:１３２人目の素数さん
17/03/13 20:50:11.36 A8Mi3RiY.net
まあ望み薄だろうな。
チューリング完全なら計算が停止しないパターンがあるはず？

697:righ1113 ◆OPKWA8uhcY
17/04/01 15:59:42.74 wkby9ngI.net
左端を伸ばすパターンはチューリング完全と言えるかもだけど、
それをコラッツパターンにどう繋げたら良いか分からないです。
現状なんにも出来てないです。

698:righ1113
17/04/27 03:59:35.58 NZOaVTiK.net
チューリング完全、ムリでした……
ループのほうのpdfはゆっくりと書いています。

699:righ1113
17/06/03 21:17:02.54 27SYi9gm.net
作成途中ですが、上げておきます。
今は別の事を考えているので中断します。
やる気がなくてすみません。

4-2-1以外のループが無い事の証明
URLﾘﾝｸ(drive.google.com)
　
　

700:１３２人目の素数さん
17/06/03 21:26:11.99 5IRlU4Ze.net
おつ

俺の実力じゃ読み解けないけど読みやすさを意識して書いたんだろなてのは伝わってくるよ。

701:１３２人目の素数さん
17/06/17 23:08:02.85 vqhkVmpO.net
結局この証明の胆ってどこなんだろうな。よくわからん。
ごちゃごちゃ式変形してるけど一見、そこからは特別な情報は出てこなさそうに見えるんだよなぁ
俺にもうちょっと実力があれば付き合ってやれるんだが、すまんな。

702:righ1113
17/06/18 02:08:58.25 xOnz2tO1.net
>>679

胆は5ページ目の
(1+1/3x_0)...(1+1/3x_{[s']-1})がeより小さい
ところかな、と思います。

703:righ1113
17/06/18 02:43:18.07 xOnz2tO1.net
あと、ループする仮定のもとで、
コラッツパターンの左端傾き(t-s)/sと、左端を伸ばすパターンの右端傾きlog(3/2)
が交差する事も重要だと思います。

704:１３２人目の素数さん
17/06/20 21:30:48.98 vNJoeLUD.net
コラッツパターンの左端とか左端を伸ばすパターンの右端ってのは直線なの？

705:righ1113
17/06/21 01:24:06.07 fu38/wPJ.net
あ、直線です。

706:１３２人目の素数さん
17/06/21 18:56:37.20 4uYof9II.net
ループするてことは一周して増えもしないし減りもしないってことだけど
この証明は一周する度に何が減るって議論してるような？
何が減ってるんだろう？

707:684
17/06/21 21:17:55.31 Br1vBJfF.net
うーん左端と右端の差が減るんだろうか？

708:righ1113
17/06/22 12:42:22.70 a+o92jNq.net
>>684

>>620の前準備2より、ループを重ねるたびに、
コラッツパターンと左端を伸ばすパターンのずれが「増える」のです。
で、コラッツパターンの左端と、左端を伸ばすパターンの右端が交差する所で
ずれが3以上になって、
その場所で矛盾するのです。

709:１３２人目の素数さん
17/06/23 20:47:11.82 Aha3AK9Q.net
>[logY_s]と[logX_s]
すまん、この記号[ ]の意味はなんだっけ？切り上げ？

710:１３２人目の素数さん
17/06/23 21:01:44.54 8j+4jyzS.net
>>687
[ ]はガウスの記号、つまり端数を丸めて（絶対値で見た時に切り捨てて）整数にする演算のことじゃないの？

711:１３２人目の素数さん
17/06/23 21:08:08.37 8j+4jyzS.net
>>688訂正
すまん、ガウスの記号の意味は正負どちらでもそれ以下の最大の整数にする演算、つまりfloorと同じ意味だった
ともかく[ ]はガウスの記号だと思うよ
（なぜかガウスの記号には高校数学だと[ ]を使うのに対して、大学以上の数学だと下だけに爪が出てる記号（つまり」とその左右反転形）を使うよね）

712:１３２人目の素数さん
17/06/24 10:26:51.33 crDj8neM.net
コラッツパターンは、コラッツの操作によって得られるもともとの情報群。
複雑すぎて手に負えない。

左端を伸ばすパターンは、コラッツパターンから
情報を落とすことで得られるポンコツな指標。
操作を進めるごとに情報が落ちていくので、どんどん精度が悪くなる。
こんなものがコラッツパターンの実態を捉えているなん�

713:ﾄあり得ないので、コラッツパターンと比較したところで大して得るものは無い。「左端傾き」「右端傾き」といった考え方もゴミである。離散的な対象に対して、大域的にであれ局所的にであれ「傾き」に相当する量を定義したところで、それは極めて大雑把な荒い指標にしかならない。そんな頼りない道具だけでコラッツ予想が制御できるわけがない。

714:１３２人目の素数さん
17/06/24 10:34:09.83 crDj8neM.net
・・・と、御託はこのあたりにして、具体的に間違いを指摘する。
>>677の(17)の不等式が完全に間違っている。(17)では

[s']＝[(log_2 x_0)/(t/s－log_2 3)] ＜ 3x_0

となっているが、分母の (t/s－log_2 3) が非常にゼロに近い場合、

[s']
＝ [(log_2 x_0)/(t/s－log_2 3)]
＝ [(log_2 x_0)/(ほぼゼロ)]
＝ [(log_2 x_0) * (1/ほぼゼロ)]
＝ [(log_2 x_0) * 滅茶苦茶デカイ係数 ]
＞ 3x_0

となり得るので、この場合、不等号が逆転することになる。

「このような可能性は実際には起こらず、確実に [s'] ＜ 3x_0 が成り立つ」

と言うのであれば、そのことを証明しなければならない。
しかし、末尾の coq では証明されていない。

「図を使って傾きを比較することで [s'] ＜ 3x_0 が成り立つ」

と言っているようにも見えるが、図が無い上に、それぞれのパターンを
どのように配置してどこを原点としてどのようにして直線の傾きを
比較するのか文章からは読み取れないので判断のしようがない。

715:１３２人目の素数さん
17/06/24 10:40:58.68 crDj8neM.net
なお、きちんと精査はしていないが、
(1)～(23)のうち、(17),(22),(23)を除く全ての式は
おそらく正しいと思われる。なぜなら、これらの式では

・記号の定義
・単なる等式の変形
・自明な評価による自明な不等式の導出

のいずれかの行為しか行っていないからだ。
パターンのずれとか傾きの違いがどうこうなどと
御託を並べているものの、その実態は上記の3項目のみである。

ちなみに、(22),(23)で間違っている箇所は、途中で(17)を使っているところであり、
それゆえに間違いとなる。従って、実質的には(17)のみが間違いとなる。
そして、それ以外の個所では上記の3項目による自明な行為しか行っていないので、
結局、>>677ではコラッツ予想の難しさを(17)に責任転嫁しているだけということになり、
コラッツ予想について何も言えていないことになる。

716:righ1113
17/06/24 12:53:18.60 JGgmjFB8.net
指摘ありがとうございます。見直したところ、
(t/s－log_2 3) > 0 のところを、
(t/s－log_2 3) > 1 と勘違いしていました。
またしてもダメでした……
お騒がせしました。

717:１３２人目の素数さん
17/06/26 21:23:01.72 1jLGU0ra.net
乙。
頭の良い奴が来てくれたか。
俺も力になれればいいんだが、なかなか難しい。

718:１３２人目の素数さん
17/08/06 18:21:21.93 oDKJI1vJ.net
耳栓をしたら世界が変わってワロタ

719:￥
17/08/06 18:21:56.37 +CYdGQny.net
☆☆☆馬鹿板は数学徒の脳を腐らせる悪い板であり、そやし廃止してナシにすべき。☆☆☆

￥

720:１３２人目の素数さん
17/08/06 20:09:55.82 oDKJI1vJ.net
耳栓をしたら世界が変わってワロタ

721:￥
17/08/06 22:08:57.65 +CYdGQny.net
￥

722:￥
17/08/06 22:09:14.50 +CYdGQny.net
￥

723:￥
17/08/06 22:09:31.49 +CYdGQny.net
￥

724:￥
17/08/06 22:09:48.32 +CYdGQny.net
￥

725:￥
17/08/06 22:10:10.97 +CYdGQny.net
￥

726:￥
17/08/06 22:10:28.01 +CYdGQny.net
￥

727:￥
17/08/06 22:11:05.27 +CYdGQny.net
￥

728:１３２人目の素数さん
17/08/07 03:17:18.68 /yQwEvEc.net
￥さんが数学板に極めて批判的であるのは良く承知していますが、このスレは荒らさないであげて下さいよ
珍しく自分なりに数学をやっている人がその研究経過について報告してくれているのですから

数学板のすべてのスレが腐っているわけではありません
他の板でも腐っているスレもあれば数学板でもこのスレのように「数学

729:」という言葉本来の目的で使用されているスレもあるのですからまた数学板の全てのスレで各スレの投稿者や読者の集合が一致しているわけでもありません（もしそうだと主張なさるならば数学の証明として通用するレベルの論理的な証明か又は２ちゃんねる数学板のログのような客観的で確実な証拠でもご提示ください）板で腐っているかいないか決めつけるのは人の知性の有無を国籍や肌の色で判断するのと同じ乱雑で反知性的な判断であって数学や知性を愛する￥さんに相応しい行動とは思えませんスレ主さんや他の住人の方々、スレ違いの投稿失礼しました

730:１３２人目の素数さん
17/08/07 05:56:13.38 OTMGdlHi.net
>>705
基地外に言葉が通じると思ってるのか？

731:１３２人目の素数さん
17/08/07 06:44:03.01 KEQcYZki.net
昔からあるスレ攪拌のためのスクリプトかなんかじゃないのかね

732:￥
17/08/07 06:47:24.69 /rspiZFz.net
☆☆☆馬鹿板は数学徒の脳を腐らせる悪い板であり、そやし廃止してナシにすべき。☆☆☆

￥

733:￥
17/08/07 08:32:54.67 /rspiZFz.net
￥

734:￥
17/08/07 08:33:11.53 /rspiZFz.net
￥

735:￥
17/08/07 08:33:26.97 /rspiZFz.net
￥

736:￥
17/08/07 08:33:42.15 /rspiZFz.net
￥

737:￥
17/08/07 08:33:57.07 /rspiZFz.net
￥

738:￥
17/08/07 08:34:35.16 /rspiZFz.net
￥

739:￥
17/08/07 08:34:52.14 /rspiZFz.net
￥

740:￥
17/08/07 08:35:08.23 /rspiZFz.net
￥

741:￥
17/08/07 08:35:24.05 /rspiZFz.net
￥

742:￥
17/08/07 08:36:04.26 /rspiZFz.net
￥

743:１３２人目の素数さん
17/08/07 08:44:46.18 0YzkEl/p.net
耳栓をしたら世界が変わってワロタ

744:１３２人目の素数さん
17/08/07 15:14:50.99 /yQwEvEc.net
>>706
現代数学の系譜スレでは￥氏はちゃんと会話をなさってるので
こちらが適切に発言すれば言葉は通じると思ったわけです

745:１３２人目の素数さん
17/08/07 15:17:03.95 0YzkEl/p.net
耳栓をしたら世界が変わってワロタ

746:righ1113
17/10/08 09:15:13.38 StPF7u7V.net
メルセンヌ素数 2^110503 - 1 って
止まらないことないですか？

747:１３２人目の素数さん
17/10/08 11:28:20.81 Cutv7rfi.net
計算機でまわしたのか？
単にデカいから時間かかってるだけじゃないのか？

748:righ1113
17/10/08 11:36:26.39 V4WPWhh+.net
2^110503-1が大体30000桁で、
10時間程走らせて、今45000桁ぐらいなのです。
また止まったら報告します。

749:１３２人目の素数さん
17/10/08 15:27:53.11 m0FVLI/3.net
2^n-1をコラッツの操作かけると3^n-1になるんだろ？30000桁が45000桁になってもさほど特別とは思わんな

750:１３２人目の素数さん
17/10/08 15:58:04.91 Pp5mcjdG.net
>>725で指摘されてるが、2^n-1から始めたいなら、
バカ正直に2^n-1からスタートさせるのではなく、
3^n-1からスタートさせないと無駄にも程があるな

751:１３２人目の素数さん
17/10/08 23:28:04.64 Cutv7rfi.net
ちなみに>>1の計算機だと３００００万桁の数値に対して何コラッツステップ/secくらいのスピードで計算できんの？

752:１３２人目の素数さん
17/10/08 23:28:29.03 Cutv7rfi.net
あ間違えたｗ３万桁ねｗ

753:righ1113
17/10/09 00:59:44.36 Vv+x6w6w.net
奇数→奇数を1ステップとして、
2361コラッツ奇数ステップ/sec　ぐらいですかね。

754:１３２人目の素数さん
17/10/09 01:11:15.90 93q6V3EV.net
すまん、聞いてはみたものの速いのか遅いのかよくわからんｗ
プログラム言語は何使ってんの？

755:righ1113
17/10/09 01:19:17.60 Vv+x6w6w.net
僕もよく分からないですw
言語はHaskellを使っています。多倍長整数が標準搭載されているので。

756:１３２人目の素数さん
17/10/09 01:28:20.34 93q6V3EV.net
Haskellか～
プロトタイプ作るのには良いかもしれんが計算ぶん回すのにはどうなんだろ？
C++とまではいかなくても速度高めの言語も試してみるといいかもね。

757:righ1113
17/10/09 01:44:12.02 Vv+x6w6w.net
そうですね、考えてみます。
そういえば今年の始め頃にこんなことをやっていました。
Go,C++,F#,Haskellでコラッツを計算してみた
URLﾘﾝｸ(d.hatena.ne.jp)

758:１３２人目の素数さん
17/10/09 01:53:47.71 93q6V3EV.net
ん～haskell最速ってホンマかいなｗ
どんな理屈でそういう結果になるのか想像つかないｗ

759:１３２人目の素数さん
17/10/09 02:00:31.03 93q6V3EV.net
haskellだけ多倍長になってないとかかなぁ
うーん。なんか違和感あることはある。

760:righ1113
17/10/09 02:04:02.85 Vv+x6w6w.net
多分、多倍長整数と並列計算の組み合わせが
低コストで上手くいっているのがHaskellだと思います。
自信は無いですがw

761:righ1113
17/10/09 17:38:37.95 Vv+x6w6w.net
>>726
3^110503-1で再チャレンジしました。
一日かかって40000桁まで下がったのですが、これ以上続けるのはしんどいです。
グダグダですみません。

762:１３２人目の素数さん
17/10/10 11:57:48.23 ziN8w0WH.net
停止するかどうかを 3^110503-1 のときに
確かめようとしてる時点で既にグダグダだけどな。
なぜなら、どうせ停止するに決まってるからだｗ
それが 1 になるかは分からないが、少なくとも
停止することは確実だと予想してよいだろう。
無論それ自体も未解決ではあるのだが、
停止「しない」ことが期待されるような良い根拠はどこにも無く、
逆に必ず停止すると思しき良い根拠はいくつもあるわけで。

763:１３２人目の素数さん
17/10/10 22:17:48.67 n27Dzau3.net
例えばループする自然数があったとして、ループの周期が非常に長く履歴がメモリに納まらないようなことが想定される場合、
ループを検出するアルゴリズムとしてどのようなものが考えられるだろうか？

764:１３２人目の素数さん
17/10/11 01:44:51.35 4RhSgzf6.net
>>739
1ステップずつ移動するのと2ステップずつ移動するのを用意して
同時に走らせて、両者の値が一致するかどうかを毎回チェックする。
一致したらループに入ってるし、逆にループに入ってたら
必ず一致するタイミングが訪れる。

765:１３２人目の素数さん
17/10/11 02:00:01.80 qm6Ubkun.net
最小値。

766:１３２人目の素数さん
17/10/11 05:34:15.97 acXKCTJa.net
〔問題〕
自然数nを1つ選び、2nを元に3倍して2を足す操作をk回繰り返す。
k を 1,2,3,… とすると、いつかは 2の累乗になる？
　一般項　（3^k)(2n+1）- 1
ｽﾚﾘﾝｸ(math板:171番)-179
面白スレ２４

767:１３２人目の素数さん
17/10/11 11:00:01.29 qm6Ubkun.net
１３。

768:￥
17/10/23 20:45:36.52 Dl6USvMt.net
￥

769:￥
17/10/23 20:45:57.26 Dl6USvMt.net
￥

770:￥
17/10/23 20:46:15.47 Dl6USvMt.net
￥

771:￥
17/10/23 20:46:40.05 Dl6USvMt.net
￥

772:￥
17/10/23 20:47:01.88 Dl6USvMt.net
￥

773:￥
17/10/23 20:47:18.45 Dl6USvMt.net
￥

774:￥
17/10/23 20:47:37.29 Dl6USvMt.net
￥

775:￥
17/10/23 20:47:54.98 Dl6USvMt.net
￥

776:￥
17/10/23 20:48:12.00 Dl6USvMt.net
￥

777:￥
17/10/23 20:48:33.10 Dl6USvMt.net
￥

778:１３２人目の素数さん
17/12/17 21:47:06.98 VxDAPNtz.net
ABC予想が解かれたとかなんとか
コラッツも解けるといいですね

779:righ1113
17/12/18 03:09:43.02 zmSySbud.net
>>754
そうですね～
成果は出ていないのですが、もう少しだけ頑張ってみます。

780:righ1113
17/12/29 09:10:07.92 miDoSCc+.net
>>570-576を再掲します。
・前準備1
例えばx_sが7,11,17,13,5,17,13,5……とループするなら、先頭2項は外して、
さらに最小値をx_0とおいて、5,17,13,5,17,13……にします。
例ではx_3=x_0になります。
・前準備2　
x_0~x_s-1がループ1周期として（x_0=x_s）、コラッツパターンX_sと左端を伸ばすパターンY_sのビット長は
[logY_s] = [log(x_0*(3/2)^s)]
[logX_s] = [log(x_0*(3/2)^s)+log(1+1/3x_0)…(1+1/3x_s-1)]
です。このときの[logY_s]と[logX_s]のずれがあってもなくても、周期を重ねるごとに[logX_s]と[logY_s]の差は
2log(1+1/3x_0)…(1+1/3x_s-1)、3log(1+1/3x_0)…(1+1/3x_s-1)、……と増大するので、
ずれも際限なく増大していきます。

781:righ1113
17/12/29 09:13:24.23 miDoSCc+.net
ループ1周期sで、コラッツパターンと左端を伸ばすパターンのずれが1、3周期でずれが3と仮定します。
X_3sを3ビット下位へシフトしてずれを消します。これをX_3s'とおきます。
X_3s'=x_0*(3/2)^3s*(1+1/3x_0)…(1+1/3x_3s-1)/8　　です。
[logX_3s'] - [logY_3s] = 0　　から始めて　
[log(x_0*(3/2)^3s)+log(1+1/3x_0)…(1+1/3x_3s-1)/8] - [log(x_0*(3/2)^3s)] = 0
切り上げを外して
-1 < log(1+1/3x_0)…(1+1/3x_3s-1)/8 < 1
logを外して
1/2 < (1+1/3x_0)…(1+1/3x_3s-1)/8 < 2
ここで、x_0がループ中最小で、s<=x_0ならば、
(1+1/3x_0)…(1+1/3x_3s-1) < ((1+1/3x_0)^3x_0)^(3s/3x_0) <= (1+1/3x_0)^3x_0 < e
なので、
(1+1/3x_0)…(1+1/3x_3s-1)/8 < e/8 ≒ 0.339
となって1/2を下回って矛盾します。よってs>x_0です。

782:righ1113
17/12/29 09:16:25.04 miDoSCc+.net
まとめると、
ループ1周期sで、コラッツパターンと左端を伸ばすパターンのずれが1、3周期でずれが3としたとき、
s > x_0（ループ中の最小値）　　です。
あるいは同じことですが、
ループ1周期でずれが1、3周期でずれが3としたとき、
1～nまででコラッツの反例がなければ、
n周期以下のループは存在しない　　　です。

783:righ1113
17/12/30 15:51:01.05 4pni1/3N.net
GitHubにまとめを載せました。
良かったらどうぞ。
URLﾘﾝｸ(github.com)
　

784:１３２人目の素数さん
18/01/13 04:19:02.55 puPuVYkL0
コラッツ予想って、「すべての自然数が
１→４→２→１というループを根とした
二分木で表される」てことだよね？
「すべての原始ピタゴラス数は、｛３、４、５｝を
根とする三分木で表される」っていう定理があるけど
あれの類推でなんとかならないか？

785:righ1113
18/01/21 06:56:30.67 o3XeyIKH.net
新しい証明を考えました。
URLﾘﾝｸ(github.com)
ポイントは、「最下位からの連続するビット1の個数」の帰納法で考えることです。

786:１３２人目の素数さん
18/01/21 21:54:14.87 e4dWohlO.net
>761
1回小さくなることしか証明してない

787:righ1113
18/01/22 00:44:19.88 4mi9P+bz.net
>>762
すみませんが、よく分からないです。
1回でも小さくなることを証明すれば、十分じゃないでしょうか。
nの全ての値がコラッツ操作で小さくなる→n+1の全ての値がコラッツ操作で小さくなる
が言えるので、帰納法により、全ての値がコラッツ操作で小さくなる
ことが言えると思います。

788:１３２人目の素数さん
18/01/22 04:00:15.16 zEZO4ljt.net
8x+3(n=2)→12x+5(n=1)→18x+8(n=0)→9x+4(n=?)
補題1-2がn=1の場合に偽じゃねえかな

789:righ1113
18/01/22 20:40:41.60 CNwla0Dh.net
【補題1-2】を次のように変更します。
旧：￢smaller(n+1)ならば、￢smaller(n)である。
新：￢smaller(k+2)ならば、￢smaller(k+1)である。
これにより、この命題でのsmallerの引数が2以上に制限されます。
>>764の例は
8x+3(n=2)→12x+5(n=1)→ここで打ち止め
となり問題を回避できます。
GitHubも更新しました。

790:１３２人目の素数さん
18/01/23 05:46:43.90 O+AtXeLE.net
問題は「最初の数より小さくなる」かどうかだから次は16x+7で同じことになるね
・2x→x
・4x+1→3x+1
では小さくなっているが
n>2では「最初の数より小さくなる」ことが保証できんのだ
2x→xによって整数全体に移るせいで問題がフラクタル構造持ってる
再帰的な解決はここを回避しないと封じられてしまう気がする

791:righ1113
18/01/23 09:59:19.01 MzJqaum6.net
>>766
すみませんよく分からないです……
じっくり考えてみます。

792:righ1113
18/01/23 10:50:15.55 iVG/+p9N.net
8x+3(n=2)→12x+5(n=1)=4(3x+1)+1→3(3x+1)+1
　　　　　　　　　　　　　　　　^^^^^^^^^^^^^^^^^^^^
　　　　　　　　　　　　　　　　ここでは小さくなっているが、
^^^^^^^^^^
この最初の数より小さくなっていない、でしょうか。
理解しました。

793:righ1113
18/02/03 16:35:17.43 fD/urjTL.net
◆◆◆■■■■　　　　　　　15→127
□◆◆■■■□■　　　　　　23→95
□□◆■■□□□■　　　　　35→71
□□□■□■□■■　　　　　53
□□□□□□□■□■　　　　5
□□□□□□□□□□■　　　1
新しいコラッツパターンを考えました。
◆を追加します。
すると、nの大小=x_sの大小が言えるので、
smaller(n+1)ならば、smaller(n+2)
が言えると思うのですが、どうでしょうか。

794:１３２人目の素数さん
18/02/04 07:22:20.66 mw9eaFXP.net
2x+1→6x+4→3x+2
2x+0→1x+0
をセットの操作として考える
xの係数は奇数なのでxの偶奇で次の偶奇が定まる
xを2x+1、2x+0で置換してもう1セット操作する
xの係数は奇数(というか3の冪)となるのでやはり次の偶奇はxの偶奇で定まる
あとは帰納法で「下位nビットがnセット操作分の変化を定める」のがわかる
下位ビット固定は固定した分しか定まらないのでうまくいかない印象

795:righ1113
18/02/04 20:03:51.85 iMjXyBGA.net
だめですかねえ……
とりあえずExcelを更新しました。
URLﾘﾝｸ(github.com)

796:righ1113
18/02/09 22:41:34.79 6EKEcZuH.net
コラッツパターン2にしたら、
4x+1が小さくならなくなってしまいました。無念。

797:righ1113
18/02/24 14:20:55.93 RYOtT8nZ.net
構成を大幅に変えました。
コラッツパターン2も変えました。

798:１３２人目の素数さん
18/02/27 22:53:52.42 /Yl+hgqj.net
コラッツ問題の解決の役に立つかどうかはわからんが、思いついたので投下。
f:N→N
　f(x)=x/2 (x:even)
　f(x)=(3x+1)/2 (x:odd)
g:N×N→Z
　g(x, n)=#{0<=i<n| f^i(x):odd}
とする。
このとき、0<k<=n に対し、
f^nは{x∈N|g(x, n)=k}上、広義単調増加である。
(i.e. x<y ⇒f^n(x)<=f^n(y))
例1. g(x, 3)=1
2→1→2→1
4→2→1→2
5→8→4→2
10→5→8→4
例2. g(x, 3)=2
1→2→1→2
3→5→8→4
6→3→5→8
9→14→7→11

799:１３２人目の素数さん
18/02/27 22:55:29.10 /Yl+hgqj.net
以下、超略証。
(n=1)
f(2x+1)=3x+2
f(2x+0)=1x+0
(n=2)
f^2(4x+1)=3x+1
f^2(4x+2)=3x+2
(n>2)
k<=n に対し{x∈N|g(x, n)=k}は周期2^nを持ち、
f^n(x+2^n)=f^n(x)+3^k を満たす。
ここから異なる周期間の単調性が、
n=2からは周期の中での単調性が示せる。
(格子状の道の最短経路の曲がり方を一つづつ変えて行くように)

800:１３２人目の素数さん
18/02/28 19:18:14.81 6Xntgk3f.net
>>775
＞(格子状の道の最短経路の曲がり方を一つづつ変えて行くように)
ここがだめ(全順序にならん)なので不成立。
一定の条件のもとで、近い数は近くなる、くらいしか言えてないか。

801:￥
18/04/06 12:28:59.91 I+Mybrk/.net
￥

802:￥
18/04/06 12:29:18.95 I+Mybrk/.net
￥

803:￥
18/04/06 12:29:38.52 I+Mybrk/.net
￥

804:￥
18/04/06 12:29:56.45 I+Mybrk/.net
￥

805:￥
18/04/06 12:30:18.29 I+Mybrk/.net
￥

806:￥
18/04/06 12:30:38.74 I+Mybrk/.net
￥

807:￥
18/04/06 12:30:58.98 I+Mybrk/.net
￥

808:￥
18/04/06 12:31:16.94 I+Mybrk/.net
￥

809:￥
18/04/06 12:31:36.78 I+Mybrk/.net
￥

810:￥
18/04/06 12:31:59.28 I+Mybrk/.net
￥

811:１３２人目の素数さん
18/04/25 11:21:08.33 syWjwryDn
「コラッツパターン」から、
「オンビットで始まってオンビットで終わるビット列」を
考えてみた。“コラッツむし”という。
全体を下位に１ビットシフトして、キャリーを
立ててから算術加算する。（３ｎ＋１）
つぎに、下位からオフビットをクリアする。（÷２）
その挙動が面白い。なんかしら、(1,)7, 31, 127 のどこかに落ちる。

812:１３２人目の素数さん
18/04/25 11:35:51.96 syWjwryDn
“コラッツむし”は、「１ビットシフト」と「キャリーオン」で、
相対的に上位側に「１」だけ移動している。
これは、通常営業だから勘定に入れなくていい。
「下位からオフビットをクリアする」のが、
実質的な移動量になる。
体長１の“コラッツむし”は、「4 -> 2 -> 1 -> 4」のループだから、
最終形態だ。
ここで 2^n - 1 のメルセンヌ数を出発点に取ると
（基本的に、体長が伸びるのは、このときだけ。
なぜなら最下位のキャリーが伝播しない）、
1 に直接

813:落ちなければ、メルセンヌ素数である7, 31, 127 を経由するらしい。

814:１３２人目の素数さん
18/04/25 11:48:27.28 syWjwryDn
まぁ、結局 >>40 のアイディアの焼き直しなんだが、
二次元セルオートマトンとして実際に目で見てみると、
それなりに面白い。
←こっち下位ビット　こっち上位ビット→
として、1101 は
1101
101 +
-----
になり、最下位のビットは 0 になるからクリアされる。
あとは、（メルセンヌ素数ではなく）メルセンヌ数のときに、
体長に関する保存量があるかどうかと、
「伸びてゆくメルセンヌ数」があるかどうかで、
全長に関する限界は示せそうに思う。
たぶん、保存量が「任意のビットパターン」に対して
求められれば、「すべての自然数がメルセンヌ数に
帰着できる」みたいなことが示せそうな気がする。
あくまで「気がする」だけだが。

815:１３２人目の素数さん
18/04/28 16:55:40.82 d9jkS/fs.net
１つ予想を立ててみた。
自然数全体の集合を N とする。
まず木を定義する。
定義
自然数 a に対し、集合 T(a) を
T(a) = {b∈N | a と b はコラッツ操作によって同じ数に到達する}
と定める。
T(a) の形の集合を木と呼ぶ。
コラッツ予想が真であることは、自然数全体が１つの木をなすことと同値である。
で、次のように予想した。
予想
T を木とし、n, k を自然数とする。
このとき、ある a∈T が存在して a≡k (mod n) が成り立つ。
コラッツ予想が正しければ、T は N に一致するので、明らかにこの予想は成り立つ。
逆にいえば、予想が成り立たないような T, n, k が存在する場合、コラッツ予想も偽であることになる。

816:１３２人目の素数さん
18/04/28 16:56:23.83 d9jkS/fs.net
基本的な操作を補題としてまとめておく。
補題
T を木とする。このとき以下が成り立つ。
(1) a∈T かつ a が偶数 ⇒ a/2∈T
(2) a∈T かつ a が奇数 ⇒ 3a+1∈T
(3) a∈T ⇒ 2a∈T
(4) a∈T かつ a が偶数かつ a≡1 (mod 3) ⇒ (a-1)/3 ∈ T
２つの自然数 a,b が同じ木に属することは、(1)～(4) の繰り返しによって
一方から他方に移ることができることと同値。

さて、例えば n=1,2 の場合は予想は明らか。
n=3, k=1 or 2 の場合も難しくはないが、証明を述べておく。
命題
T を木とし、k=1 or 2 とする。
このとき、ある a∈T が存在して a≡k (mod 3) となる。
証明
任意に b∈T をとる。
b が 3 の倍数でない場合、b, 2b のいずれかが mod 3 で k に等しくなる。
2b∈T なのでOK。
b が 3 の倍数の場合、b=2^i*c (c は奇数) となるように非負整数 i, 自然数 c をとれば、
c∈T, c は奇数かつ 3 の倍数となる。
さらに 3c+1∈T であり、3c+1≡1 (mod 3) となる。
よって、上の場合に帰着されてOK。□

まだいろいろと書けることはあるけど、反応を見ながらということで。

817:righ1113
18/04/28 17:56:49.19 UAXb8Z2X.net
考え方として、
いくつもの木を考えるのですか？
それとも1を含む木T1のみに注目するのですか？

818:786
18/04/28 18:15:59.36 d9jkS/fs.net
全ての木を考えます。
それが１つなのか複数なのかは分かりませんが。

819:righ1113
18/04/28 18:26:23.27 LOcVhBQa.net
なるほどありがとうございます。

820:１３２人目の素数さん
18/04/28 18:28:10.02 zCYrfxzC.net
お、新人か。

821:１３２人目の素数さん
18/04/28 18:42:45.61 zCYrfxzC.net
ぜひ新しい風を吹き入れてほしいね。

822:786
18/04/28 18:53:42.76 d9jkS/fs.net
これを書こうと思って忘れていた。
コラッツ予想は初期値が奇数の場合だけ調べればいい、というのは明らかだが
>>790の予想が正しければそれを一般化できる。
すなわち、ある n, k について予想が正しければ、
「コラッツ予想は a≡k (mod n) を満たす自然数 a が初期値の場合だけ調べればいい」
と言える。
>>795 >>796
よろしくお願いします。

823:１３２人目の素数さん
18/04/28 19:00:55.51 zCYrfxzC.net
modに関しては2と3には何かあるかもしれないが例えば5はどうか？といわれるとちょと疑問
今の時点ではね

824:１３２人目の素数さん
18/04/28 20:44:50.70 aSLESMuD.net
グラフ理論に「木」があるから名前は変えた方がいいかもね
グラフ理論といえば、コラッツ操作による有向グラフとしてなんかできないかなー、
と昔考えたけど、グラフ理論で扱われるのは有限頂点のグラフだった……

825:１３２人目の素数さん
18/04/28 20:47:56.57 zCYrfxzC.net
いや、まさにグラフ理論の木のつもりで書いたんじゃないか？

826:１３２人目の素数さん
18/04/28 21:05:09.07 aSLESMuD.net
というか「木」は数学では同値類になるか。
自分が書くならこんな感じ。
関数 f:N→N を
f(x)=x/2 (x:偶数) f(x)=3x+1 (x:奇数)とする
x,y∈Nに対し, x～y⇔∃i,j∈N, f^i(x)=f^j(y)
は同値関係となる。

827:１３２人目の素数さん
18/04/28 21:09:57.55 aSLESMuD.net
イメージは1を根とする木かな。
わからなくもないけど
・頂点が無限
・1→4→2→1のループがある
なのでなおさら木とは呼びづらい。

828:786
18/04/28 21:23:20.77 d9jkS/fs.net
確かに「木」だと誤解を招いてしまうかもしれませんね。
「束」のように複数の意味で使われる例もありますが…
良い名称を思いついたら変えようと思います。

829:１３２人目の素数さん
18/04/29 00:40:21.09 daW9MuG1.net
うーん、やっぱり木が一番しっくりくる。
もうしばらく様子を見ます。
同値類を用いた定義も承知していますが、
一応高校数学の範囲で理解できるよう上のように定義しました。
あと、グラフ理論では無限個の頂点や辺を持つグラフも扱っていたと思います。

予想についての結果をひとつ追加。
命題
任意の木は 3 の倍数を含む。
証明
T を木とし、任意に b∈T をとる。
b が 3 の倍数の場合、示すことはない。
b が 3 の倍数でない場合、
b は mod 9 で 1,2,4,5,7,8 のいずれか。
ここで、Z/9Z において 2 は原始根であるので、
　b*2^d≡1 (mod 9)
を満たす d∈N が存在する。
b*2^d∈T かつ b*2^d は偶数で b*2^d≡1 (mod 3) なので、
　c=(b*2^d-1)/3
とおくと c∈T である。
さらに b*2^d-1≡0 (mod 9) より c=(b*2^d-1)/3≡0 (mod 3) なので、T は 3 の倍数を含む。 □

830:１３２人目の素数さん
18/04/29 01:27:39.57 Z6W4RKDj.net
ふーむ。
例えば同様の議論で他の倍数も通用したりするの？

831:786
18/04/29 18:35:28.76 daW9MuG1.net
>>805
n=3^e, e∈N の形のときは同様に議論できます。これから書きます。
それ以外の場合、Z/3nZ において 2 が原始根になりえないので、全く同じ議論でというわけにはいきません。
n=4,8,16,… の場合は議論するまでもなく成り立ちますが…
ちなみに、ある n に対して n の倍数が木に含まれるかという問題は>>790の予想において k=0 の場合ですが、
n が奇数のとき、これは k が他の値の場合よりも難しいと思います。
n=3 の場合もそうでしたが、n=5 あたりを考えてみても分かります。
これもそのうち書こうと思います。

n=3^e, e∈N の場合を考える。
補題
任意の 2 以上の整数 e に対して 4^(3^(e-2)) ≡ 1+3^(e-1) (mod 3^e)
証明
e=2 のときは (左辺)=(右辺)=4 よりOK。
ある e で成り立つとすると、
　4^(3^(e-2)) = 1+3^(e-1)+3^e*m, m∈Z
と表せる。このとき、
　4^(3^(e-1)) = (1+3^(e-1)+3^e*m))^3 ≡ 1+3^e (mod 3^(e+1))
より、e+1 でも成り立つ。□
（続く）

832:786
18/04/29 18:36:40.20 daW9MuG1.net
補題
e を 2 以上の整数とする。
このとき、Z/(3^e)Z において 2 は原始根である。
証明
2 の位数を d とおく。
2^d≡1 (mod 3^e) より 2^d≡1 (mod 3)
したがって、d は偶数である。
また、d は φ(3^e)=2*3^(e-1) の約数である。
ここで、前補題より
　2^(2*3^(e-2)) = 4^(3^(e-2)) ≡ 1+3^(e-1) ≠ 1 (mod 3^e)
(≠は「≡でない」を表すとする)
なので、d=2*3^(e-1) となるしかない。
したがって、2 は原始根である。□

定理
T を木、e を 2 以上の整数、k を任意の自然数とする。
このとき、ある a∈T が存在して a≡k (mod 3^e) が成り立つ。
証明
・ k が 3 の倍数でない場合
3 の倍数でない b∈T を任意に取る。
2 が Z/(3^e)Z の原始根であることから、
　b*2^d≡k (mod 3^e)
を満たす d∈N が存在する。
a=b*2^d とすればよい。
・ k が 3 の倍数である場合
3 の倍数でない b∈T を任意に取る。
2 が Z/(3^(e+1))Z の原始根であることから、
　b*2^d≡3k+1 (mod 3^(e+1))
を満たす d∈N が存在する。
このとき、a=(b*2^d-1)/3 とおくと、
a∈T かつ a≡k (mod 3^e) となる。□

833:１３２人目の素数さん
18/04/29 22:12:16.24 Z6W4RKDj.net
mod 5とか mod 7について何か出すのは難しいかもしれないけど
3^n-1についてとかなら何か出せるんだろうか？

834:786
18/04/30 11:15:04.08 RzdNNNxX.net
>>808
「何か出す」の意味がよく分かりませんが
mod 5, mod 7 の場合は任意の k について予想が成り立つことが分かっています。
3^n-1 の場合は特に考えたことはないんですが、何かアイデアがあれば教えてください。

やはり先に分かっていることについて一通り書いた方がいいですね。
以下、0≦k≦n-1 とします。
次の場合は予想が成り立つことが分かっています。
・n=1,k=0
・n=3^e, e∈N, k は任意
・n が 5 以上の素数、Z/nZ において 2 が原始根、k≠0
・n が 5 以上の素数、Z/nZ において 2 が原始根、n≡2 (mod 3), k=0
・n=7, 13, 17, k は任意
また、次が分かっています。
・m∈N とする。もし n=3m の場合に任意の k で予想が正しければ、n=2m の場合も任意の k で予想は正しい。
これにより、n が偶数の場合は n が奇数の場合に帰着されます。

835:786
18/04/30 11:45:54.34 RzdNNNxX.net
偶数から奇数への帰着について先に書いておきます。
定理
m∈N とする。もし n=3m の場合に任意の k で予想が正しければ、n=2m の場合も任意の k で予想は正しい。
証明
T を木とし、n=2m とする。
k が奇数の場合に証明できれば、奇数に 2 をかけていくことで k が偶数の場合も証明できる。
k を奇数とする。
仮定より、ある b∈T が存在して
　b≡(3k+1)/2 (mod 3m)
となる。このとき、
　2b≡3k+1 (mod 6m)
であり、2b∈T, 2b は偶数かつ 2b≡1 (mod 3)。
よって a=(2b-1)/3 とおくと a∈T かつ a≡k (mod 2m)　□
>>807 の結果と合わせれば、
n=2^d*3^e の形の場合、任意の k で予想が正しいことになります。
また、私見ですが、n が偶数の場合はこの定理によって奇数の場合に帰着させる以外の手はなさそうに思います。
他の方法がありそうならご一報ください。
そういうわけで、今後は n が奇数の場合のみ考えようと思います。

次ページ