由一個十位數說起
3816547290
現在為大家介紹一個很特別的泛位數 (Pandigital Number) - 3816547290。
這個自左看起:3、38、381、3816、38165、381654、3816547、38165472、381654729、3816547290 分別是 1 至 10 的倍數。可惜這樣特別的數只此一個,絕無他選。
我認識此數是由一道奧數題開始:「使用1, 2, 3, 4, 5, 6, 7, 8, 9 全部 9 個數字組成一個 9 位數,使由該數由左至右數起的頭 n 位數組成的數字可被 n 整除。」(香港青少年數學精英選拔賽 2008-09)
九位數和十位數的差別不太重要,不過全部數字應有十個,而反正零亦居於最後。不失完整性,下文姑且把那數作十位數來看。
翻閱網上資料,原來這問題早在 2001年已見有人提出,且得解。
然而對於乎合此每數字可整除其位數的性質的數,稱呼不一,名字繁多:有人稱之為「內整除數」 (In-divisible Number),亦有人戲言為「非凡數字」(Extraordinary Number),或乾脆稱之為「某十位數」 (The Ten Digit Number)。本網跟除維基稱此數為累進可除數 (Polydivisible Number)。
當然,原本的累進可除數並沒有要求數字不可重覆使用,本問題只是多加了這一重限制而已,而這樣的數可稱作泛位累進可除數 (Pandigital Polydivisible Number)。若沒此限,乎合的例子會更多,本網另設專文《累進可除數》再作跟進。
回到我們的問題上,如何找到這一個十位數呢?要知道我們規限了十個數字不重覆,但仍有 10! = 3628800 個不同的可能性。
這好比在茫茫的數字中尋找一個可以通過十個試官考核的全能健兒一樣難,但其實又不是太難的。
我們只要借助各個數的倍數的一些等質便可以知曉了:
首先,左起第一個位是什麼也可以,因為這個一號試官沒有什麼特別要求,凡數皆可通過。
第二,偶數的倍數仍是偶數,故該泛位數的偶數位必然是偶數,這樣便通過了二號試官的要求。
第三,考慮 5 和 10 的倍數的個位,得知左起第五位為 5,第十位為 0,這樣接連便通過了五和十號兩名試官的要求。
第四,由於左起第三及七位為奇數,故考慮 4 和 8 的倍數的特性,第四及八位只可以是 2 或 6;即第二和六位數只可是 4 或 8 。這樣連四號試官的要求也通過。
第五,考慮 3 的倍數的特性,所以左起首三位數的數字之和必為 3 的倍數,同理第四至六位數和第七至九位數亦有相同要求。這次一連攻克三、六、九這三名試官。
由於第四至六位數一組了解較多,可由此組起試,此組可能是 258 或 654。
由於選定了中間的三個數位,故第二和第八位也自然有了定數,再加上 3 的倍數的考慮,對於上述的 258 或 654 合共有二十個不同的可能性,為:
可能解 | 首 7 位 | 7 的倍數否? | 6 至 8 位 | 8 的倍數否? | 解否? |
1472583690 | 1472583 | 是 | 836 | 否,餘 4 | 否 |
1472589630 | 1472589 | 否,餘 6 | 896 | 是 | 否 |
7412583690 | 7412583 | 否,餘 4 | 836 | 否,餘 4 | 否 |
7412589630 | 7412589 | 否,餘 2 | 896 | 是 | 否 |
1836547290 | 1836547 | 否,餘 6 | 472 | 是 | 否 |
1836549270 | 1836549 | 否,餘 1 | 492 | 否,餘 4 | 否 |
3816547290 | 3816547 | 是 | 472 | 是 | 是 |
3816549270 | 3816549 | 否,餘 2 | 492 | 否,餘 4 | 否 |
7896541230 | 7896541 | 否,餘 2 | 412 | 否,餘 4 | 否 |
9876541230 | 9876541 | 否,餘 3 | 412 | 否,餘 4 | 否 |
7896543210 | 7896543 | 否,餘 4 | 432 | 是 | 否 |
9876543210 | 9876543 | 否,餘 6 | 432 | 是 | 否 |
1896543270 | 1896543 | 否,餘 5 | 432 | 否,餘 4 | 否 |
1896547230 | 1896547 | 否,餘 2 | 472 | 是 | 否 |
9816543270 | 9816543 | 否,餘 2 | 432 | 否,餘 4 | 否 |
9816547230 | 9816547 | 否,餘 6 | 472 | 是 | 否 |
3876541290 | 3876541 | 否,餘 4 | 412 | 否,餘 4 | 否 |
7836541290 | 7836541 | 否,餘 6 | 412 | 否,餘 4 | 否 |
3876549210 | 3876549 | 否,餘 5 | 492 | 否,餘 4 | 否 |
7836549210 | 7836549 | 是 | 492 | 否,餘 4 | 否 |
我們以 1、3、7、9 四數作兩兩分組,得 13 - 79 、 19 - 37 、 17 - 39 的分法。再配以一個未用的偶數使三數之和為三的倍數,得 123 - 789 、 183 - 729 、 129 - 387 、 189 - 327 、 147 - 369 五個組合。我們發現若中間選用 654 首四個組合可以用得上,再考慮 8必在第二位及 2 必在第八位,且同組中哪一個奇數先行的問題,故有 16 個不同的組合。若中間的為 258 ,我們只有一組用得上,但也有四個不同的方案可供選擇。對這了二十個候選數作最後甄選,其它們已通過了第一、二、三、四、五、六、九、十號試官的測考,現在只要通過最後的第七和第八號試官的考核便可當選了。
最終十項全能的神奇泛位數是 3816547290,恭喜恭喜 。
但在別的進制 (Numeral System) 會否有類同的數呢?如在十六進制中找一個十六位數包含 0-9 和 A-F,好使左起第一個位是 1 的倍數,首二個位是 2 的倍數,首三個位是三的倍數,如此類推。這便交給大家想一想了。
異世界的全能健兒
那麼在別的進制中會否有類同的數呢?答案是有的,但很稀少。大家可參考下表:
進制 | 泛位累進可除數 | 十進制的值 | 截位的值 |
二進制 | 10 | 2 | 1, 2 |
四進制 | 1230 | 108 | 1, 6, 27, 108 |
3210 | 228 | 3, 14, 57, 228 | |
六進制 | 143250 | 13710 | 1, 10, 63, 380, 2285, 13710 |
543210 | 44790 | 5, 34, 207, 1244, 7465, 44790 | |
八進制 | 32541670 | 6996920 | 3, 26, 213, 1708, 13665, 109326, 874615, 6996920 |
52347610 | 11128712 | 5, 42, 339, 2716, 21735, 173886, 1391089, 11128712 | |
56743210 | 12306056 | 5, 46, 375, 3004, 24035, 192282, 1538257, 12306056 | |
十進制 | 3816547290 | 3816547290 | 3, 38, 381, 3816, 38165, 381654, 3816547, 38165472, 381654729, 3816547290 |
十四進制 | 9C3A5476B812D0 | 7838911147538198 | 9, 138, 1935, 27100, 379405, 5311674, 74363443, 10441088208, 14575234923, 204053288930, 285674045021, 39994444630296, 559922224824157, 7838911147538198 |
(OEIS A111456)
我們重上表中不難發現沒奇數進制的參與,這得看看我的一些計算發現了:
首先,我們看看 N 進制中首 N-1 個數,即使用了一至 N 這 N 個數字。其數值應為
a1 + a2 * N + a3 * N2 + ... + aN * NN-1, 其中那些 a1 、 a2 、 a3 等分別是不同的數字。
若取模 N-1 的同餘,上式值應為零好使該數為 N - 1 的倍數,然而上式取同餘後會變成
a1 + a2 + a3 + ... + aN ,即 1+ 2 + 3 + ... + N = N * (N - 1) / 2
若 N 為奇數,即 (N-1)/2 為整數,上式的同餘值便會是 (N-1)/2 而非零。但若 N 為偶數,則 N/2 為整數,上式的同餘值便會是零。
所以只有偶數進制才可能存有泛位累進可除數了。
第二,上表中 N 進制的序列 b1 、 b2 、 b3 ... 的關係可視為
bk+1 = bk * N + ak+1 ,但若在左起第 M 個位中,而 (M,N) 不等於 1 的話, aM 亦只會是 (M,N) 的倍數,故亦限制了測試的可能性。
因此我們便有偶數位為偶數,奇數位為奇數的因由了。
英文字一個
有一個題外話,由 In-divisible 引起的一個英文字 Indivisibility ,可以解作「不可整除性」或「不可分性」。這英文字有何特別呢?這裡竟有七個「I」之多,亦是日常英文字中最多 「I」的一個字了。當然不常用的英文字或許有更多「I 」的,如 Honorificabilitudinitatibus (不勝光榮)、Indistinguishabilities (不可分辨)、Supercalifragilisticexpialidocious (奇妙的) 均有七個「I」,而 Floccinaucinihilipilification竟有九個「I 」之多呢。Floccinaucinihilipilification 意思是指「把某人或東西視作無用」,看來大家都可以把這長達 29 個英文字「視作無用」了。
.
參考文獻及網址:
Weisstein, E. W. "Divisibility Tests." From MathWorld. http://mathworld.wolfram.com/DivisibilityTests.html.
Wikipedia. "Polydivisible Number" From Wikipedia. http://en.wikipedia.org/wiki/Polydivisible_number.