Perl6: 十進位可左截短質數之判定與其產生器

作者：gugod 發佈於：2019/08/25 #perl6

由於在推持朋友圈傳遞閉包上看到 "20190823" 是「質數日」這樣的訊息，就來隨意作文好了。

將其中一推全文引用如下：

2019年5月23日になりました。
20190523→素数 0190523→素数 190523→素数 90523→素数 0523→素数 523→素数 23→素数 3→素数
どこから左を切っても素数となる珍しい日です！

原推文為日文，在日語中「素数」便是質數之意。此推文展示出的演算手法，是為「可左截短質數」的一種。可截短質數在 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 })

輸出：

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。