问题
替换2位数*3的第1位，可以得到6个素数值：13、23、43、53、73、83。
同样地，替换56**3的第3和第4位，可以得到7素数：56003、56113、56333、56443、56663、56773、56993。它们是第1组长度为7、且能通过替换数位生成的素数。而56003，则是这一族素数当中最小的那个数。
找出第1组长度为8、且能通过替换数位（不一定相连）生成出来的素数，并找出该族素数当中的最小值。
* 传送门
分析
这个问题感觉无从入手啊……数位替换的规则不一定相连，那如果想通过拼凑的方式生成这些素数，复杂度是相当高的。再说还不知道上界有多大，拼凑生成的方法估计是没可能完成的……
我倒想到一个接近暴力解题的方法：直接用筛选法生成一堆素数，然后将它们逐个判断看看是否有重复的数位，如果有，则记录它们重复的规则，如此类推，重复规则相同的则追加到相同的数组，最后一点一点增加搜索上界，找到第1个长度为8的数组，便是我们要的答案。这里找到上界为一百万的时候找到了答案。
这个方法暴力，是在于一个素数可能同时属于多个不同的族（按题目的说法）。题目例子就有，例如56003，我们可以用二进制00110来描述它重复的模式，但是到了56663，它自身的重复模式其实是01110。显然，56663的模式较56003的宽泛、可以通过二进制或来测试它们两个模式之间的兼容性，再用异或求出差异。
另外，Google了一下，发现本题竟然可以利用数位之和除以3的方法排除很多可能性。但是那个数学分析过程实在看不懂……暂时先这样吧……
本题目是欧拉计划难度提升的第一题，前50题都是只有5%的人做不出来，这一题则是只有15%的人做不出来。可这个难度已经令我心生敬畏了……
答案
// 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 cache = {/*
binary mask: {
number pattern: [number, ...],
...
},
...
*/}
function save_pattern(mask, pattern, num) {
if (mask in cache) {
const patterns = cache[mask]
if (pattern in patterns)
patterns[pattern].push(num)
else
patterns[pattern] = [num]
}
else {
const patterns = {}
patterns[pattern] = [num]
cache[mask] = patterns
}
}
function* to_compatitable_patterns(mask, pattern, num) {
for (const m in cache)
if (m != mask && (m | mask) == mask) {
let p = pattern
for (let diff = m ^ mask, power = 1; diff > 0; power++, diff >>= 1)
if ((diff & 1) == 1) { // 恢复为能兼容的模式
const base = Math.pow(10, power)
p += (Math.floor(num / base) % 10) * base
}
yield [m, p]
}
}
function to_number(digits) { // 低位在前，高位在后
let num = 0
const last = digits.length - 1
for (let i = last; i >= 0; --i)
num += digits[i] * Math.pow(10, i)
return num
}
function* detect_patterns(num) {
if (num < 10)
return
const digits = [] // 低位在前，高位在后
const digit_counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
const last_digit = num % 10 // 最后一位不用考虑重复的情况
let max_digit = -1
for (let n = Math.floor(num / 10); n > 0; n = Math.floor(n / 10)) {
const digit = n % 10
if (digit > max_digit)
max_digit = digit
digit_counts[digit]++
digits.push(digit)
}
for (let d = 0; d <= max_digit; ++d)
if (digit_counts[d] > 1) { // 只对有重复的数字进行拆分
let mask = 0 // 二进制模式，方便快速匹配
let pattern = [last_digit] // 低位在前，高位在后
for (let i = 0; i < digits.length; ++i)
if (digits[i] == d) {
mask |= (1 << i)
pattern.push(0)
}
else
pattern.push(digits[i])
pattern = to_number(pattern)
yield [mask, pattern]
for (const [m, p] of to_compatitable_patterns(mask, pattern, num))
yield [m, p]
}
}
let result = 0
for (const prime of primesBelow(1000000)) {
for (const [mask, pattern] of detect_patterns(prime)) {
save_pattern(mask, pattern, prime)
if (cache[mask][pattern].length == 8) {
const numbers = cache[mask][pattern]
result = numbers[0]
console.log(numbers)
break
}
}
if (result != 0)
break
}
alert(result + ', ' + (Date.now() - start) + 'ms')
