找到最大的x^y小於數字

我有數字A（從數字0,1,2,3構建）。我想找到最小的x和y，如果我做X ^易得到比A找到最大的x^y小於數字

X ^Ÿ< = A X^Y小的最大數量是最大

加X和Y不能是十進制數，只有「整數」

例如：

A = 7 => x^y = 2^2 
A = 28 => x^y = 3^3 
A = 33 => x^y = 2^5

等

編輯： 由於izomorphius在評論中提出，它將始終解決x = A和y = 1的問題。但那不是理想的結果。我希望x和y儘可能地接近數字，因爲它可以。

來源

2012-11-14 Martin Perry

請添加更多的語句。很顯然，如果y = 1，您總是有選項x = A和y = 1。 –

另外，「最小的x和y」是什麼意思？這不是一個數學表述。 – Jon

x和y是整數，還是可以浮動？ –

幼稚解決方案可以是：

做a^y對於某一常數a「最接近但不高於」編號，以A爲：

a^{floor(log_a(A))} [其中log_a(A)是用鹼A的a對數，在大多數編程語言中可以計算爲log(A)/log(a)]

通過遍歷範圍[2,A)中的所有a s，您可以找到該數字。

該解決方案是O(A * f(A))其中f(A)是你的POW /日誌複雜

附：如果你希望你的指數（y）更大然後1，你可以簡單地重複範圍內[2,sqrt(A)] - 它的時間複雜度降低到O(sqrt(A) * f(A)) - 並讓你只用數字的指數更大然後1.

來源

2012-11-14 13:10:05 amit

謝謝......多數民衆贊成在爲我工作後，一些調整:) –

這種解決方案是非常天真。 –

這是不清楚你在問什麼，但我會嘗試猜測。

我們首先爲實數z解出方程z^z = a。令u和v分別爲z向上舍入。在三個候選人中，(u,u),(v,u),(u,v)我們選擇最大的那個不超過a。

示例：出具者案例a = 2000。我們通過數值方法（見下文）解決z^z = 2000以獲得近似解決方案z = 4.8278228255818725。我們向下取整以獲得u = 4和v = 5。我們現在有三個候選人，4^4 = 256,4^5 = 1023和5^4 = 625。他們都小於2000，所以我們採取給出最大答案的是x = 4,y = 5。

這裏是Python代碼。功能solve_approx做你想做的。它適用於a >= 3。我相信你自己可以應付案件a = 1和a = 2。

import math 

def solve(a): 
    """"Solve the equation x^x = a using Newton's method""" 
    x = math.log(a)/math.log(math.log(a)) # Initial estimate 
    while abs (x ** x - a) > 0.1: 
     x = x - (x ** x - a)/(x ** x * (1 + math.log(x))) 
    return x 

def solve_approx(a): 
    """"Find two integer numbers x and y such that x^y is smaller than 
    a but as close to it as possible, and try to make x and y as equal 
    as possible.""" 
    # First we solve exactly to find z such that z^z = a 
    z = solve(a) 
    # We round z up and down 
    u = math.floor(z) 
    v = math.ceil(z) 
    # We now have three possible candidates to choose from: 
    # u ** zdwon, v ** u, u ** v 
    candidates = [(u, u), (v, u), (u, v)] 
    # We filter out those that are too big: 
    candidates = [(x,y) for (x,y) in candidates if x ** y <= a] 
    # And we select the one that gives the largest result 
    candidates.sort(key=(lambda key: key[0] ** key[1])) 
    return candidates[-1]

這裏是一個小演示：

>>> solve_approx(5) 
solve_approx(5) 
(2, 2) 
>>> solve_approx(100) 
solve_approx(100) 
(3, 4) 
>>> solve_approx(200) 
solve_approx(200) 
(3, 4) 
>>> solve_approx(1000) 
solve_approx(1000) 
(5, 4) 
>>> solve_approx(1000000) 
solve_approx(1000000) 
(7, 7)

來源

2012-11-14 13:56:03

但是，這不符合'A = 33 => x^y = 2^5'。然而，如何解決最大化'x^y'和最小化'| x - y |'之間的可能衝突並未被指定。 –

事實上，它沒有被指定，並且由於我無法讀懂頭腦，所以我做了這樣的事情，以便「x」和「y」之間的差別總是最大爲1.我相信還有其他的解讀。 –

找到最大的x^y小於數字

回答

相關問題