2017 is not just another prime number

Good bye year 2016. Hello year 2017.
We all know that 2017 is a prime number, but it is more than just another prime number.

• 2017π (rounds to nearest integer) is a prime
• 2017e (rounds to nearest integer ) is a prime.
• The sum of all odd primes up to 2017 is a prime number, i.e. 3+5+7+11+...+2017 is a prime number. 
• The sum of the cube of gap of primes up to 2017 is a prime number. That is (3-2)^3 + (5-3)^3 + (7-5)^3 + (11-7)^3 + ... + (2017-2011)^3 is a prime number.
• The prime number before 2017 is 2017+(2-0-1-7), which makes it a sexy prime, and the prime after 2017 is 2017+(2+0+1+7). 2017 itself is of course equal to  2017+(2*0*1*7) 
• Insert 7 into any two digits of 2017, it is still a prime number, i.e. 27017, 20717, 20177 are all primes. Plus, 20177 is also a prime number
• Since all digits of 2017 is less than 8, it can be viewed as an octal. 2017 is still a prime number as an octal.
• 2017 can be written as a sum of three cubes of primes, i,e,  p^3 +q^3 +r^3 for some primes p, q, r.
• 2017 can be written as a sum of cubes of five distinct integers.
• 2017 can be written as  x^2+y^2, x^2+2y^2, x^2+3y^2, x^2+4y^2 x^2+6y^2, x^2+7y^2, x^2+8y^2, x^2+9y^2 (for positive integers x, y)
• 20170123456789 is also a prime
• the 2017th prime number is 17539 and 201717539 is also a prime.
• Let p=2017, then both (p+1)/2 and (p+2)/3 are prime numbers.
• The first ten digits of the decimal expansion of the cubic root of 2017 contains all different digits 0~9. 2017 is the least integer has this property. 
• 2017 = 2^11 - 11th prime 

You can check OEIS for more interesting facts for your favorite numbers :)

Update: a sagemath worksheet to verify these facts by William Stein

Read More

Google Jam 2013 資格賽題目的數學證明

這篇用英文打的,就不轉成中文了。原來的題目可以在這裡找到。

$\newcommand{\lyxlock}{}$

1 Problem A. Tic-Tac-Toe-Tomek

No math involved, but complex number is builtin in python and go, so I use $0,i,1,-1$ to represent “ “, T, O, X. So if$\left\Vert \sum_{i=1}^{4}a_{i,i}\right\Vert >3$ , then some one won.

2 Problem B. Lawnmower

Theorem.$\left(a_{i,j}\right)$ is a possible pattern if $$a_{i,j}=\min\left(\max\left(\left\{ a_{i,k}\right\} \right),\max\left(\left\{ a_{k,j}\right\} \right)\right)$$ for every $i,j$ .

Proof.

Can be easily proved by induction on $N=\sum_{i,j}M-a_{i,j}$ , where $M=\max\left(\left\{ a_{i,j}\right\} \right)$ .

         

     

3 Problem C. Fair and Square

Let $$N=a_{n}10^{n}+a_{n-1}10^{n-1}+\cdots+a_{1}10+a_{0}$$ , where $a_{i}\in\left\{ 0,1,\ldots9\right\}$ and $a_{n}\neq0$ . Denote by $\delta_{k}\left(x\right)$ the $\left(n-k+1\right)$ -th digit of $x$ , then we have $\delta_{k}\left(x\right)=a_{k}$ .

Assume $N$ is a palindrome, i.e., $a_{i}=a_{n-1}$ for every $i$ .

Let $b_{k}$ be the coefficient of $x^{k}$ of $$\left(a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}+a_{0}\right)^{2},$$ that is, $$b_{k}=\sum_{i=\max\left(0,k-n\right)}^{\min\left(k,n\right)}a_{i}a_{k-i}.$$

Theorem. $N^{2}$ is also a palindrome iff $b_{k}\leq9$ for all $k$ .

Proof.

($\Leftarrow$ )

Trivial.

($\Rightarrow$ )

Observe that $b_{k}=b_{2n-k}$ for all $k$ . We prove the statement by mathematical induction on $k$ for $k\leq n$ .

Case $k=0$ :

Since $$a_{n}^{2}10^{2n}\leq N^{2}<\left(a_{n}+1\right)^{2}10^{2n}$$ and $$\delta_{0}\left(N^{2}\right)=\delta_{0}\left(a_{0}^{2}\right)=\delta_{0}\left(a_{n}^{2}\right),$$ it is easy to see that $a_{0}=a_{n}\in\left\{ 1,2,3\right\}$ . So $b_{0}=a_{0}^{2}\leq9$ .

Moreover, we also know that $N^{2}$ has $2n+1$ digits and hence $\delta_{2n-k}\left(N^{2}\right)=\delta_{k}\left(N^{2}\right)$ for all $k\leq2n$ .

Case $k>0$ :

Suppose $b_{i}\leq9$ for all $i<k$ , we want to show $b_{k}\leq9$ .

By the induction hypothesis, we know that $\delta_{2n-i}\left(N^{2}\right)=\delta_{i}\left(N^{2}\right)=b_{i}=b_{2n-i}$ for all $i<k$ . So

$$\begin{eqnarray*} 10^{2n-k-1}\cdot\left\lfloor \frac{N^{2}}{10^{2n-k-1}}\right\rfloor & = & \sum_{i=2n-k-1}^{2n}\delta_{i}\left(N^{2}\right)10^{i}\\ & = & \sum_{i=2n-k-1}^{2n}b_{i}10^{i} \end{eqnarray*}$$

On the other hand, $$\begin{eqnarray*} \left\lfloor \frac{N^{2}}{10^{2n-k-1}}\right\rfloor & = & \left\lfloor \frac{\sum_{i=0}^{2n}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor \\ & = & \frac{\sum_{i=2n-k-1}^{2n}b_{i}10^{i}}{10^{2n-k-1}}+\left\lfloor \frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor . \end{eqnarray*}$$ Therefore, $\left\lfloor \frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor =0$ , hence $$b_{k}=b_{2n-k}\leq\frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k}}<10.$$

  

  

Corollary. $N^{2}$ is also a palindrome iff $\sum_{i=0}^{n}a_{i}^{2}\leq9$ .

Proof.

$b_{n}=\sum_{i=0}^{n}a_{i}a_{n-i}=\sum_{i=0}^{n}a_{i}^{2}$ .

($\Leftarrow$ )

$b_{n}\geq b_{k}$ for every $k$ by Cauchy-Schwarz inequility.

($\Rightarrow$ )

Trivial.

In particular, if $N\neq3$ , then $a_{i}\in\left\{ 0,1,2\right\}$ .

4 Problem D. Treasure

Let $T\subseteq\mathbb{N}$ be the set of all key types. Assume $0\notin T$ .

Construct a directed graph $G=\left(V,E\right)$ as following:

• $V=T\cup\left\{ 0\right\}$
• $\left(0,j\right)\in E$ iff we starts with at least one key of type $j$ .
• If $i\neq0$ , then $\left(i,j\right)\in E$ iff there is a key of type $j$ in a box of type $i$ .$b_{n}\geq b_{k}$ for every palidrone $N$ by Cauchy-Schwarz inequility.

Denote by $B\left(i\right)$ the number of boxes of type $i$ and $K\left(i\right)$ the total number of keys of type $i$ (including the keys you start with and keys in boxes).

Theorem. All box can be opened iff for every $j\in T$ , $B\left(j\right)\leq K\left(j\right)$ and there is a directed path from $0$ to $j$ in graph $G$ .

Proof.

($\Rightarrow$ )

If $B\left(j\right)>K\left(j\right)$ , then we don’t have enough keys of type $j$ to open all boxes of type $j$ .

If there is no path from $0$ to $j$ , then it means we are unable to get any key of type $j$ .

($\Leftarrow$ )

We prove this by induction on the number of boxes. Denote by $N$ the number of boxes.

Assume for every $j\in T$ , $B\left(j\right)\leq K\left(j\right)$ and there is a directed path from $0$ to $j$ in graph $G$ .

Case $N=1$ :

Then all vertices in $G$ are leaves except $0$ and the type of the only box. So there must be an edge from 0 to the type of the box.

Case $N>1$ :

Suppose the theorem holds for the case with $N-1$ boxes.

There are at least one $\left(0,i\right)\in E$ . Consider we open a box of type $i$ (that contains a key of type $i$ if possible). Assume we destroy the key and the box just opened, then we have a setting of $N-1$ boxes. In this setting, we still have $B\left(j\right)\leq K\left(j\right)$ for all $j$ . Let $G'=\left(V',E'\right)$ be the directed graph of this $\left(N-1\right)$ -box setting.

If $B\left(i\right)=1$ , then all children of $j$ in $G$ become children of $0$ , $0$ can still reach all other types in $G'$ .

Assume $B\left(i\right)>1$ .

If $\left(i,i\right)\in E$ , then we can open a box of type $i$ that contains a key of type $i$ .

Otherwise, because $K\left(i\right)\geq B\left(i\right)>1$ , we still hold at least one key of type $i$ after we open a box of type $i$ (and destroy the key).

Either way, $\left(0,i\right)\in E'$ . Therefore, for every child $j$ of $i$ in $G$ , either

1. $\left(0,j\right)\in E'$ (if a key of type $j$ is in the box we just opened), or

2. $\left(i,j\right)\in E'$ and so there is a path from $0$ to $i$ and then to $j$ .

So $0$ can still reach very vertex in $G'$ .

By induction hypothesis, the remaining $N-1$ can also be opened.

  

  

By the proof of the theorem, there is a simple algorithm to open all boxes: open any box unless you have just one key of that type and box does not contain a key that can open itself.

However, this algorithm may not yield a "lexicographically smallest" way to open the boxes.

The solve the problem, you should open the box with smallest number such that either this box is the last one of type $i$ or there is still a way to get a type $i$ key.

---

Document generated by eLyXer 1.2.5 (2013-03-10) on 2013-04-16T11:23:46.409386

Read More

悖論的演講投影片

這是今天在 IMO 第二階段選訓營的投影片內容，簡報內容改自以前通識課的演講。但聽眾不同，所以內容還是差異不少。一些東西有講，沒有在簡報裡。許多圖取自 wikipedia 的 CC 圖片，投影片裡沒有註明，但是演講時都會口頭提到。

Read More

GeoGebra 開箱

在臉書上看到蔡炎龍老師利用 GeoGebra 做出的這個圖片。題目看起來還挺有趣的，所以就想了一下。第一個想法是用複數，在白板上面稍微算了一下果然可行。但直覺這種東西應該有幾何上的意義，所以盯著這個圖片看了一陣子，總算看出了圖形化的證明。
但一來憑空想像的圖形有時會出錯，二來要怎麼把這個解法貼出？
於是，我想不妨試看看這個蔡老師推廣的 GeoGebra 好了。
第一步當然是先用 google 找到 GeoGebra 網站，發現是 Java 軟體，點一下然後等一下就能打開。稍微摸索一下，就上手畫出跟上面一樣的圖形。這也多虧有上面的圖當範本，讓我知道 GeoGebra 能畫出這樣的圖形，才能往正確的方向嘗試，幾乎可以說是打開就會用了。
接著就要做圖形化的證明。傳統的方式，我們會用輔助線的方式來做圖形證明。像是過某點作與某線段平行的直線之類的，然後再說新作出來多邊形和原來的哪個全等。
GeoGebra 也能做同樣的事，不過還有更好的做法。與其弄一堆平行的輔助線，我把原來的圖形繞著一個點旋轉 180 度，這樣平行以及全等就是自然而然的事情了。
準備儲存圖片時，發現可以輸出 GIF 動畫。心想這樣更好，但是找不到動畫時間軸的要怎麼弄，所以便宜行事 Google 了一下，了解 slider 的用法。

最後的結果如下:

由這個動畫，可以很清楚的了解兩個正方形中心相連的那個線段的幾何意義，當然也就清楚知道為什麼會垂直了。
也由於是 Java，什麼平台都能跑，拿來畫畫圖看起來還挺方便的。

Read More

松鼠URL 2011-4-20

Matrix67: 随记：我们需要怎样的数学教育？
陳安儀的筆下人生: 讚美與獎勵制度
Lifehack: 5 Sci-Fi Brain Hacks That Modern Science Is Making Possible
A Neighborhood of Infinity: Image-based rendering and some ancient history
關於知識的兩個有名而且有趣的悖論：

1. What's New: The blue-eyed islanders puzzle – repost  這個問題中，會用到「假定我沒有藍眼，則你會想，假設你沒有藍眼，他會想.....，但xxx知道至少有一個人藍眼,...所以....」這樣的推理，所以涉及假設性情境下「知道」的問題，某種意義上是「能知(knowable)」和「必知（在所有假設情形下都知道）」之間的微妙關係。
2. Matrix67: Fitch悖论：我们已经掌握了所有的知识 Fitch's paradox 的主軸就是「能知」和「知」之間的關係。

The Surprise Examination Paradox and the Second Incompleteness Theorem (pdf 檔)
Surprise exam paradox 又稱 hanging man paradox，也是極有名的悖論。悖論的成因有更種不同的說法，有一種看法認為跟「知識」的本質有關，因為用到數學歸納法，其中也涉及到假設情形下的「知」。這篇文章利用這個悖論來證明 Godel's incompleteness theorem，並反過來，用不完備性來解釋這個悖論的成因。
簡單的說，就是將「知」比為「證明」時，「猜不到」 就類同於「不能證明」。這樣，就牽扯到了 consistency。

Read More

Project Euler 198 題

Project Euler 的 198 題。簡單的說，要算出分母在 10^8 以內，大小在 0~0.01 之間的「混淆數」總共有幾個 。而所謂的混淆數 x，是指如果對於某個 m，分母不超過 m 的「最近似 x 的分數」不只一個時，就稱 x 為混淆數。比方對於 x=9/40 來說，m=6 時， 1/5 和 1/4 都是分母不超過 6 最近似 x 的分數。
這個題目其實如果沒有任何基礎知識的話，還不太容易，所以解出的人不多。但站在一些基礎知識之上， 10^8 這種數量級是很容易用程式來秒殺的。據說 Knuth 的 The Art of Computer Programming 裡面就有提供相關的演算法。
不過使用 Haskell，可以很直接的用遞迴解出：

f a b l m | a*b>l || (a==1 && b > m)  = 0
         | otherwise = (f a c l m)+1+(f c b l m) where c=a+b
main = putStrLn $ show result
      where result= (f 1 100 l2 m) + 49+l2-m
      l = 10^8
      l2 = l `div` 2
      m = floor (sqrt (fromIntegral l2)

七行就簡單解決了。如果你知道背後的數學，上面的程式碼其實是很直接的。但用 Python 解就麻煩了，因為上面這個遞迴解超出 Python 的遞迴深度。可以用迴圈來取代遞迴，如下面的演算法：

def p198(M=10**8, z=100, cnt=0):
 M2=M/2
 a=m=int(M2**0.5)
 stack=range(z,m)
 while stack:
     b=stack[-1]
     if a*b>M2:
         a=stack.pop()
     else:
         cnt+=1
         stack.append(a+b)
 return cnt+M2-z/2

(程式碼我從 Project Euler 直接貼過來，排版有點亂掉）
這個演算法是我參考別人的解答後寫出的，配上 psyco 後，其實還挺巧妙也挺快的，但不太容易讀懂，要跟蹤一下堆疊是怎麼跑的。
但有些簡單的工作， Haskell 寫起來又很累贅。比方有一個整數 n，想找出它的根號的整數部份，如後印出來，在 python 來說再簡單不過的

print int(x**0.5).

Haskell 的作法要先將整數轉成浮點數，開根號，然後再用 floor 轉成整數，最後再用 show 轉成字串才能印出。所以是

putStrLn.show $ (floor . sqrt) (fromIntegral n)

如果有許多浮點數與整數，那更複雜一點的運算就要轉來轉去。雖說這樣可以強迫正確的設計風格，但有時只是簡單的小計算，這樣也未免太累了。
果然 Haskell 能將複雜工作簡單化，簡單工作複雜化。

Read More

zhpy 的另類用法

配合上 zhpy ，我們可以寫出下面這樣的 python 程式:

# encoding: zhpy_utf8
from math import *
from operator import *
print Σ(range(100))
print sin(π/4) ≠ √(2)/2
print ㏒(100), ㏑(e)
print 5 × 30 ÷ 2 ≦ tan(√(5)*π/4)
Π=λ f:reduce(mul, f, 1)
print Π(range(1,6))
print set([1, 2, 3, 4, 5]) ∩ set([1, 3, 5, 7, 9])

(第一行是 MagicCodec 語法，普通的 zhpy 請去掉第一行)
不管實不實用，至少增加了一點可讀性。既然是λ，為什麼要寫成 lambda?
以上的程式碼只需要下面的 zhpy .ini 檔案（可以叫做 math.ini，放在執行的目錄下)

[math]
λ=lambda
π=pi
Σ=sum
≠=!=
÷=/
×=*
㏒=log10
㏑=log
√=sqrt
≧=>=
≦=<= ∩=& ∪=l

for 和 in 可以換成相對應的符號, set 的 <, <= 也可以換成 set 符號。
Haskell 的 ide Lesksah 就能做到這件事情。 如果能夠把 lyx 修改成 python, haskell 或者其他程式語言的編輯器，應該也挺有趣的。
相關的東西是 TeXmacs 的 python plugin tmPython，

Read More

根號 2 到兩百萬位的挑戰

Sphere Online Judge 有一個題目是在 20 秒內計算根號 2，越多位越好（上限是兩百萬位）。有不少人能達到這個目標，但都是使用 C 或者 C++。我想試試看 python 這種以速度慢聞名的語言，能達到什麼程度。試驗的結果是十五萬位。雖然不太多，但是也擠進了排行榜裡面前二十名。而目前 python 語言的第二名還不到五萬位。

我的程式沒有用什麼特殊的技巧。事實上， python 的乘法不算太慢，現在 python 已經使用了 Karatsuba 演算法來做乘法，在一萬位以內的效能都還不錯，算到十幾萬位也都還能接受。但再上去就有點吃力了。而最主要的瓶頸在於 long 到 str 的轉換速度。光是將一個兩百萬位的數字轉成字串，就會花上非常久的時間。

改用 gmpy 會快很多，應該能夠算到百萬位以上，雖然我沒試過，但 spoj 應該不能使用 gmpy。

所以，也許應該直接寫個簡單的 FFT 乘法模組。事實上，我找到了一個叫做 DecInt 的 Pure python 套件，裡面實現了幾種快速的乘法及除法演算法，而且因為基本上資料是用十進位表示，數字轉字串非常快。他的乘法也許不是最快的，但是如果要我自己寫，大概也會是類似的東西，所以相當適合先拿來測試一下效能。

果然，大致上可以讓算十五萬位的速度快兩三倍。如果自己再強化改進，也許能再快個兩倍，但估計最多只能勉強上到百萬位，而且需要相當長時間的測試和實驗，所以我放棄。

於是我改用 Haskell 來寫。我沒有寫過 Haskell 程式（現在也還不會），而且連 Tutorial 都沒有讀完，就抓了 ghc 用最笨的方式把程式寫出來了。我只需要知道怎麼用 = 來定義函數能寫了。結果算到了一百六十萬位，足足比 python 多了十倍(Haskell 現在第二名約一百二十萬位)。如果再多加微調，或者我如果對 Haskell 再多熟悉一點，也許還能多個不少位，甚至到兩百萬位也不無可能。

其實我只要算到五十萬位，然後再用個 4-way Toom Cook 就行了，而算到四十萬位不用三秒。不過問題是，就像前面說得，其實我還不會寫 Haskell。

演算法基本上和 python 版本的相同，不過改以 recursive 的寫法。 Python 雖然完全支援 recursive 函數，但是 Python 的函數呼叫很慢，又限制層數（內定1000，最多 5000)，所以，其實有點降低我把東西寫成遞迴的誘因。反之，Haskell 是 functional language，所以其實是獎勵這種寫法。

而 Haskell 之所以算得這麼快，其實有點勝之不武，因為 ghc 內建用 gmp 來做計算。

讓人疑惑的反而是，為什麼 python 不用 gmp 來做計算？

當演算法夠好，時間夠長， python 的速度劣勢就能被彌補，但 online judge 的時間限制都不太長，二十秒已經算是超級長的了，但這二十秒差不多只等於我電腦上的五、六秒，典型的時間限制是兩秒。用 pure python 實現很好的乘法演算法，也要到上萬位才能擊敗 python 內建的長整數乘法。所以，現在想用純 python（而且程式碼在4kb以內）上兩百萬位，還挺困難的，不過，也許還是有人能辦到也說不定。

(Update 2008-06-11) Haskell 達成兩百萬位。當然我 Haskell 的能力比兩天前進步一點，但主要還是用笨方法寫 recursive function。程式碼總共 11 行，而且其中有 3 行是用來定義一個函數，來達到 python 的 zfill 功能。

Read More

Euler 計畫和其他

前一陣註冊了 Project Euler，然後玩了一下裡面的題目。
Project Euler 蒐集了一系列的挑戰問題，這些問題的答案都是一個數字或者一組數字。每當你破解一個問題後，你就能與其他同樣破解這個問題的人，討論答案與心得。通常解決這問題需要一點程式設計技巧和數學知識。

網站裡面也會對於不同國家或者程式語言的解題者做統計和排名。比方說這是台灣的統計，而這是 Python 語言的統計。和「點點點」相比，台灣的表現很爛。
一般所謂的 online judge 系統其實很多，ACM 風格的 online judge 是主流。 UVa online judge 是其中的代表。其他還有如ZeroJudge。
和 Project Euler 不同， Project Euler 上傳的是答案，而這類 online judge 要你上傳的是「程式」。所以有限定使用的程式語言。標準的語言是 C,C++,Java。雖然我也寫 C++和C，但我還是比較喜歡能自由選擇工具。這點到不是根本性的問題，像是 Sphere Online Judge 就能讓你使用許多不同的程式語言，包含 perl, ruby, python。
另外一個不同點是時間限制，雖然 Project Euler 也有所謂的「一分鐘法則」，就是程式應該要能在一分鐘跑完，但這不是硬性規定，真正的裁判是你自己。事實上，如果你喜歡（而且可以的話），你甚至可以 用google 找答案。真正的裁判是你自己。我喜歡這種風格。
一般的 online judge，有些題目有時間限制。就比賽而言，這提供競賽公平性的基準。但這個時間限制沒有「理論上的定義」，端看裁判主機端執行的時間而定。這缺乏了一點美感。
另外就是題目取向，Project Euler 的題目有時會需要一點數學知識，而一般程式競賽有時則是要一點演算法上的知識。而 Project Euler 容許的執行時間往往比較長一點。
總之，雖然都是程式挑戰題，但是風格和取向各有不同。
另外一種類型是 Code Golf，著重在用最短短的程式碼達成指定的功能，就像是打高爾夫一樣，你想要用最少的桿數完成比賽。雖然也是程式解題競賽，但又另有一番風格。
當然，寫程式的目的在於寫出「真正有用」的東西，而不是解答這些問題來炫耀自己有多強。但是，不管是哪一種風格的程式解題競賽，在你解題的過程，都能增進自己的程式設計能力。比方 Code Golf 裡面，有些解答是不可思議的短，在你追求這個目標的同時，才發現原來有些語言特性是自己之前忽略的，某種問題原來還有這種寫法。
(對 Project Euler 有興趣的朋友，可能也會對 IBM 的 Ponder This 有興趣。)

Read More

lyx 1.5.2

lyx 1.5.2 版之後，對於中文的支援已經沒有問題了，Windows 下搭配的 MikTeX CJK 應該也沒有問題了。
唯一要增加的是字型， Windows 下面可以根據這個介紹的 7,8頁或者之前文章的 3,4 項來安裝字型。前面的方式比較簡單，對大部分的人應該都可行。
這時候，只要將 language 設成 Chinese(Traditional)，然後在第一行按下 Ctrl-L 加上 TeX 指令

\CJKfamily{cwmu}

就能順利使用中文了。
有些頁面標頭設定下，使用中文 title 可能會出問題。我想應該不難解決，我暫時也用不到，所以就沒有解決了。

Read More

有學問語錄

關於數學、科學、研究的語錄

As far as the properties of mathematics refer to reality, they are not certain: and as far as they are certain, they do not refer to reality.
Albert Einstein

"Obvious" is the most dangerous word in mathematics.
Eric Temple Bell

A talk in mathematics should be one of four things: beautiful, deep, surprising... or short.
Michel Mendès France, remark, c. 1986

There are only two kinds of modern mathematics books — those you cannot read beyond the first page and those you cannot read beyond the first sentence.
C. N. Yang

Factorials were someone's attempt to make math look exciting.
Steven Wright

A circle is the longest distance to the same point.
Tom Stoppard

There is very little flexibility in the behavior of the Universe. What it does once, it does again.
Isaac Asimov

What makes the Universe so hard to comprehend is that there's nothing to compare it with.
Ashleigh Brilliant

If you wish to make an apple pie from scratch, you must first invent the universe.
Carl Sagan, Cosmos (1980)

The whole of science is nothing more than a refinement of everyday thinking.
Albert Einstein, Out of My Later Years (1950)

Science is a long history of learning how not to fool ourselves.
Richard Feynman, quoted in K. C. Cole, The Universe and the Teacup: The Mathematics of Truth and Beauty (1998)

The main object of all science is the freedom and happiness of man.
Thomas Jefferson

Science is always simple and always profound. It is only the half-truths that are dangerous.
George Bernard Shaw, The Doctor's Dilemma (1913)

The experimenter who does not know what he is looking for will never understand what he finds.
Claude Bernard

I have little patience with scientists who take a board of wood, look for its thinnest part, and drill a great number of holes where drilling is easy.
Albert Einstein

Every hour a scientist spends trying to raise funds is an hour lost from important thought and research.
Isaac Asimov

"Research" means "to search again." Why not? Sometimes, a new interpretation emerges that is of vast importance.
Isaac Asimov

Basic research is what I am doing when I don't know what I am doing.
Wernher von Braun

In research the front line is almost always in a fog.
Francis Crick, What Mad Pursuit: A Personal View of Scientific Discovery (1988)

Results! Why, man, I have gotten a lot of results. I know several thousand things that won't work.
Thomas Edison

If we knew what it was we were doing, it would not be called research, would it?
Albert Einstein

The final results [of his work on the theory of relativity] appear almost simple; any intelligent undergraduate can understand them without much trouble. But the years of searching in the dark for a truth that one feels, but cannot express; the intense effort and the alternations of confidence and misgiving, until one breaks through to clarity and understanding, are only known to him who has himself experienced them.
Albert Einstein

The mere formulation of a problem is far more often essential than its solution, which may be merely a matter of mathematical or experimental skill. To raise new questions, new possibilities, to regard old problems from a new angle requires creative imagination and marks real advances in science.
Albert Einstein

If we want an answer from nature, we must put our questions in acts, not words, and the acts may take us to curious places. Some questions were answered in the laboratory, others in mines, others in a hospital where a surgeon pushed tubes in my arteries to get blood samples, others on top of Pike's Peak in the Rocky Mountains, or in a diving dress on the bottom of the sea. That is one of the things I like about scientific research. You never know where it will take you next.
J. B. S. [John Burdon Sanderson] Haldane

Why think? Why not try the experiment?
John Hunter, letter to Edward Jenner

Copy from one, it's plagiarism; copy from two, it's research.
Wilson Mizner

For God's sake, stop researching for a while and begin to think.
Sir Walter Hamilton Moberly, The Crisis in the University (1949)

I didn't think; I experimented.
Wilhelm Roentgen

We haven't the money, so we've got to think.
Ernest Rutherford, in R. V. Jones, Bulletin of the Institute of Physics 1962, 13, 102

The joy of research must be found in doing, since every other harvest is uncertain.
Theobald Smith

Research means going out into the unknown with the hope of finding something new to bring home. If you know in advance what you are going to do, or even to find there, then it is not research at all: then it is only a kind of honourable occupation.
Albert Szent-Györgi, Perspectives in Biology and Medicine (1971)

If a research project is not worth doing at all, it is not worth doing properly.
Unknown, Journal of Irreproducible Results 1961, 9, 43

The difference between science and magic is that magicians usually know what they're doing.
Ashleigh Brilliant

There are two kinds of truth; the truth that lights the way and the truth that warms the heart. The first of these is science, and the second is art. . . . Without art science would be as useless as a pair of high forceps in the hands of a plumber. Without science art would become a crude mess of folklore and emotional quackery.
Raymond Chandler, The Notebooks of Raymond Chandler (1976)

Everything should be as simple as possible — but not simpler.
Albert Einstein

Most of the fundamental ideas of science are essentially simple, and may, as a rule, be expressed in a language comprehensible to everyone.
Albert Einstein

The only source of knowledge is experience.
Albert Einstein

There is no logical way to the discovery of these elemental laws. There is only the way of intuition, which is helped by a feeling for the order lying behind the appearance.
Albert Einstein

You do not really understand something unless you can explain it to your grandmother.
Albert Einstein

The most incomprehensible thing about the world is that it is incomprehensible.
Albert Einstein, quoted in his obituary (April 19, 1955)

I think and think for months, for years; 99 times the conclusion is false, but the hundredth time I am right.
Albert Einstein, quoted in Banesh Hoffman, Albert Einstein, Creator and Rebel (1972)

Nothing is too wonderful to be true if it be consistent with the laws of nature.
Michael Faraday

This is common to all our laws; they all turn out to be simple things, although complex in their actual actions.
Richard Feynman, The Character of Physical Law (1965)

Being a language, mathematics may be used not only to inform but also, among other things, to seduce.
Benoit Mandelbrot

The aim of science is not to open the door to infinite wisdom, but to set a limit to infinite error.
Bertolt Brecht

Science is everything we understand well enough to explain to a computer. Art is everything else.
David Knuth

There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable. There is another theory which states that this has already happened.
Douglas Adams

A common mistake that people make when trying to design something completely foolproof is to underestimate the ingenuity of complete fools.
Douglas Adams. Mostly Harmless

All of physics is either impossible or trivial. It is impossible until you understand it, and then it becomes trivial.
Ernest Rutherford

If we are to achieve results never before accomplished, we must employ methods never before attempted.
Francis Bacon

You cannot teach a man anything; you can only help him find it within himself.
Galileo Galilei

he most exciting phrase to hear in science, the one that heralds the most discoveries, is not "Eureka!" but "That′s funny..."
Isaac Asimov

If I have seen further than others, it is by standing upon the shoulders of giants.
Isaac Newton

If the brain were simple enough for us to understand it, we would be too simple to understand it.
Ken Hill

Read More

lyx 文法檢查

很久沒有更新了，來一個沒什麼用的東西: 將 lyx 加入文法檢查。
環境是 ubuntu，不過 windows 下面也類似。

Step 1: 安裝 lyx 1.5.1（google ubuntu lyx), perl (用 apt-get 就行了）
＊＊注意要將 /usr/bin/lyx link 到 /usr/bin/lyx-1.5.1 上
Step 2: google 搜尋 lyx-gc languagetool，然後下載 lyx-gc 0.3h 版本
Step 3: 解開 lyx-gc 的壓縮檔。
Step 4: 修改 lyx-gc，將第一行 #!/bin/sh 改成 #!/bin/bash，也可以把 locale 改掉
Step 5: 修改 chktex.pl
將 $ErrorText .='> '.embed_error_tags($rule_context,' '.$rule_ptrs,'?,'?').".\n\n "; 裡面的兩個奇怪的字元改掉，改成不奇怪的字元。我是用 _
Step 6: 執行 lyx-gc 即可，然後用 lyx 選單裡面的 check tex 檢查簡單的文法錯誤(666錯誤)。
Step 7: 可以 sudo apt-get install chktex 來增強功能（非 666錯誤）。
要更進階的功能，則需要 LanguageTool。
Step 1: 安裝 sun java 1.4 以上的版本
Step 2: google 搜尋，下載 LanguageTool 0.9.1 版
Step 3: 解該 LanguageTool 到某個目錄，假定是 /home/user/lt
Step 4: 修改 chktex.pl.jLanguageTool.pl 的 my $LANGUAGETOOL_PATH，指向 /home/user/lt。
Step 5: 這樣就能用了。可以開個新檔，打入 is were，然後執行 lyx 的 check tex 兩次（算是 bug），如果檢查出文法錯誤，那就成功了。

可惜 LanguageTool 本身不太穩，某些怪一點的文字，會讓他爆掉。所以長一點的文章可能只好分段檢查。
Windows 方面，可以安裝 windows 版本的 perl，但是 lyx-gc 的作者顯然 perl 功力不怎麼樣，很多檔案操作都是呼叫 shell 來完成的。需要手動修改 perl 程式，把一些檔案操作改成 perl 的內建功能。另外也可能要把一些 bash 檔的功能手動調整。基本上， windows 版本下面也是可以跑的。雖然說和 chktex 及 LanguageTool 搭配還要額外的修改。

Read More

手寫數學式輸入

目前來說，對數學家來說還沒有到非常實用的階段。但是還是先整理一下(主要參考這裡修改的)

• Freehand Formula Entry System 算是一個可用的玩具各平台都可以用。有 source 。
  
• Natural Log by Matsakis, Miller, and Viola (MIT) 有 online demo 可玩，使用 java。
  
• JIMHR:, 整合 FFES/DRACULAE and the Natural Log system， by Joy-Gong Ho (Acuitus Corp., USA)和 CIT。 opensource。
• JMathNotes by Ernesto Tapia Rodriguez (Free University of Berlin) 跨平台，容易安裝，看起來介面完成度還挺高的。
  
• Infty by M. Suzuki et. al. (Kyushu University, Japan) 免費， windows 下可用，有編輯器以及文檔自動翻譯，目前免費，但是無 source，可以玩一玩，但是有時不是那麼穩。
  
• MathJournal by XThink Inc. 商業軟體， 另外有簡化版本 Math Calculator可以試用。似乎還挺不錯的。
  
• MathPad by Joseph LaViola 也是個原型，但是看不到哪裡可以下載。
  
• Maple 10 有手寫符號輸入，可惜不怎麼好用。

一般來說，主要的問題應該是手動調種 grouping 的功能要不就是沒有，要不就是不那麼直覺，需要學習（人類學習，不是機器學習）。

Read More

LyX 1.5.0 beta1 + MiKTeX + CJKutf8

LyX 1.5 將會支援 utf8 code 的編輯，這也意味著可以直接在上面編輯中文文件了。其實我目沒有需要用到這個功能，但是有可能會用到，所以測試並且解決了一些問題。

1. 首先先說明 MiKTeX 的安裝，我使用 LyX 內含的 MiKTeX 2.5 版，安裝後使用 MiKTeX 設定程式，增加語言裡面的 CJK 套件。
2. 但是 CJK 套件的版本不夠新，沒有 utf8 的支援，所以請下載 CJK Latex 4.7 以後的版本。下載後解開檔案，然後把 texinput 目錄下的檔案放到適當的位置。我是直接覆蓋到c:\Program Files 下 MiKTeX 程式目錄下面舊版 cjk 相關的位置。
3. 然後再安裝中文字型。我是抓 CWT1 的 cwfs 字型。在 windows 下面當然無法直接安裝，但是可以閱讀 install.sh 檔，然後手動 copy 檔案。我是用 cygwin 來執行這個檔案。先 ln -s MiKTeX 的目錄到 /tex，把 HOME 設成 /tex。但是這樣還是不能執行，因為 MiKTeX 是 windows 的程式，傳回值跟 install.sh 預期的不同。所以直接修改 install.sh，把終止 install 的部份直接 remark 掉就行了。這樣，就能成功的 copy 檔案到適當位置。
4. 最後，你還要修改一下 updmap.cfg 這個檔案，這有很多方法可以弄，我是直接修改 MiKTeX 的檔案，反正電腦只有我在用。在裡面加上

   Map cwfsu.map

   這一行。當然不同的字型就會有不同的 map。然後執行一下 updmap， refresh 一下你的系統。
5. 原則上這時應該就能使用 CJK，可以先測試一下。
   
6. 接下來是 LyX 的部份。到官網下載 1.5 之後的版本。原則上，只要把 document -> setting -> language -> encoding 改成 utf8 就可以了。這時理論上來說，存檔時就會把 utf8 的編碼存進去。
7. 所以在 Preamable 放入

   \usepackage{CJKutf8}

   內文使用用 Ctrl-L 插入 TeX 指令
   

   \begin{CJK}{UTF8}{cwfsb}

   以及

   \end{CJK}

   然後在這兩個中間就能使用中文了。
   
8. 可惜我的 LyX 1.5 beta 1 雖然能夠正確 export latex 檔，但是只要 preview 或者 export dvi/pdf 等等檔案都會 crash，這個應該是因為某些 dll 不相容的問題。所以我做了一個 workaround。先設定快速鍵到 buffer-preview latex 上，這個在 tools->preferences -> look and feel -> user interface 裡面的 binding 檔案中。我是直接把 buffer-preview dvi 的 dvi 改成 latex。
9. 然後，寫一個程式來翻譯 latex 成為 dvi 並且檢視。並且把 tools->preferences -> file format 中 latex (plain) 的 viewer 設定成這個程式就行了。我是用 python 寫的，程式碼如下:

   import os, win32api, sys
   basepath=sys.argv[1][:sys.argv[1].rfind("/")]
   output=sys.argv[1][:-4]+".dvi"
   os.system('latex -output-directory="'+basepath+'" "'+sys.argv[1]+'"')
   win32api.ShellExecute(0,"open",output,"","",1)
   
   

   這樣看起來可能有一點複雜，不過不用花太多時間去深入 hack。我相信如果把 LyX 重新 compile 一次應該就可以了。
   

Read More

大哥，你題目出錯了吧？

下面列出一些跟數學有關的有趣的益智問題 puzzle，你看完題目之後第一個想法是:「大哥，你題目出錯了吧？」
這些題目出自
SevenPuzzles You Think You Must Not Have Heard Correctly
(我從 Computational Complexity: Puzzles That Keep You Awake at Night 看來的)
解決這些問題，不需要太深奧的數學知識。
而上面的 blog 另外提出一個有趣的 puzzle，就稍微要一點數學知識了，我把他翻譯如下

可數無窮多個人排成一列，每個人都戴著一頂帽子，這頂帽子要不就是黑的，要不就是白的。每個人都可以清楚看到其他人頭上的帽子顏色，但是看不到自己的。我們要求他們所有人同時大聲猜出自己頭上帽子的顏色。帽子的顏色是隨機決定的。有沒有一個策略能夠能只讓有有限個人猜錯呢？

至於原來裡面的七個題目，我也翻譯出一些題目（略為修改）:
1. 盒中的名字

將一百個囚犯的名字放在一百個木箱之中，並且把這些木箱排成一列放在一個房間中的桌子上。囚犯們一次一個的進入房間中，每個人進去房間之後，可以打開其中五十個箱子看其中的名字，然後關上所有盒子，離開房間。囚犯之間不可以有任何的通訊。最後除非所有囚犯都能在他打開的五十個箱子中發現自己的名字，否則他們全部會被處以死刑。請問囚犯們能不能事先商量出一個策略，使得他們能夠逃過死刑的機會大於 30% ?

2. 盒中盒

許多快遞計算運費的，是以盒子的長+寬+高的數字來計算，越大就越貴。證明你沒辦法作弊把一個較貴的盒子放在一個較便宜的盒子中。

3. 點點城自殺事件

點點城的居民每個人的額頭上都有一個紅點或者是藍點（但只有一個點），只要他知道自己頭上的點的顏色，他就只能自殺。每天點點城的居名聚會一次。有一天，一個陌生人進城來了，告訴居民們「某個」他們頭上點顏色數目的資訊，「任何」一個不是廢話的資訊都可以。證明一段時間之後，所有居民們都會會因為這個資訊而自殺。

4. 不要的展開(我覺得比較沒意思）

代數學過一些x,y,z 加減乘除的運算，所以都學過怎麼用分配律把式子展開。但是你怎麼知道式子不會一直展開下去呢？

5 偷偷邦(Kleptopia)之愛

詹和瑪利亞透過網路線路愛河了，詹先望能寄給瑪利亞戒指。但不幸的，他們住在偷偷邦，所以除非放入一個被掛鎖鎖上的盒子中外，任何郵寄物都會被偷走。他們兩個人都有足夠多的掛鎖，但是沒有對方掛鎖的鑰匙。詹要如何寄戒指給瑪利亞?

6 贏得溫布敦（比較沒意思）

在暫時性的魔法作用下，你打入了溫布敦的決賽，正對上了費德勒。但可惜的是，你的魔法無法在整個比賽中持續作用。所以呢，你希望在比數是多少的時候魔法消失，這樣你才有最大的獲勝機率？

7 隨機的土著
這個比較沒什麼，也是誠實說謊隨便答的一種，而且比常見的那個還簡單。

下面這本書也可參考
Mathematical Puzzles: A Connoisseur's Collection.

Read More