Posts tagged ‘arithmetics’

As discussed in previous post, kakuro can be tackled using simple addition and subtraction during initial stage, particularly if the kakuro puzzle contains some certain arrangement pattern. As an example, see the figure below:
Read the rest of content »

Sort of puzzled — I haven’t seen anywhere mentioning that some kakuro puzzles can be solved with the help of simple arithmetics (yet). Indeed I don’t mean the whole puzzle can be solved merely with addition and subtraction; nor do I mean every puzzle can be worked on this way. Arithmetics usually only works at the beginning, and only works with some kind of puzzles. Here is a simple example. Consider the following fragment:

Read the rest of content »

昨天看 MathForge 看到的，似乎已經是一個月前的「新聞」了。基本上，就是有個電腦系教授 James Anderson 說 0 除以 0 不再是無定義，將它定義為一個稱為 nullity 的數，就可以解決許多一般數學解決不了的問題。

說清楚一點，除了賦予 nullity 定義外，還有：

1. 將 nullity 放置在數線以外，這個「數」不能和任何實數比較大小。
2. 將正無限和負無限定義為一個「數」：
   ；。
3. 將 nullity 和正負無限都納入實數，或者說是實數的 superset（他稱這個集為 “transreal number”）。用數學的表示方式是：
4. 將 nullity 和正負無限直接當成數字來用，拿來進行四則運算、三角函數、極限、微積分運算。

當然，這種想法一定是被人批得體無完膚，而且不外乎以下幾種駡法：

1. 只不過是將以前稱為「無定義」的東西正式給一個名字罷了，甚麼都沒做過。
2. 它根本是抄襲自 IEEE 754 中的 NaN (Not a Number)。
3. 雖然 James Anderson 想解決某個數字除以 0 這個 exceptional case (divide by zero)，但將它定義為一個特殊符號根本無助解決問題，電腦始終不能處理這個「數字」。

不單是 James Anderson 本身，就連 BBC 也因為「報告」這個「大發現」而被人狠狠地煎皮拆骨。根據 James Anderson 在 wikipedia、BBC 等地方親身反駁，而且自己出兩份 paper 講解自己的數學體系，看來他應該是認真的，而且他的目的不是單單為了數學，而是為一個假想的所謂 Perspex machine 創立數學模型，避過 divide by zero 的問題，並企圖將它實現，製造一部電腦令 divide by zero 不再是錯誤。

我覺得，任何人都可以隨便地創作數學體系，只要定義一系列的公理 (axiom)，而且最後沒有自相矛盾，這個體系便算完成了（雖然別人接受與否是另一回事）。如果有人說 1+1=3，最後能演化成完整的系統，那麼這個人一定會聲名大噪吧。另外，James Anderson 是想擴展實數，那就要看他想像出來的系統和實數是否兼容了，如果很多地方不兼容的話，那麼整個系統就沒用了。

我稍為看過一下他的 paper [1] [2]，得出的感覺是，似乎他的理論站不住腳，不論是學術態度、論證方式、兼容性等等都不行。

學術態度：在他的 paper 和 wikipedia 等地方，他都說以往 0/0 沒有定義是錯的，IEEE 754 將這類無法定義的情況寫作 NaN 也是錯的，只有他才是對的。但據我的理解，這些東西應該有定義還是沒有定義，是不可能被肯定或否定；最多只能說，如果沒有定義的話，就是人們現今的數學體系，如果有定義的話就變成另一個體系罷了。除此之外，更有不少語句是以挑戰讀者的語氣寫出來的。這種武斷，不是做學問的人的應有態度。但 James Anderson 不是數學出身，有這種 mind set 不是太奇怪。

論證方式：在他的 paper 裏面，有許多我一看見就覺得毛管豎起了。例如：

• 有沒有見過這樣通分母？
  
  如果上面的行得通，偏偏這樣又不允許：
  
• 他從來沒定義過甚麼是 。只有三個情形定義過：, , 。即是說負數的負數次方沒有定義過，是虛數還是甚麼東西，不知道，提也沒提過；但 偏偏是經常拿來用。

兼容性：加入 -∞, ∞ 和 Φ 之後，大部份實數原本擁有的 group, field, ring 等性質都會消失。例如 multiplicative inverse 和 additive inverse 都不能存在；而因為他將 ∞ 規定為 1/0，所以有人挑戰他尤竟 1/x 在 x=0 時的左極限和右極限是甚麼的時候，他就索性將 1/x 的定義也改變了，說它不是函數，而只是一個 mapping 了事。在一般的數學：

這裏他只取右極限就算，一副遇神殺神、遇佛殺佛的樣子，有甚麼不兼容就將原來的數學「改」成符合自己的模型。

很明顯，他的着眼點一直在無限、極限、微積分的身上，嘗試將所有不能到達的極限（在現今的數學，極限只能無限接近，永遠不能達到）寫成能夠直接得出結果的東西。可是，因為 linear algebra 的性質有不少都消失殆盡，基本上不能說它是實數的擴展概念了。

但是要說它失敗呢，又言之尚早。許多畫家都是生時不得志，死後作品才被人發掘出來大受歡迎，正所謂死後留名吧。數學也是一樣，有不少創意是生前認為太離經叛道的，到死後不知多少年才發覺在某某地方有用。所以呢，等他死後才蓋棺論定為妙。

只有一點肯定：想別人投資製作這種電腦，看來應該是不可能了。

This is a continuation of previous article; here I’ll explain the reasoning behind the method. It’s basically related to the expansion of square of polynomial:

Or arranged alternatively:

These terms may look strikingly similar to the ‘division’ operation: in the first round, the last digit a is doubled and shifted left, and we need to find the digit b so that is the largest possible number deductible.

Now let’s start. Denote n as the number of which we want to find the square root, as well as representing its square root as a sum of series of digits (the series can be finite or infinite). Expressed in equation form:

with = 0-9 for any i. Think about replacing the a, b, c, d… with and so on, as well as replacing with n:

When the terms in right hand side are reduced from n in succession (i.e. after each iteration), the remainder becomes the following infinite series:

……

The remaining task is to show that this series (the remainder) converges to zero, so we can get arbitrary precision with enough iteration. Try to express as sum of remaining terms instead:

which can be arbitrarily small when i is large enough. The conclusion is, after enough iteration, the difference between the real square root and the number we get approaches to zero (since the square of this difference, , approaches to zero as well).

2007-03-03 update: Edited formula so that it works with LatexRender.

Actually I just want to showcase the wordpress FigureRender plugin (superseded by LatexRender plugin and my ScoreRender plugin)

This page mentions quite an interesting way to calculate square root of any real number, which is elementary enough so that even senior primary students and junior secondary school students can do it (corresponding to about 5^th to 8^th year of K-12). It looks strikingly similar to long division notation used by these students (back to the era when calculators are not dominant among them). Too unfortunate that I have no chance to learn it during old days (though I doubt teachers know that as well).

However, the example given in that page is too ‘nice’: 46656, with square root equal to 216. I’ll try to use a non-square number for illustration on how to calculate the digits after decimal point as well: 678.9 . In the following illustration, I will assume reader has read and understood the aforementioned page.

First, group the digits in pairs as mentioned in the page, with decimal point outside of any pair; this means the number is splitted as “6 78 9″, not “67 89″ (the decimal point is between 8 and 9). And find the smallest integer so that its square is not larger than the first digit or first pair of digits. In this case, the result is 2, since 2² ≤ 6; this is written as:

    2
  ┌───────
2 │ 6 78.9
  │ 4
  ├──
  │ 2

Next, borrow the next pair of digits downward, similar to what is done in long division:

    2
  ┌───────
2 │ 6 78.9
  │ 4
  ├─────
  │ 2 78

The left hand side works differently though; in long division the left hand side never changes, but this time the last digit in left hand side (which is 2) is doubled, then multiplied by 10. We have to decide the last digit later as well:

     2  ?
   ┌───────
 2 │ 6 78.9
   │ 4
   ├─────
4? │ 2 78

The question mark is the digit we need to find out; the one on top is also the same digit. That means we need to find the largest digit (in question mark) so that 4? × ? ≤ 278. Here the answer is 6 (46 × 6 = 276):

     2  6
   ┌───────
 2 │ 6 78.9
   │ 4
   ├─────
46 │ 2 78
   │ 2 76
   │ ───────
   │    2 90

Basically, repeat the same process over and over; however, this time some special care must be taken. First, after doubling the last digit on left hand side the number become 52 (46+6):

      2  6. ?
    ┌─────────
  2 │ 6 78.9
    │ 4
    ├─────
 46 │ 2 78
    │ 2 76
    │ ───────
52? │    2 90

And we need to skip this turn, since 52? × ? > 290 for any digit (except 0):

      2  6. 0
    ┌─────────
  2 │ 6 78.9
    │ 4
    ├─────
 46 │ 2 78
    │ 2 76
    │ ───────
520 │    2 90
    │    ───────
    │    2 90 00

Now we can reiterate the next step normally:

       2  6. 0  5
     ┌────────────
   2 │ 6 78.9
     │ 4
     ├─────
  46 │ 2 78
     │ 2 76
     │ ───────
 520 │    2 90
     │    ───────
5205 │    2 90 00
     │    2 60 25
     │    ───────
     │      29 75

One can continue forever like this, though I decide to stop here since the illustration so far should be enough to make some esssential points clear. As a caution, check the answer we get and see if this method really works:

26.05 × 26.05 = 678.6025 < 678.9
26.06 × 26.06 = 679.1236 > 678.9

Next article would be an explanation of how it works.

During old Orkut days, I had been diving into a challenging yet simple mathematical problem. It all starts from the statement: use 4 4’s to form 44, with arithmetic operators or joining digits together. Of course, the answer is simple:

44+4-4=44
44*4/4=44

There are lots of similar answers. And the fun starts from here: what if the answer is not 44, but any other positive integer? What if the 4 basic digits are not all 4’s, but all possible single digits? For example: use 2,6,7,9 to form 21. So a Japanese and me started the mind boggling marathon, finding answers from 1 to 100. It was a lengthy journey, and when we have finally gone through every integer, I wrote a simple script to check the results (If you want to save it, please rename it to check-rpn.pl). It makes use of Perl Math::RPN module and dc so that I don’t need to handle any parenthesis. Although not well written, it is sufficient for my purpose.

However, the problem is, I didn’t save the result

2006-05-24 Update: avoid usage of latex plugin when I don’t need to.

2006-05-28 Update: The Japanese guy is Katsutoshi Seki. He is quite a nice guy and is popular among very active Orkut users.

Sincerely, I didn’t discover this until translating coreutils:

$ factor 192834563192834567
192834563192834567: 37 5211744951157691

$ LANGUAGE=C factor --help
Usage: factor [NUMBER]…
  or:  factor OPTION
Print the prime factors of each NUMBER.

Are coreutils maintainer(s) insane? What is coreutils supposed to be?