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) 個新整數。($kdigits($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