r - 1-1000 中的 x 和 1-1000 中的 y 使用 R 的 x^y 有多少独特的幂

Question

使用 R，计算 x 和 y 是整数 ∈ [1, 1000]，存在多少个唯一的幂 x^y。这是我现在的，只是不知道如何消除重复的数字，

x<-1:1000
y<-1:1000
for (i in x)
{
    for (j in y){
       print(i^j)
    }
}

Answer 1

对此的组合方法可以将 1-1000 的数字分成等价类，其中类中的每个数字都是其他数字的幂。例如，我们会将数字 1-10 拆分为 (1)、(2、4、8)、(3、9)、(5)、(6)、(7)、(10)。等价类之间的值的幂不会重合，所以我们可以单独处理每个等价类。

num.unique.comb <- function(limit) {
  # Count number of powers in each equivalence class (labeled by lowest val)
  num.powers <- rep(0, limit)

  # Handle 1 as special case
  num.powers[1] <- 1

  # Beyond sqrt(limit), all unhandled numbers are in own equivalence class
  handled <- c(T, rep(F, limit-1))
  for (base in 2:ceiling(sqrt(limit))) {
    if (!handled[base]) {
      # Handle all the values in 1:limit that are powers of base
      num.handle <- floor(log(limit, base))
      handled[base^(1:num.handle)] <- T

      # Compute the powers of base that we cover
      num.powers[base] <- length(unique(as.vector(outer(1:num.handle, 1:limit))))
    }
  }
  num.powers[!handled] <- limit

  # Handle sums too big for standard numeric types
  library(gmp)
  print(sum(as.bigz(num.powers)))
}
num.unique.comb(10)
# [1] 76
num.unique.comb(1000)
# [1] 978318

这种组合方法的一个优点是，与蛮力方法相比，它的速度非常快。例如，在限制设置为 1000 的情况下，计算时间不到 0.1 秒。这使我们能够计算更大值的结果:

# ~0.15 seconds
num.unique.comb(10000)
# [1] 99357483

# ~4 seconds
num.unique.comb(100000)
# [1] 9981335940

# ~220 seconds
num.unique.comb(1000000)
# [1] 999439867182

这是一个非常简洁的结果——我们可以在 4 分钟内计算出 1 万亿个数字中唯一值的数量，其中每个数字最多可以有 600 万个数字!

更新:基于这个组合代码，我更新了 OEIS entry for this sequence包括最多 10,000 个术语。