Поиск, если число является суммой из двух степеней.

Question

Я успешно решил проблему, где я бы определил, можно ли записать число в виде суммы двух квадратов.

25 => [5,0], [3,4] 
5**2+ 0**2 = 25 and 3**2 + 4**2 = 25 

Вот как я решил, что

def power_pairs(num) 
    a = (0..100).to_a 
    a.combination(2).select{|x|(x[0] ** 2) + (x[1] ** 2) == num} 
end 

power_pairs(40) 
=> [[2,6]] 

Я хочу изменить этот метод, чтобы определить, является ли число прошло в самом деле количество энергии.

Число мощности может быть представлено в виде суммы в 2 степени.

27 = 0**2 + 3**3 
28 = 1**2 + 3**3 

Как исправить этот метод

Answer 1

Предположения

Я предположил, что, учитывая целое n >= 8, вы хотите, чтобы определить, есть ли целые числа a, p, b, q, все >= 2, такие, что:

n = a**p + b**q 

Код

He Это один из способов сделать это. Обратите внимание, что я кэширую значения для выполнения умножения, а не для возведения в степень (хотя нужно проверить, что это действительно экономит время или исчерпает доступную память).

def sum_power(n) # n >= 2 
    @cache = (2..n-1).each_with_object({}) { |i,h| h[[i,2]] = i*i } 
    (2..Float::INFINITY).each do |pow| 
    (2..n-4).each do |m| 
     x = m_to_pow(m,pow) 
     if x <= n-4 
     pow_other = power(n-x) 
     return [[m,pow], pow_other] if pow_other 
     else 
     return nil if m == 2 
     break 
     end 
    end 
    end 
end 

def power(n) # n >= 2 
    (2..Float::INFINITY).each do |pow| 
    (2..n-1).each do |m| 
     x = m_to_pow(m, pow) 
     case x <=> n 
     when 0 then return m, pow 
     when 1 
     return nil if m == 2 
     break 
     end 
    end 
    end 
end 

def m_to_pow(m,pow) 
    x = @cache[[m,pow]] 
    if x.nil? 
    x = m * @cache[[m,pow-1]] 
    @cache[[m,pow]] = x 
    end 
    x 
end 

Примеры

sum_power(25)    #=> [[3, 2], [4, 2]]  => 3**2 + 4**2 
sum_power(26)    #=> nil 
sum_power(3468)    #=> [[7, 3], [5, 5]]  => 7**3 + 5**5 
sum_power(1426716)   #=> [[19, 3], [17, 5]] => 19**3 + 17**5 

Answer 2

Ниже дается ответ разделить число на сумму двух чисел одинаковой мощности. Его можно изменить, чтобы решить вашу проблему. Вам просто нужно изменить powers.

def powers power, num 
    a = [] 
    i = 0 
    while (k = i ** power) <= num 
    a.push([i, k]) 
    i += 1 
    end 
    a 
end 

powers(3, 100) 
# => [[0, 0], [1, 1], [2, 8], [3, 27], [4, 64]] 

def power_pairs power, num 
    a = powers(power, num) 
    a.map{|i, k| [i, a.find{|_, l| l == num - k}.to_a.first]} 
    .select(&:last) 
    .map(&:sort) 
    .uniq 
end 

power_pairs(2, 25) 
# => [[0, 5], [3, 4]] 

power_pairs(3, 28) 
# => [[1, 3]]