问题
有一个数字序列，1487、4817、8147，它们相邻两个之间的差为3330，且有两个不寻常的特性：（一）它们三个都是素数；（二）每个4位数都是其它素数的排列组合。
已知不存在这些特性的3个1位、2位或者3位素数。但还存在另一组递增的4位数符合这些特性。
这组数字连接起来的12位数是什么？
* 传送门
分析
素数的问题向来不敢对它有什么分析。但题目已经限定了，找3个4位素数。所以直接用筛选法生成所有4位素数，然后再用《问题41》排列组合代码生成所有排列组合，再判断是否存在这样的等差数列。
基本上就是暴力解题嘛~
答案
// answer: brute force
const start = Date.now()
function* primesBelow(n) {
const m = Math.floor((n - 2) / 2)
const sieve = new BitSet
for (let i = 1; i < m; ++i) {
let j = i, p = i + j + 2*i*j
for (; p <= m; ++j, p = i + j + 2*i*j)
sieve.set(p, 1)
}
yield 2
for (let i = 1; i <= m; ++i)
if (sieve.get(i) == 0)
yield (2*i + 1)
}
const is_prime = new BitSet
const primes = []
for (const p of primesBelow(10000))
if (p > 1000) { // 只要4位素数
is_prime.set(p, 1)
primes.push(p)
}
function to_number(digits) {
let num = 0
const last = digits.length - 1
for (let i = last; i >= 0; --i)
num += digits[last - i] * Math.pow(10, i)
return num
}
function swap(digits, i, j) {
[digits[i], digits[j]] = [digits[j], digits[i]]
}
function* permutation(digits, from, to) {
if (to > 1) {
if (from == to)
yield to_number(digits)
else
for (let i = from; i <= to; ++i) {
swap(digits, from, i)
for (let num of permutation(digits, from + 1, to))
yield num
swap(digits, i, from)
}
}
}
function to_digits(n) {
const digits = []
while (n > 0) {
digits.push(n % 10)
n = Math.floor(n / 10)
}
return digits
}
function bin_search(array, el, min_idx = 0, max_idx = 0) {
max_idx = max_idx || array.length - 1
while (min_idx <= max_idx) {
const curr_idx = (min_idx + max_idx) >> 1
const curr_el = array[curr_idx]
if (curr_el < el)
min_idx = curr_idx + 1
else if (curr_el > el)
max_idx = curr_idx -1
else
return curr_idx
}
return -1
}
function incr_the_same(prime_pers) {
prime_pers.sort() // 先排序，后面就可以用二分法查找
for (let i = 0; i < prime_pers.length - 2; ++i) {
const first_prime = prime_pers[i]
for (let j = i + 1; j < prime_pers.length - 1; ++j) {
const cur_prime = prime_pers[j]
const last_num = first_prime + 2*(cur_prime - first_prime)
if (bin_search(prime_pers, last_num, j) > j) // last_num的索引理应比j大
return [first_prime, cur_prime, last_num]
}
}
return []
}
function* same_diff_permutation_primes() {
for (const p of primes)
if (is_prime.get(p)) {
const prime_pers = []
const digits = to_digits(p)
for (const per of permutation(digits, 0, digits.length - 1))
if (is_prime.get(per)) {
prime_pers.push(per)
is_prime.set(per, 0) // 避开重复的素数
}
if (prime_pers.length >= 3) {
const r = incr_the_same(prime_pers)
if (r.length > 0)
yield r
}
}
}
let result = 0
for (const r of same_diff_permutation_primes())
if (r[0] != 1487) {
result = r.join('')
break
}
alert(result + ', ' + (Date.now() - start) + 'ms')
