返回格式为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

希望能提供一些见解。在一家公司的编码环节中遇到了这个问题。暴力方法最终导致超时错误。

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

编辑2：我分享了codegolf链接，以帮助检查已经可用且预计会超过时间限制的一些解决方案。我尝试了Mathematica和sage两种方法，但都面临着超时错误。

- John Doe

---

这是离题了。你只是重新发布了一个代码高尔夫问题，没有展示出解决它的努力（更不用说那里已经给出了一个一行的Mathematica解决方案）。 - agentp

请注意，代码高尔夫问题允许 x=1，因此解决方案需要进行（微不足道的）调整。 - agentp

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

- גלעד ברקן