是否所有的有限數列都可以由相應的一個公式生成？

12-04

這裡問這個問題，是因為有這樣一個想法：是否計算機上的任意文件，都可以由一個相對應的公式來生成？如果答案是肯定的，那麼這將給文件壓縮帶來質的變化。試想，隨便多大的文件，只要能夠推導出一個數據生成的公式，那麼只要把公式分享給別人，就完成了所有數據的傳遞。
從大家的答案可以看到，上面的猜測是正確的，那麼下一個問題就是是否能夠從有限數列推倒出公式來。

覺得諸位貌似沒有回答道點子上啊。。。

問題的關鍵是，這個公式的複雜度是否低於這個數列的複雜度？
這個問題的答案才是真正解決樓主所說的「文件壓縮」問題。

至於這個問題的本質，請參考Kolmogorov複雜度：
http://en.wikipedia.org/wiki/Kolmogorov_complexity
而Kolmogorov complexity恰恰正是編碼、壓縮的基石之一。

在實際生活中比較普遍的應用是稀疏分析。這一領域的目標是讓一個「representation」（對應理解為lz所說的公式）的l1 norm（某種意義上的複雜度）盡量低於原來數列的複雜度。

目前日常生活中的典型應用之一就是jpeg/mpeg編碼。

這個問題可以有以下幾個考慮方向：

是否存在一個函數，使得x_1到x_n的n個點的分別依次對應函數值為這個有限數列；
是否存在一個變換矩陣，使得任意有限數列都可由其所構成的n維空間V的基向量變換得到。

對於第一種考慮：
對問題進一步數學化一些，轉述為：對於任意的有限的數列s_1, s_2, ... , s_n是否存在一個函數f，使得f(x_1)=s_1, f(x_2)=s_2, ... , f(x_n)=s_n。也就是，對於數對序列{ (x_1,s_1), (x_2,s_2), ..., (x_n,s_n) }，是否對於一個定義域[a,b]，且有a≤x_1≤x_2≤...≤x_n≤b，存在函數f滿足上述序列。
於是，這就變成了一個多項式插值問題了，完全可以使用簡單的拉格朗日插值法，求得這樣的為如下形式的函數（按LaTeX的函數書寫方式）：
f(x)=sum_{j=0}^n s_j l_j(x)，其中 l_j(x)=PI_{i=0,i≠j}^n frac{x-x_i}{x_j-x_i}

對於第二種考慮：
對問題進一步數學化，轉述為：是否存在一個n維空間上的變換矩陣F，使得有限數列s_1, s_2, ... , s_n所構成的向量S滿足F?S=h，h為基向量。根據矩陣變換的相關知識，很顯然，必然存在這樣的變換F滿足這一條件。

綜上，是存在這樣的「公式」，滿足問題條件。只是這樣的公式是否唯一有待驗證罷了……

參考：

拉格朗日插值法 http://en.wikipedia.org/wiki/Lagrange_polynomial
多項式插值 http://en.wikipedia.org/wiki/Polynomial_interpolation
矩陣變換 http://en.wikipedia.org/wiki/Transformation_matrix

學點資訊理論你就不會問這種問題了，你這個想法就跟造第二類永動機本質上是一樣的，信息量不能無中生有，跟熵不能自行減小是一個意思
最基礎的原理上來說根本就不需要太多數學論證，既然你要求的是所有的有限數列，那任意一個有限數列都應該有一個對應的公式或者編號或者別的什麼，總之你需要有一種方法將它和其他的有限數列區分開。那麼，你有多少種不同的有限數列，就需要游多少種不同的公式或者編號。接下來你需要用符號把它們表示出來，然而要表示這麼多種不同的有限數列，需要的最小平均編碼長度，跟最開始有限數列的長度是一樣的。
舉個例子，你要用一種方法表示所有三位二進位數，這個很短的有限數列有8種，你用0-7分別表示，然而發送0-7也需要3位二進位數。最終來說並不能減少要發送的信息量。
再來說說壓縮的原理，壓縮原理在於人要發送的文件有其分布規律，而不是任意有限數列概率都相等，所以可以讓概率大的用較短的編碼，概率小的用較長的編碼，比如說發送三位二進位數，但是大部分情況下發送的是000和111，那麼可以用00和01分別表示000和111，用1101表示101之類其他的二進位數，這樣000和111就可以只用兩位二進位數表示了，但是其他不常用的反而長度會變長。

是的。

但是至於補充問題，你有點想多了。

你猜存儲這樣一個公式需要多少容量？

必須有的。高一的時候就和同桌玩過。他推出來的就是拉格朗日的那個，而我就推出了下面這個土不拉幾的。。。

1 - | |x - n - 0.5| - |x - n + 0.5| |

隨意補充一下：

上面只是係數，完整版本如下：

f(x)=sum_{i=1}^{n}(1-left|left|x-i-0.5
ight|-left|x-i+0.5
ight|
ight|)a_{i}

a_{i} 為 n 個給定值。x = 1時為a_{1}; x = 2時為a_{2}，依此類推

還可以從反證法這個角度想想：

假設題主所言成立，用一個公式代替數列（即計算機文件）可以「壓縮」存儲空間。
那麼這個公式本身也是一個數列，將可以用另一個公式「簡化」表達。
如此反覆，最終一部幾百G的高清電影可以被題主的這種方法壓縮到幾個位元組。

顯然，這是不可能的。

問題就在於，不能保證每一次的壓縮率都小於100%，甚至偶爾會極有可能大於100%，如此一來這個循環「壓縮」的過程就不是單調遞減的。

通項公式有時候會比數列更複雜。

有但是一般情況下無論是公式還是數列信息量是一樣的甚至更多所以對壓縮無用還要白白增加計算成本
update:
其實現代的壓縮演算法已經非常接近香農第一定律的極限了所以LZ想用一個單一公式的方法到達「給文件壓縮帶來質的變化」是不可能了

我認為可以。把這些點進行插值就可以求出數列通項公式。插值點是有限的、離散的，而插值多項式是連續的，應該沒問題。

任何有限序列都是pi的子段。。。。文件壓縮變成了兩個個數，也就是pi的起始位置和長度。。。。一個參考實現是pi文件系統，在github上有。。。但正如前幾樓有人所講，計算複雜度大幅度提升。。。甚至難以接受

因為序列可以看作是一個定義在整數子集上的離散函數，求通項公式就類似於求函數表達式，容易處理的是多項式函數。知道了前n個項，就知道了多項式函數（對應的n次方程）的n個根，那麼簡單的形式就是：(x-x1)(x-x2)...(x-xn)，這樣總是可以寫出「公式」來，進一步，可以為這個乘積添加任意其它因子，所以符合前n項的序列不會只有一種。

必須可以。這也是為什麼所有的「找規律填數字」的「智力題」（在數學上）毫無意義的原因：理論上你可以在留空處填上任意數字。

不過你明白你說的「公式」是什麼東西么？嚴謹地說，應該是：對於任意有限數列 a_1,a_2,...,a_n ，是否存在從集合{1,2,...,n}到集合{a_1,a_2,...,a_n}的映射f使得f(i)＝a_i。答案顯然是肯定的（因為問題本身已經給出了這樣一個映射的定義）。而且，顯然的，不止是有限數列，對可數數列同樣成立。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
手機打字好痛苦！。。。。

可以，解多元方程組即可。
比如有限數列是l1, l2, l3 ... ln
則令f(x) ＝ l1 * x^(n-1) + l2 * x^(n-2) + ... + l(n-1) x + ln
解方程組 f(1) = l1 , f(2) = l2 .... f(n) = ln
即可得到公式。
如果無解，則再令 f(x) = k * x^n + l1 * x^(n-1) + l2 * x^(n-2) + ... + l(n-1) x + ln
（其中k為任選的非零常數），同上方法繼續解方程組即可。