-
- いいね！0
na2hiro 💿 93連休終わった
@na2hiro
コラッツ数列の項数の数列は[1] [2] <8> [3] *6* <9> =17= [4] 20 *7* 15 <10> 10 =18= 18 [5] のように，倍になると１増えるという規則性があるので，偶数はlog(N)オーダー．しかし奇数は結構ランダムに見える．
2011-01-23 03:17:53
na2hiro 💿 93連休終わった
@na2hiro
などと，センター数IIBのプログラミング問題でコラッツの問題(角谷の予想)が出題されたので，チャットでコラッツブーム
2011-01-23 03:20:20
na2hiro 💿 93連休終わった
@na2hiro
どういうところで合流するのか調べてみた．すると簡単．まず全ての数はその倍の数から飛んでくる．次に3(2n+1)+1=6n-2の時に，奇数の３倍に１を足したものなので，2n+1から飛んでくる．よって6n-2の時必ず合流する． http://pastebin.com/Qutp1CRh
2011-01-23 03:40:42
na2hiro 💿 93連休終わった
@na2hiro
6n-2のとき必ず合流するというより，奇数のときに飛んだら必ず合流すると言ったほうが分かりやすいな．それにしても，これほどシンプルに見えるコラッツ問題が未解決とは不思議だ．
2011-01-23 03:47:07
na2hiro 💿 93連休終わった
@na2hiro
コラッツ数列を書き出すSchemeプログラム．http://ideone.com/CMmTa ２７の暴れっぷり．でも奇数になったら合流するんだから半分の確率で合流だよなあ．
2011-01-23 04:07:08
na2hiro 💿 93連休終わった
@na2hiro
コラッツ問題を言い換えると，「全ての数字は，１から始めて２倍にするか，(可能な場合)１を引いて３で割ることをくり返すことで，到達できる」ということか．
2011-01-23 04:12:34
na2hiro 💿 93連休終わった
@na2hiro
ビット演算で考えると計算が楽だ．２で割るのは最下位ビット0を取り除く，３をかけるのはその数に左に0をシフト(=２倍)したものを足すことで表現できる．1001100→10011→10011+100110+1=111010→11101→1011→10001→1101→101→1
2011-01-23 04:40:29
na2hiro 💿 93連休終わった
@na2hiro
1に合流するのは100 10000 1000000 100000000，これに合流するのは1 101 10101 1010101だ．即ち，1+10+1=11+1=100，101+1010+1=1111+1=10000．10101+101010+1=111111+1=1000000
2011-01-23 04:53:45
na2hiro 💿 93連休終わった
@na2hiro
あのコラッツがビット演算になったよ!! http://gyazo.com/b584be2c2a60eb6d0089252b378b78ee.png
2011-01-23 05:48:28
na2hiro 💿 93連休終わった
@na2hiro
ビットでcollatzを１演算ずつ表記するプログラム． http://ideone.com/AngxX 10101が起こると00000になること，末尾が11111だと，桁数が増え末尾の11111の列が少しずつ短くなることは読み取れるが，それ以外はランダムに起こっているように見える
2011-01-23 06:40:13
na2hiro 💿 93連休終わった
@na2hiro
数学って純粋に不思議なことがあるね．コラッツ問題は，無限に広がる世界が，全てびっしり１本の木とその枝で張り巡らされているということだ．
2011-01-23 07:15:32
na2hiro 💿 93連休終わった
@na2hiro
コラッツ演算で１０回以内に１にたどり着くグラフ http://gyazo.com/d5fbc9986001251d4124bbc87c9a8519.png (Graphviz使用)
2011-01-23 17:19:43
na2hiro 💿 93連休終わった
@na2hiro
コラッツ問題の遷移図をSVGで書いたよ!30などはサイズ注意 http://81.la/img/collatz10.svg http://81.la/img/collatz20.svg http://81.la/img/collatz30.svg
2011-01-23 18:28:42
na2hiro 💿 93連休終わった
@na2hiro
3(2n+1)+1=6n-2の時にのみ，2n+1から飛んでくるので，3の倍数になったらもうそれ以上が一本道なのは当然か．
2011-01-23 18:44:26
na2hiro 💿 93連休終わった
@na2hiro
やばいな，collatz30.svg見てると全然飽きない http://81.la/img/collatz30.svg
2011-01-23 20:20:10