给定n，求出有多少个n位数，使得这个数字在素数索引上有素数，并且可以被m整除

Question

特殊数字是这样的，即数字在素数索引上有素数(2，3，5，7(，在非素数索引上是非素数。(例如，15743-素数索引(2，3，5(具有素数(5，7，3((。有多少个n位数的特殊数字也可以被m整除。

例如，对于n=2和m=2，答案将是[12,42,62,82,92]，因此为5。

我写了一个回溯算法，可以找到所有这些特殊数字的排列，然后检查这些特殊数字中的每一个是否可以被m整除，并返回计数。这适用于n和m的小值，但问题的n、m值在0-500之间。

var primes = [2, 3, 5, 7]
var nonPrimes = [1, 4, 6, 8, 9]

n = 2 // number of digits
m = 2 //divisor
k = 0 //remainder
function rec(index, temp, count) {
if (temp.length >= n) {
if (Number(temp) % m === k) {
/* console.log(temp) */
count += 1
}
return count
}
if (primes.includes(index)) {
for (num1 in primes) {
temp += primes[num1];
count = rec(index + 1, temp, count)
temp = temp.slice(0, -1)
}
} else if (nonPrimes.includes(index)) {
for (num2 in nonPrimes) {
temp += nonPrimes[num2];
count = rec(index + 1, temp, count)
temp = temp.slice(0, -1)
}
}
return count
}
console.log("number of n-digit special numbers which are divisible by m with remainder k is ", rec(1, "", 0))

Answer 1

由于逐位递归可以使它们相互依赖，因此为所有小于m的余数求解，并返回余数0的解。给定一个计数表；特别的"；当除以m时留下余数r的数字，列表直到第i个索引。然后将索引i + 1:的行制成表格

(1) Transform the current row of remainders,
each storing a count, multiplying by 10:
for remainder r in row:
new_r = (10 mod m * r) mod m
new_row[new_r] += row[r]

row = new_row

(2) Create new counts by using the new
possible digits:
initialise new_row with zeros
for d in allowed digits for this ith row:
for r in row:
new_r = (r + d) mod m
new_row[new_r] += row[r]

例如，n = 2, m = 2:

row = [None, None]
# We are aware of the allowed digits
# at the ith row
row[0] = 3  # digits 4, 6 and 8
row[1] = 2  # digits 1, 9
row = [3, 2]

(1( 转换：

new_row = [0, 0]
remainder 0:
new_r = (10 mod 2 * 0) mod 2 = 0
new_row[0] += row[0] = 3

remainder 1:
new_r = (10 mod 2 * 1) mod 2 = 0
new_row[0] += row[1] = 5

row = new_row = [5, 0]

(2( 创建新计数：

new_row = [0, 0]

d = 2:
rd = 2 mod 2 = 0

r = 0:
new_r = (0 + 0) mod 2 = 0
new_row[0] += row[0] = 5
r = 1:
new_r = (1 + 0) mod 2 = 1
new_row[1] += row[1] = 0

d = 3:  # Similarly for 5, 7
rd = 3 mod 2 = 1

r = 0:
new_r = (0 + 1) mod 2 = 1
new_row[1] += row[0] = 5
r = 1:
new_r = (1 + 1) mod 2 = 0
new_row[0] += row[1] = 5  # unchanged

row = new_row = [5, 15]

[12,42,62,82,92]
[13,15,17,
43,45,47,
63,65,67,
83,85,87,
93,95,97]