Perl6: 十進位可左截短質數之判定與其產生器
作者:gugod 發佈於: #perl6由於在推持朋友圈傳遞閉包上看到 "20190823" 是「質數日」這樣的訊息,就來隨意作文好了。
將其中一推全文引用如下:
2019年5月23日になりました。
20190523→素数 0190523→素数 190523→素数 90523→素数 0523→素数 523→素数 23→素数 3→素数
どこから左を切っても素数となる珍しい日です!
(出處 @9973_prm/1131217915389157383)
原推文為日文,在日語中「素数」便是質數之意。此推文展示出的演算手法,是為「可左截短質數」的一種。 可截短質數在 Wikipedia 上所述定義為:
可截短質數是在特定進位制下,位數中不包括0的特定質數。可左截短質數是指若從最高位數起,由左側依序刪除數字,其結果都是質數的數。
以下程式範例選用 Perl6 語言。先試著定義出能判別整數 $n
在十進位基底系統之中是否為可左截短質數。在此,先依照述推文所展示的效果、忽略「不包括 0」這條規則。
令輸入 $n
的型別為 Int,在十進位基底系統之中,其位數之數為的求法為:
sub digits(Int $n) {
return floor(log($n, 10)) + 1;
}
「將最左側 k 個數字刪除」的演算,能用以下函式做到:
sub truncate-left(Int $n, Int $k) {
my $t = 10 ** ( digits($n) -$k );
return $n - floor( $n / $t ) * $t;
}
或是先把輸入轉為字串型別 Str,再用 substr
來做也可:
sub truncate-left(Int $n, Int $k) {
return Int( "$n".substr($k) )
}
把一個整數 $n
由左側截去 $k
位數,而 $k
的範圍為 1..digits($n)
,因此,可變得 digits($n)
個新整數。($k
為 digits($n)
時表示截去 0 個位數,結果與 $n 相同)
my @numbers = (1..digits($n)-1).map(-> $k { truncate-left($n, $k) });
若全為質數,則 $n
為可左截短質數。
@numbers.map({ .is-prime }).all
以上程式碼合併起來,便為:
sub is-left-truncatable-prime(Int $n) {
return (1..digits($n)-1).map(-> $k { truncate-left($n, $k) }).map({ .is-prime }).all;
}
此函式裡最後的 all
函式為能建出 all-Junction,在布林語境中取值時,若容器中所有值皆為真值,則取為真值,否則取為偽值。
有了這函式之後,便可先產生許多數字,再以此判函式過濾出可左載短質數。例:取得 123456 以上,前 10 個可左截短質數的程式碼為:
(123456..*).grep(-> $n { is-left-truncatable-prime($n) })[1..10].map({ .say })
輸出:
124337
124373
124547
124967
126053
126113
126317
126947
127043
127103
Wikipedia 上也指出,十進制的可左截短質數共有4260個(各位數中不含 0 的),其中最大的為 357686312646216567629137。如果要從 2 開始以上述 is-left-truncatable-prime
函式來逐一測試去搜出的所有可左截短質數的話,絕對會花去太多時間。但其實有個更快的產生方式。
若已知所有 K 個位數的可截短質數,只要取其一,於其左方增加 1..9 其中一位數字,再測試是否為質數,便可產生出所有 K+1 個位數的可截短質數。一位數的質數為 2,3,5,7,由此可生出所有二位數的可左截短質數:13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97。
以下是這個產生器的全文。產生之後,隨即輸入到 STDOUT:
my @p = (2,3,5,7);
while @p.elems > 0 {
.say for @p;
@p = @p.flatmap(-> $p { (1..9) <<~>> $p }).grep({ .is-prime });
}
此段程式碼使用了 超算符 (Hyper operator) <<~>> 與 flatmap。(1..9) <<~>> $p
的結果就是將 (1..9)
與 $p
做外積,唯將 ×
算符符號換為字串相連算符 ~
。結果有 9 項,為 (1~$p, 2~$p, 3~$p, 4~$p, 5~$p, 6~$p, 7~$p, 8~$p, 9~$p)
。若 $p == 19
,則 (1..9) <<~>> $p
為 ("119", "219", "319", "419", "519, "619", "719", "819", "919")
。
此程式的完整輸出在此: left-truncatable-primes.txt。
關於產生可截短質數的各語言程式碼,在 RosettaCode 網站上有一頁內容可參考:rosettacode/Truncatable_primes。此外也可看看 Numberphile 去年此時的這段影片:357686312646216567629137 - Numberphile、以及 OEIS/A024785。