给定 n，找出有多少个 n 位数字使得该数字在素数索引处具有素数并且可以被 m 整除？

Question

特殊数字是指这些数字在素数索引上具有素数数字 (2、3、5、7)，在非素数索引上具有非素数值。（例如，15743 - 质数索引 (2, 3, 5) 具有质数位 (5, 7, 3)）。能被m整除的n位特殊数有多少个

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

我写了一个回溯算法，找到特殊数字的所有此类排列，然后检查每个特殊数字是否可以被 m 和 return 计数整除。这适用于较小的 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 的余数和 return 余数 0 的解决方案。给定 table计算除以 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]

给定 n，找出有多少个 n 位数字使得该数字在素数索引处具有素数并且可以被 m 整除？

Given n, find how many n-digit numbers are there such that the number has prime digit at prime indices and is divisible by m?

javascript

algorithm

math

primes

permutation