perrin-prime-check.ts

// perrin(n) / n === 0
//  =
//   isPrime(n)

const perrinMemo: [bigint, bigint, bigint] = [0n, 2n, 3n]
const primeMemo: number[] = [2, 3]

function perrinNext(): bigint {
	const next = perrinMemo[0] + perrinMemo[1]
	perrinMemo[0] = perrinMemo[1]
	perrinMemo[1] = perrinMemo[2]
	perrinMemo[2] = next
	return next
}
function isPerrinPrime(n: number): boolean {
	return perrinNext() % BigInt(n) === 0n
}

for (let i = 4; i <= 100000; i++) {
	if (isPerrinPrime(i) !== isPrime(i)) {
		console.log(i)

		break
	}
	if (i % 1000 === 0) {
		console.log(i / 1000)
	}
}
console.log('end')

function isPrime(n: number): boolean {
	let res = true
	if (n === 1) return false

	for (const p of primeMemo) {
		if (p ** 2 > n) break
		if (n % p === 0) {
			res = false
			break
		}
	}
	if (res) primeMemo.push(n)
	return res
}