おはようございます。先週は次男が発熱の為、自分と次男だけ実家で生活していました。幸い次男はインフルエンザは陰性でしたが、なかなか熱が平熱に戻らず、結局、1週間ほど実家で過ごしていました。@kjunichiです。

背景

Mathematicaの公式の以下のツイートで知った。

357686312646216567629137という数が印刷された鉛筆が、イギリスの数学グッズにあります。

売りは、左側からどんなに削っていっても素数でありつづけること！

このような #切捨て可能素数を見つける方法がコミュニティページに投稿されています。ぜひご覧ください。https://t.co/NLQtsj6goR pic.twitter.com/z8LTNVyCHE
— Wolfram Japan (@WolframJapan) 2018年12月26日

truncatable primeをnode.jsで計算してみた

node.jsのv10からbigintがサポートされる

以下のQiitaの記事にあるように、node.jsでもbigintがv10以降サポートされ、大きな数も手軽に扱えるようになっている。

qiita.com

愚直な素数判定だと日が暮れても終わらなかった

Wikipediaには計算機で簡単に計算できる]と書いてあるが、真に受けて愚直な実装で試したら、日が暮れても終わらなかった。(三日三晩放置したが、半分も求めることが出来なかった。。。)

ja.wikipedia.org

手っ取り早くネイティブモジュールで時短を図った

そこで、以前の記事を思い出し

https://abrakatabura.hatenablog.com/entry/2014/11/28/175853

このbignumモジュールの素数判定を利用して高速化を図ろうとした。

WindowsではOpenSSLのビルドが必要に！

bignumモジュールのビルドでWindowsではOpenSSLの.libファイルが必要になった。DLLファイルはnode.jsに含まれているが、 Windowsは.libファイルがnpmモジュールのビルドに必要なため、これを用意する必要があった。

OpenSSLのビルドにはPerlが必要となったり、なかなか家族旅行中のSurface Goでの作業では大変だった。

こういうのが、Windowsの嫌なところ、わざわざnode.js以外に依存しないnpmを選んでも.libファイルの扱いがナー pic.twitter.com/2AgPRy2fxE
— kjunichi (@kjunichi) December 30, 2018

そう言えば、以前、東京Node学園で大津さんの「祝Node-v10リリースこれまでのNodeの振り返り」でもPerlが使われているという話を思い出した。そう、OpenSSLのビルドにはPerlが必要なのだった。

また、とにかく最新のOpenSSLのバージョンで良いわけでもなく、Node.jsで利用している系のバージョンに限定されている模様。今回は OpenSSL_1_0_2-stable を使用した。ビルドは

INSTALL.W64
INSTALL.W32

を参考にすすめ、インストール先をbignumモジュールの参照している openssl-win64 を指定する。

成果物

WindowsはにOpenSSLをビルドした後、macOS、Linuxは事前準備なしで

npm i bignum

試行錯誤したままのコードなので、ちょっと恥ずかしいけど。

const bignum = require('bignum')

const cachePrime = {}
let findDigit = 0
let counter = 1
let cacheCounter = 0
let numOfTruncatablePrime = 1

const isPrime = (n) => {
    const bn = bignum(n.toString())
    const r = bn.probPrime(80)
    //console.log(`r = ${r}`)
    return r
}

const getNum = () => {
    if (findDigit > 0) {
        //console.log(cachePrime[findDigit - 1][cacheCounter])
        if (cachePrime[findDigit - 1][cacheCounter] === undefined) {
            return -1
        }
        const sNum = counter.toString() + cachePrime[findDigit - 1][cacheCounter++].toString()
        //console.log(sNum)
        num = BigInt(sNum)
        if (cacheCounter >= cachePrime[findDigit - 1].length) {
            cacheCounter = 0
            counter++
        }
    } else {
        num = BigInt(counter)
        counter++
    }
    if (counter > 9) {
        findDigit++
        //console.log(`findDigit = ${findDigit}, counter = ${counter}`)
        cachePrime[findDigit] = []
        counter = 1
        cacheCounter = 0
    }
    //console.log(`${num}`)
    return num
}

const check = (num) => {
    if (!isPrime(num)) {
        return
    }
    let cnum = num.toString()
    const digit = cnum.length

    console.log(`truncatable prime (${numOfTruncatablePrime++}[${digit}]) : ${num}`)
    cachePrime[digit - 1].push(num)
}

cachePrime[0] = []
while (true) {
    const num = getNum()
    if (num > 0) {
        //console.log(`num = ${num}`)
        check(num)
    } else {
        break
    }
}

旅行中にOpenSSLをビルドした甲斐があり、node.jsでbignumモジュールを使う事で truncatable primeをwikipediaの記載のように簡単に計算機で求める事が出来るようになった https://t.co/FQAbRg8xsm pic.twitter.com/9DB7w4NOhH
— kjunichi (@kjunichi) December 31, 2018