3n+1 problems -- Collatz conjecture python code

這裡介紹一個神奇的問題，我也是最近才看到，數學家稱作3n+1 problems -- Collatz conjecture.
問題簡單到爆，卻仍然未解
給一個數列，起始點是n，一個正整數
f(n)={n/2  | if n is even;  3n+1 | if n is odd}
keep 使用 f(n)會得到很多很多項。
ask 是否有一項是1?

就這樣
先試試看 n=12 
我們可以得到:
[12, 6, 3, 10, 5, 16, 8, 4, 2, 1]

n=19
[19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

這個問題是open problem
因為目前知道的都是這樣。....

放下我自己寫的小code...如果有興趣可以試試看 g(27)
也會看到他terminate
這個問題可以視為 halting problem 的子問題。

2013 莊敬校慶 陳米亞

 2013 莊敬校慶 陳米亞 — at 莊敬高職.

November 15, 2013 at 10:13 AM ·
我這周期中考太忙了 好不容易才有時間出相簿呢 米亞超讚的ㄟ 這邊還有另一張合照喔 哈哈 謝謝米亞幫我期中加油ㄟ 還過得去啦 明天我又要出去拍了ㄟ

我這周期中考太忙了 好不容易才有時間出相簿呢 米亞超讚的ㄟ 這邊還有另一張合照喔 哈哈 謝謝米亞幫我期中加油ㄟ 還過得去啦 明天我又要出去拍了ㄟ

OMG:射了

林蔓雯 at 86小舖 西門中華店.

林蔓雯 at 86小舖 西門中華店.
November 14, 2015 at 10:30 AM · Taipei, Taiwan ·



WOOOO 想來當初第一次看小蔓 是應用大展 整整兩年前了....上次看到忘了
小蔓今天說 :她很久無見到我了 應該是超級久
我說:我這段時間在忙
她說:忙著拍妹喔 ? 現在不是在期中考?
我說忙著讀書啦XD 當初大一升大二 現在也快畢業了 WOO


其實今天門口超多人擠爆店門都是為 李毓芬..不過偶們不是XD
粉專 林小蔓

台大和交大弦論組 String Theory and String Group

相信大家都聽過String theory. 大家google 查一下，或是再依些科普聽過這東西，很玄妙什麼的，清大賣雞排的老闆會string，或是可以看到很多文章批評:

not ever wrong 什麼的。

敝人過去曾經在和交大and 台大的string group 待過一年多，發過三篇papers，參加過很多string group 的研討會。

關於這主題，我有很多可以分享的，可惜，時間不多，能寫多少就會寫多少。

如果還有鬼島年輕人要讀string，不讀就會死掉。可以去看台大賀培銘教授個人網站。

上面說得夠多了。

或是高涌泉的文章，世界上還有很多東西很好玩的，大家不要想不開唷。

附上一些活動照片，老了呀

2016/11/10-11/11 9th string workshop

蘇格貓底咖啡廳

在新竹兩天下來，聽了好多聽不懂頭很痛的東西，但卻是高興 因為很多國外教授+日本教授，交大和台大的教授還有同學們都認識 除了可以跟他們聊天以外，今天還和我們之前看得paper的ucla大咖本人，教授聊天。

我用我的破英文和他聊了十多分鐘XD
其實這樣的生活模式我是喜歡的，晚上還有晚會，免費的午餐和晚餐，吃超飽的，大家討論一些生活啊，或是學問上，很難的東西，未來阿。

昨天也送日本的學生回台北，英文真的重要，溝通都要用英文 漸漸的會比較習慣，我知道，即便我們真的沒有搞下去了，也不錯，曾經接近過，看過，感受過就好了，好了..

.真的到台大後，發現真的參加很多學術活動，很多JOURNAL CLUB MEETING等 知道別人把你當人才看 即便....未來不知道能否留在學校靠這吃飯 至少 我們曾經經歷過一些回憶

是我們自己喜歡的。

 
 

底下附錄一下string theory 怪談

我大二跟台大材料冠傑談到 STRING THEORY 說 數學物理學家 想知道 我們能不能證明 世界是存在的 或是 世界是"邏輯不矛盾"的存在

你能不能寫出一個數學模型 他是沒有矛盾的 他有世界上出現的基本現象 結果太困難了 很多天才跳進去 直到1984年 超弦論出現

史上第一個 數學 可以描述世界所有自然現象本質的理論

人類在地球200萬年 還不能證明 我們世界是真的 沒有邏輯 矛盾的

有點像 電影 你怎麼知道自己處在虛幻世界裡 主角 開車到世界的邊緣 發現那裏是網格 或是 主角發現有些東西違反物理定律 他醒悟到這是假的 超弦論說這世界一定要10維的 而且有個MOTHER 在11維的世界 我們的宇宙可能就像一個薄膜 在11空間的世界裡飄著 然後模跟模會撞擊

宇宙可能無限的大爆炸循環

冠傑:這樣聽起來 難怪你們會瘋掉 這樣好像世界一切都沒意義了

  

Fast multiplication of Two polynomials

Fast multiplication of Two polynomials
這東西也是開了我眼界，你想兩個多項式乘法能有多困難，就是term by term的乘出來，然後加起來。
這樣當然需要N^2次的乘法(兩個多項式都是N degree的話，係數乘完以後再加起來。)
偏偏有人就是想要搞得 NlogN 的演算法 來計算這東西。
也算了嚇到我這種數學人。

以下是我看網路上影片作的筆記，主要就是Fast Fourier Transform+ Discrete Fourier Transform
這最古老 可以reference to Gauss.

但好滿玩的: 給大家看看唄

新竹冷風二六食堂

看以前的老動畫，老電影，聽那些音樂感嘆想哭，自己口口聲聲說以前好，可根本忘了以前，仔細想，除了一直讀數學+物理
確實，大學整天想早畢業，想回家拍照，到台大後，整天忙研究，修課論文，之後準備英文，想出國，整天腦袋，轉來轉去就是這些東西，日復一日，後來入伍，整天只想退伍算時間，
不看這些東西，真的完全忘了自己以前是什麼樣子，
全忘了，忘了自己國高中愛的東西，
淚崩了。

推薦一家新竹老吃的日本料理:

二六食堂

很棒，日本料理非常棒，食物很豐富。

Approximation Algorithm for some NP complete problems

There are some Np hard problems we know, although we can not get a exactly answer, there are still polynomial time approximation algorithms. 

Go back to Main page Notes for Complexity theory

Introducing some good algorithms for Vertex covering and compare it with Greedy algorithm.

 Introducing the K coverage problems and their approximation algorithms

 Introducing the TSP coverage problems and their approximation algorithms

最近剛好看了 clay 千禧年數學難題 有個 NP=P? 之前每次想大概了解在幹啥 都看無 最近看了一些演算法介紹 漸漸覺得很帥 這問題難怪很難~~ P :就是那些可在多項式時間解出的問題的集合 NP:就是 給你一個解 你可以帶進去驗證 只需要多項式時間的問題的集合

比方給你一個高次方程 你要解 一定很難 但要你驗證一個數字是不是解 就簡單多了 這問題抽象上是說 是不是 這兩個問題的難度相等...

感覺就不相等...但目前沒有證明 NP=P?集合上的相等

比方銷售員問題 一個銷售員 跑20城市 每個城市彼此連接 他要跑完 每個都只跑一次 繞回原點 求最短路徑 這個計算量要算20! 全部路徑加起來比較 就算一秒跑一百萬次 應該也要幾千年 但有辦法驗證你的路徑是不是最短 不用太長時間 指數時間 是否可透過某些CLEVER方法簡化到多項式時間?

頗有趣 而且很難 銷售員問題是個NPC問題 意思是如果誰可以證明銷售員問題是個P 那就P=NP!! 所有NP問題都可以用P解 世界是很美好的 在多項式時間可以解出 不過我猜應該不是這樣 想到近年很紅 量子電腦 只要三千個位元 就是可以超過 地球上所有電腦的總和 但目前量子電腦只能-273K運行 而且只能16位元 XD 假設量子電腦問世 銷售員問題應該只要一秒而已

千禧年的數學難題 光是敘述和看他們的介紹就可以學到許多有趣DER 統計 我到現在 大概可以敘述內中四個題目(共七個)了

斐陶斐 Phi Tau Phi ( φτφ)是啥 (能吃嗎)

2022 選舉到了

又有人提出台灣最神秘組織之一 phi tau phi

高虹安 上節目說他有

大學部學士班每一學院可推薦1%應屆畢業生品學特優者入會，作為學術榮譽。全台共計57所分會

整理一下 我對 高虹安 最近對 φτφ的新聞的看法

讀輸 已經沒蒿 幫高虹安 整理一下 在我看來

φτφ 號稱什麼菁英啦 如今在極樂島上

早輸給 tier 2 網紅 電競 直播 實況 Yt 因為這些人做自己

像是 廖老大 館長 連千 勾惡 烏鴉 蘭小明 鳳梨 蛋塔

反骨 張家兄弟 等等不及備載

更輸給 tier 1 台灣價值配二代 像是 九萬 秉樞 介佑 允恭

可惜阿!!! 可憐阿

從83年 410教改開始 加上少子化 鬼島讀書就不是像李登輝當年 念一個洋博 就有18%回到大學任教 有當年 爸爸媽媽喜歡的那種安穩 那種七年級生愛得要死的 五子登科 結婚生子買車買房成家立業

現在讀輸 沒有謝謝

現在的 φτφ 連竹科開獎都打不贏 大輸給 gg發哥滷肉螃蟹

遑論 對抗 做自己網紅 跟 台灣價值超二代

φτφ 早已就沒蒿 讀書 早就沒老天看見 五濁惡世

高委員 應該及早看破 這些 讀輸 因為老天已經不愛讀書了 輸爛了

渔父莞尔而笑，鼓枻而去，乃歌曰：. '沧浪之水清兮，可以濯吾缨。沧浪之水浊兮，可以濯吾足

任汝千般快樂 無常終究到來

畢業時。一切成績悉皆散壞。一切分數悉皆捨離。一切威神悉皆退失。成績分數。獎狀名次，千萬經卷。如是一切無復相隨。 更改自普賢行願品

第一次來到本版的好友們 主人翁期待你們到來，本網站主要談以下內容:

人生 讀書 鬼島 數學 物理 showgirl辣妹 網路賺錢 運彩 撲克

歡迎多來欣賞 

說說故事:

有個神祕獎項，在鬼島的大學體制叫做斐陶斐。來自於一個美國人很早以前在中國創的。 看維基找歷史:Phi Tau Phi - Wikipedia
大概就是頒給鬼島大學生。每一間大學前1/100. 有時候要一個學院。每一年整間學校可能就只有二十幾個。
簡單講:就是畢業時院內綜合前幾名。

鬼島沒幾個人知道這獎項，因為不有名，加上得到的人也沒有像國小國中一樣搞的超級盛大，你乾脆想成市長獎in 鬼島大學。

如果好奇，想要知道誰拿過這些獎項，

可以去看 中華民國斐陶斐協會，裡面有歷年拿得獎項的人。

這些人當初都是系上最前面(成績，可惜人生不是前面的)的人。

頒獎完以後，給一個獎狀，給你一個徽章。然後會有好吃的食物，就這樣。徽章個別學校略有不同，按照ptt說法

很多主管不知道這個獎項

儘管 他看起來是最強的獎項 因為必須要拿過很多次書卷才行

獎狀在這 X!

我很好奇，斐陶斐應該去調查當初這些拿獎的人，後來的人生歷程，看看他們是不是真的有成功，才知道這樣有沒有意義。

這獎，敝人也拿過，也算是四大的斐陶斐，但我總覺得無啥意義，也是浮雲，交個女朋友大學好好玩過會實在點，那些獎狀分數成績，最終也不過成空。而且申請學校也沒屁用，因為海外學校不一定知道，知道也不算真的很強，第一名畢業就只是會考試和考古題，體驗人生才是真的。

不要想要去 網站上 找我是誰 我過很差 沒女友沒錢沒房沒車 沒奶茶沒火鍋沒家人沒朋友身邊 不想毀了學校名聲

一個獎也不過多了一個說嘴和發一篇廢文的空間罷了。

好了! 都過去了，管他。

拿phi tau phi 又怎樣? 老天看不到 還是薪水輸滷肉 輸竹科開獎

別再查 這獎沒蒿 不能五子登科 不能有人看到

在你的世界 我偶爾只是個 不同的過客就夠了 答應了我 你會很快樂 幸福到處隨手可得 把眼淚全都流乾了 把快樂都定格 就這樣好了

後記:

之前 我無奈跟方丈講 問他以後換行搞數學怎麼樣 他:你為何這樣問 我:我看現在高能物理搞頭不多 而且我對數學也興趣不錯 也好找工作和教職 

方丈:是無錯 數學系博後時間少 而且全世界微積分的教學肯定比普物多 商學院也要學微積分線代
的確教職較多 loading重
喔 你出國讀書就為了當教授嗎?

我:阿不然咧 我對這些有興趣沒錯 可我就是想躲在大學裡 聽說出社會很恐怖 我就想放寒暑假領錢 不想去社會 我沒本事

方丈:喔 你去社會上可以遇到各式各樣人事物 你不知道大學很無聊嗎 你如果不愛做研究是很無聊的 當然你也可以 把大學當一個爽缺 可是這樣只是在浪費你自己的生命而已 人總要找一些自己覺得有意義的事情做~~

我:你!!!!! 哀





補充文:


替代役 與國小獎狀
最近才發現，小學變了，以前小學一個班，都有市長獎，區長獎，局長獎，等等等，像我們一般人，上高中以後就無法拿獎啦，因為大家競爭越來越激烈:
現在國小變了，以前一個班大概只有一半人可以得獎，現在改了，人人有獎，很多不知道有啥意義的獎， 連名字都聽不懂，勤學獎，環保獎，xxxxxx獎。
我問了一些老師，他們說，這樣小孩才不會難過呢，家長也不會難過，這有啥意義我想?
獎狀，從小拿多了，可能比冥紙還不如，冥紙搞不好死後真的有用，獎狀再多，終究成空，都是幻化的，有人說:這樣可以給小孩子信心!!!! 給他動力~~ 在我看來，給一個希望再將他拿走
，不如不要給他。以前某補教師說:你出去外面，只有第一名才可以說，第二，那就不用說了。
，很少人有辦法記住第二名der，只能記住第一，我騙了你，讓你以為你很優秀，跟他人一樣，自己也有非凡天賦，以後妳離開學校，被現實打倒在地板上，才知道空!!!
鵬程萬里，我聽過很多次:，我聽到怕了，聽到冷了。


就跟 小馬哥 要帶大家逆風高飛 可惜一直逆風 沒有高飛
關關難過關關過 最後是 天天難過天天過

Interactive proof complexity class

這些筆記都是看影片做的，某種程度上是沒有版權的，但如果要抓的，還是可以支持一下本網誌上的各式各樣的連結唷。謝謝



Go back to Main page Notes for Complexity theory
Interactive proof complexity class introduction

Prove that unSat belong to IP.

Halting problem 停機問題有多難

記得第一次聽到 Halting problem 時候，沒有覺得他那麼難，至少感覺上來說。儘管最後大家用到高等微積分裡面的Cantor的對角化法。但感覺還是還好，就是對角化法的應用而已。

可是我們可以試想如果可以的話，到底能解決啥問題?
答案是，可能目前超難的幾個數學問題都能被解決!!!!!!
先來敘述
Halting problems: 是否存在一個Turing machine algorithm
可以決定另一個 turing machine + input 是否會halts or loops forever. (停止或是進入無限迴圈)

Turing 圖靈給的解答是 : 不存在!!!!

證明:
假定存在一個D, 給一個M(turing machine 和一個 input, x) 
D(<M,x>) = 如果M(x)無限迴圈 輸出0
如果 如果M(x)停止 輸出1.

proof:
假設存在這個D，那我製造一個L 機器 定義如下
L(<M,x>)=如果M(x)無限迴圈 輸出1; 如果M(x)停止 輸出0. 這是可以做到的，因為D存在，L存在。
現在問:
L(<L>) 是什麼?
注意 by definition:
L(<L, L>) 要問 L(L) 是否停止或是無限迴圈。
如果  L(L)=0; 表示L 吃掉自己 會停止，但L(L)= 反過來的 D(<L, L>)
表示D(<L, L>)=1. 定義 L(L) 會無限迴圈。矛盾!!!!!!!!!!
如果假設反過來，也會是對的。

所以D does not exist.

計算機複雜度中有個很有名的定理 也用到一樣的證明，叫做Time Hierarchy Theorem。對類似問題有興趣的小夥伴，可以看我自己做的英文youtube影片。訂閱一下很歡迎。

這是Halting problem的影片:

這是Time Hierarchy Theorem影片:

好，如果覺得這證明頗智障，我們可以反過來想: 如果我現在可以解停機問題。那會怎樣。

以下給出幾個examples

(1) 我寫下一個program，program 去找 第一個大於2的偶數不能寫成兩個質數的和，找到，就halts.
4=2+2, 6=3+3., 8=3+5, 10=3+7.............
這叫做Goldbach's conjecture

這問題是open problems in mathematics。如果你可以解決，那你一定得費爾茲獎，如果我知道他會halts. 那就表示是錯了，如果loops forever, 那就是對的。這告訴你Halting problem 很難。

(2)寫一個program 尋找 x^n+y^n=z^n (n>2) 的正整數解，找到就停止。

這個問題是費馬大定理。一樣很難，1994 andrew wiles prove it. 花了數學家四百年。

Fermat's Last Theorem 

找黎曼猜想的反例? 世界上有多少六維的calabi yau? 世界上是否有無限多個雙生質數(twin prime conjecture)

.....都可以視為是 Halting problems的 子問題。以上這些問題都是超難超難的數學問題。

希望這樣可以讓大家感受到

Halting problem 停機問題有多難。




一些變形:
有些問題是 halting problem的變形:
比方 是否存在一個演算法 判斷 一個code 跟一個input 是否可以print "hello world'?
這個問題看起來也很智障，但可以證明 他跟 halting problem 等價?

證明很簡單:
那定義Ｇ程式(x): 如果這個程式 加上 input(x) 可以print hello world 則 halts
otherwise halts.

所以 如果 halting problem 可以被解 則  G可以被解 可以判斷一程式 加上一個input 是否會print hello world.
這證明了  halting problem  > hello world

反過來說
對於任意程式和 input x
我定義 G={如果halts 則輸出hello world 反之 則不輸出}

這樣解hello world 就可以解halting problem

這證明了  halting problem  < hello world.

還有很多問題 都一樣困難 推薦一個 3n+1 問題 大家可以看看唷。
3n+1 problems -- Collatz conjecture python code



Go back to Main page Notes for Complexity theory

江湖的雨聲 作陣聽 一身濕漉漉

November 6, 2017 at 7:58 AM

  ig fb 會看到一些人，穿美美的，面容姣好，常po美食，偶爾出國，羨煞死人，以前覺得不公平，為何偶們苦，人家爽，最近漸漸想開了，想起有人說: 一個台灣，兩個世界。
猶記隋朝智者大師，說過，一念三千，十法界內又有十法界，
台灣有福報大的，也有我們苦人團，雖此台灣也有天上人間的縮影，不妨想，我們不錯，還跟她們在這人間雜居。

到頭本非同類，這樣想心裡舒坦許多，實在本來就鼻一樣。

江湖的雨聲 作陣聽 一身濕漉漉

研究所申請另一感觸就是 : 以前我們自己為是開放激進派
最近 才發現自己是 保守派大學生 幾年來變了

和一些高中大學人聊 很多人都想出國讀 特別是有人想去北京清華讀書 也有台大朋友大學後要出國去讀碩 或是 以後想要博班再出去奮鬥....大家好有勇氣 怎麼這麼奮鬥 自然 在大學書讀多 看的人多 知道台灣太小怎樣之類 要搞學術還是要去國外學 或去對岸 因對岸學歷比台灣有更大利益


這我也懂 也知道 可是我不敢 沒把握也怕 怕什麼? 怕真的要和世界競爭 這實在是有壓力 電視上 最愛講 台灣大學生不能再這樣啊 不讀書 大學睡覺怎樣 競爭力差 沒國際觀 眼界小 以後要跟對岸各國競爭怎樣 又說陸生很多認真奮鬥

可我們為啥一定要競爭 一定要跟世界競爭 全球化搞死大家 大國那裏經濟差 連帶全球 大家逼不得已 莫怪以前 民至老死 不相往來 哪來啥經濟金融風暴 可世局又能怎樣 清朝鎖國 就給人打爛 日本鎖國 黑船事件 美國開船進去鳴炮 日本開放 西方侵門踏戶
可台灣是缺凡天然資源的地方 我也愛島國 你說沒國際觀很清淨的小島國 全球治安前幾 妹多 又有美食 文化不錯 ˙開放? 我怕阿 因為我知道各國這些人有本事 我怕競爭 我朋友不怕 他們要闖
可是時代浪潮 鎖? 怎麼鎖阿 我也想鎖國阿 我也希望找一片淨土阿不管事啊 可是能怎辦呢 你生在這個時代 要跟他同路無可奈何 你有實力可以偏安一隅嗎 以前常說民進黨太保守 要開放阿 要競爭阿 要跟各國交流阿 可這幾年台灣經濟也爛 也差 大學生又沒料 給人嗆 我是天真的 被人嗆是俗辣 說偶不敢出去闖 也是 守不住我也知道 果然 我是保守派的