夢: 愛國的數

韓國程式人員/黑客想了一個辨法去推廣數字的韓國文字，就好像是令電腦懂得分辨用家是不是愛國的韓國人，他們以為愛國的韓國人最少必須懂寫韓國字，於是就令韓國的電腦程式運作中途要是休息的話，或者是整件事是韓國政府下令的也說不定: 電腦會偶然出現一些數字的韓國文字，如7XX，用家必須明白這數字並輸入韓文，它才會繼續運作，要不然用家就會鎖了在電腦之外，除非這程式是超快完成的，中途不會間斷。

한국어 프로그래머 / 해커 한국어 단어의 숫자의 방법을 홍보하려는, 그것은 컴퓨터 사용자가 애국적인 한국인을 구별 할 수없는 것, 그들은 애국적인 한국인들은 적어도 한국어 문자를 써야할지에 있다고 생각, 그래서 그들은 한국을 경우 중간 휴식 시간의 프로그램을 컴퓨터 작업 후 아니면 모든 문제는 아마도 한국 정부는 또한 명령입니다 : 7XX과 같은 컴퓨터 것입니다 때때로 어떤 인물 한국 텍스트, 사용자는이 번호가 한국을 입력할 이해해야, 그것으로 계속 작동합니다, 그렇지 않으면 사용자는 것입니다 이 프로그램은 빠르고, 중단되지 않습니다 절반 방식으로 이루어집니다 제외하고 컴퓨터를 잠금.

A method to count the prime number

When I was writing about this method to count the prime number, I realize it could overestimate them by assuming that all factors are prime, or underestimate them by ignoring them. Therefore we can safely conclude that the number of prime number is within the range define by upper limit and lower limit.

一個質數分佈的統計方法(2)

我上次提出了兩個在一定數值範圍內估計質數數量的方法,但是一個方法像香港的司法精神寧縱無枉,於是會把質數因子也忽略,因此低估了質數的總數;另一個方法像中共國對付互聯網異見一樣寧枉無縱,於是自然不會把質數因子忽略,因此會高估了質數的總數。取其中庸之道,我們可以拿前一種方法為質數數量的下限,後一種方法為質數數量的上限,結果便可估算在一定數值範圍內質數的總數。

一個質數分佈的統計方法

又是時代已久遠到無從躇考的主意,當時剛剛升上中一,興致勃勃要拿一個諾貝爾數學獎,其中一個開心大發現是質數的分佈,是當時在研究如何寫一個找一個數的因子,由此去統計世上所有的質數,但是如此文,遇到了死迴圈便放棄了,心想人腦比電腦聰明的地方在於人腦可以自行發現解決不了的問題(Infinite recursion)而放棄的,而電腦就不懂,一定要寫程式的人去代它發現,電腦並不聰明,而是寫程式的人聰明!

今天似乎是解決了,但想必早有其他數學家發現了!

我的思路是:
１.　因為一個數的因子最大只可能是它的平方根,即任何數在某意義上都涵蓋了它的平方,由它的性質去決定在它平方範圍內的數是不是質數;
２.　另外,再考慮到所有非質數的分佈,例如2的倍數出現在任何數字的機會是2份1.3的倍數出現在任何數字的機會是3份1,N的倍數出現在任何數字的機會是N份1,只要除去該範圍內的所有部數,剩下的一定非質數不可。
1是決定了質數範圍,2是用反向思維來提供找質數的方法,關門可以打狗!

所以結論是:
質數在N^2內的機會率為:
1-[(2的倒數+3的倒數+4的倒數+...N的倒數)-(2...N的倒數的所有組合,如此是減去多數一次的因子,例如4是2的部數)]

出問題了!
因為2也是2的倍數,3也是3的倍數,如此類推,即如果因子本身是質數,在我算法內也會被當成非質數,因為我的算法本身不是用來決定一個數是不是質數,我的算法只可以排除一定不是質數的數字,所以此算法只可以作為近似值,用來比較N平方到(N+1)平方的質數分佈,不可以推出一個絕對值。

(後記,現在剛想到的是可不可冒險犯難,把所有因子自動當成質數而加入算式內呢?因此變成:
1-[(2的倒數-N平方的倒數+3的倒數-N平方的倒數+4的倒數-N平方的倒數+...N的倒數)-(2...N的倒數
的所有組合,如此是減去多數一次的因子,例如4是2的部數)]
或:
1-[(2的倒數+3的倒數+4的倒數+...N的倒數)-(2...N的倒數的所有組合,如此是減去多數一次的因子,例如4是2的部數)-N的倒數]
未解決,未解決,未解決!)

找一個數的所有因子的方法

這是我中一時遇到而解決不了的問題,解決不了不是因為我不懂寫電腦程式,也不是因為這問題本身很困難,而是自己的思想陷入了一個無窮遞歸的循環中跑不出來,因此令我對電腦最初設計者Newman提出的「停止問題(Halting problem)」印象深刻,人腦真的不同電腦。
我當時用的是Dbase作業系統,所以當學到有速算法可立刻分出哪一個數是某數的倍數時,立刻蠢蠢欲動,想寫一個可以分解一個數的所有因子的程式,我的思路是既然一個數最高的因子是它的平方根,因此只要由2開始逐個用速算法測試,直到它最接近它的平方根的整數為止,但是如此一來,數值大小便和要測試的時間成指數比例,8個位的數字是4個位的100部,如何縮短它的所需時間呢?
其中一個思路就是利用遞歸的慨念,在測試某一數字是否它的因子之前,先去測此因子是不是之前已測試的因子之部數,例如要測試101是否為4的部數,只要再測試一下4是不是之前曾測試過的因子2的部數,另外再用邏緝去推斷,既然101不可以被2整除,則它當然不可能被2的部數4來整除;倒過來說,如果它可以被2去整除,則一定要先測試才知道它可不可以被4去整除。

所以最初想的程式的大致結構如下:
輸入1N位的數字,用它的平方根來產生1陣列,以陣列的1來表達可被整除
由2開始到它的平方根(否則會進死迴圈不能停止),
{當陣列對應的值不是1時,
用存在資料庫的樣式來比較輸入之數字是不是可被整除,
如果可以的話把陣列對應的值改成1}

,好像是忘記了什麼?忘記了節省時間的因子再被之前的因子去測試的「偉大發現」!
再補充一下,但如何加上去呢?因為測試數字的次數是定值,而測試因子的次數卻跟因子值而變,我當時不懂如何用Dbase寫出來,因此問題被擱置了!

現在當然是想通了,
輸入1N位的數字,用它的平方根來產生1陣列,以陣列的1來表達可被整除
K由2開始到它的平方根(否則會進死迴圈不能停止),
{
N由2開始直到K的正整數平方根
(當陣列K的值不是1時,
用存在資料庫的樣式來比較輸入之數字是不是可被N整除,
如果可以的話,則:
假如陣列K的值是0,即之前已測試的因子不可以整除輸入的數字,改陣列N的值為0;
並把K加1)
當陣列K的值不是1時,
用存在資料庫的樣式來比較輸入之數字是不是可被整除,
如果可以的話把陣列對應的值改成1;}

不過我當時想的還有更深的一步,有沒有辦法去令電腦自己懂得尋找速算法而不見程式人員輸入呢?我當然懂2,3,4,5,6,9的速算法,但要是其他未知的呢?可不可以寫一個程式去讓電腦先去自己生產一個速算法,然後再利用自己生產的速算法來檢測因子呢?可不可以再推前幾步呢?

(以當時的技術是決沒有可能,但現在可以利用程式天演算法(evolutionary computing)來自己生產程式,所以是絕對可能,但是它可能到再前哪一步呢?相信再進步的電腦也不懂自己找問題來研究吧!)

A program to find all the factors of a number(II)

Last time when I was writing to complete my childhood wish to write a (BASIC) program to find all the factors of a number using heuristic learn from Primary School. However, when I was doing so I has forgotten the true difficult of the program: To shorten the test time, the program would limit to test only the prime factors of the number without knowing which factor are prime. In order to do so, the program will have to test the factor recursively, but I fail to find a way to such write a recursive loop.

Now, I just thought of another method to shorten the search of all factors of a number.

Given a number N,

Define the lower limit of √N as K,

Make an array of K item,

Starting from K,

Check if the K-th element of the Array is zero, otherwise reduce K by 1.

Test if N is divisible by K,

If not reduce K by 1, otherwise:

1.Mark the K as divisible by making the value of K-th item of the array to be 1

2. start the Test for Prime Factor with K as the input.

Test For Prime Factor:

(Define the lower limit of √N as K,

Make an array of K item,

Starting from K,

Test if N is divisible by K,

If not reduce K by 1, otherwise Mark the K as divisible by making the value of K-th item of the array to be 1.)

So, in according to this procedure, if it discover a factor of the N, for instance, 40 is a factor for 1600. Then it would proceed to look up for the factor of 40, which it would arrive at the results: 1,2,4,5,8,10,20. Since 40 is a factor of 1600, and we can logically conclude that the factor of the factor 40 is also a factor of 1600, i.e. 1,2,4,5,8,10,20 are also factors for 1600, which will be skipped for checking in the bigger loop.

Notice the similarity between checking for factor of the number and the checking for factor of the factor. A usual way to save time when writing program is to re-use what is already developed, therefore my first intention is to re-use the same algorithm for checking for factor of the number to check for factor of the factor. Now, wouldn't we able to apply the same logic so we should also checking for factor of the factor of the number to further shorten the process? Should we should also checking for factor of the factor of the factor of the number to further shorten the process?

So in my mind there is no built it mechanism to prevent me from infinite recursion, but when programming in whatever programming language, I need to explicitly state when I need to re-use a sub-procedure. That is the difference between computer and human mind.

A method to approximate the distribution of Prime numner

The idea is following my idea to find all the factors of a number. We know that for a number X, all its factor could be found within square of X. So for N^2, at most it will have N factors, or it will have none except 1 and N.

Since we also know that the factor of 2 has a probability of 1/2 in any natural number; the factor of 3 has a probability of 1/3 in any natural number; thereby the factor N has a probability of 1/N in any natural number. We thus can find the prime by eliminate all known factors.

To count the prime number within range of 1 to N^2 is thus,

[1-(1/2+1/3+1/4+...+1/N-(Any combinations of 1/2,1/3....1/N))]*N

Now consider the various range:
For N=2, the probability of a prime=1-1/2=1/2,
which is 2.
For N=3, the probability of a prime=1-(1/2+1/3-1/6)=1/3,
the prime numbers are 2,3,5,7 which is 4/9;
there is a difference of 1/9.

How come? Because when counting prime numbers, we discount 2,3 because they are also the multiple of 2 and 3.

We can assume that as N become greater, the different would be smaller.