给定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范围内。

null

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))

null

Answer 1

由于逐位数的递归可以使它们相互依赖，因此对小于m的所有余数进行求解，并返回余数0的解。给定“特殊”数字的计数表，这些数字被m除以时会留下余数r。然后将索引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]