math - 返回格式 x^y 的第 i 个数字，其中 x 和 y 是整数

Question

x 和 y 是大于 1 的整数。
特殊数字可以表示为 x^y。
请注意，特殊数字序列按升序排列(4、8、9、16、25、27、32、...)。
给定一个整数 i，程序应该返回第 i 个特殊数字。

i=0 -> num=4
i=4 -> num=25

想要一些见解。在一家公司的编码回合中遇到了这个问题。蛮力最终得到了 TLE。

编辑 1:找到一个链接:https://codegolf.stackexchange.com/questions/78985/find-the-n-th-perfect-power .

Edit-2:我分享了 codegolf 链接，以帮助检查一些已经可用且预计会超过时间限制的解决方案。我尝试了 Mathematica 解决方案和 sage 解决方案方法，都遇到了 TLE。

Answer 1

这个问题相当于找一个整数j哪里log_j k是一个整数，且 j位于具有上限 k 的序列中使得 sum [floor(log_j k) - 1 | j <- [2..floor(sqrt k)] == i
我们可以粗略估计i在哪里第一个元素将通过有限迭代进行二分搜索。如果我们猜测 m^2 处的数字，可以计算的最高基数是:

m

然后我们可以检查较低的基数并将它们的对数计数相加。例如，i = 10 :

Guess: 10^2
Highest base: 10

Then at minimum we have (10 - 1) + (floor(log2 (10^2)) - 1)
= 15 elements. Too many.


Guess: 5^2 
Highest base: 5
Minimum element count: (5 - 1) + (floor(log2 (5^2)) - 1) = 8

Iterate over logs:
  -- Because of the exponential nature of the problem,
  -- if the guess is too large, the bulk of the elements will appear
  -- early in the iteration; and if it's too small, the limit on
  -- exponents will drop early allowing for early exit in either case.

  [floor(logBase x 25) - 1 | x <- [2..4]] = [3,1,1]
  sum ([1] ++ [3,1,1]) = 6. Too few.


Guess: 7^2
Highest base: 7
Minimum element count: (7 - 1) + (floor(log2 (7^2)) - 1) = 10

Iterate over logs:
  [floor(logBase x 49) - 1 | x <- [2..6]] = [4,2,1,1,1]
  sum ([1] ++ [4,2,1,1,1]) = 10

Answer: 7^2