Невозможно найти правильный номер для Project Euler 23

Question

Я пытался найти проблему более 2 часов, правильный ответ - 4179871, но я только получаю 4177763,

Совершенное число - это число, для которого сумма его собственных делителей точно равно числу. Например, сумма правильных делителями 28 будет 1 + 2 + 4 + 7 + 14 = 28, что означает, что 28 это идеальное число.

Число n называется дефицитным, если сумма его собственных делителей равна меньше n и называется обильным, если эта сумма превышает n.

Поскольку 12 - это наименьшее численное число, 1 + 2 + 3 + 4 + 6 = 16, наименьшее число, которое можно записать как сумму двух чисел 24. Математическим анализом можно показать, что все целые числа больше, чем 28123, может быть записано как сумма двух чисел. Однако этот верхний предел не может быть уменьшен в дальнейшем анализом хотя известно, что наибольшее число, которое не может быть выражается как сумма двух чисел, меньших, чем этот предел.

Найдите сумму всех натуральных чисел, которую нельзя записать как сумма двух обильных чисел.

def factors(num) # function that returns array of factors
  factorsNums = []
  for i in 1..Math.sqrt(num).ceil
    if num % i == 0
      factorsNums.push(i) if i != num
      factorsNums.push(num / i) if ((num / i) < num) && ((factorsNums.include? (num / i)) == false)
    end
  end
  factorsNums
end
abundantNumbers = []

for i in 1..28123 #This loop will push into the array "abundantNumbers" each number from 1 to 28123 that is an abundant number (a number in which the sum of its divisors is bigger than the number itself)
  abundantNumbers.push(i) if factors(i).inject(0, :+) > i
end

abundantSums = []
#this 2 dimensional loop will find the every possible sum of 2 abundant numbers from which we got in the last for loop and push them into another array "abundantSums"
  for i in 0...abundantNumbers.length
    for j in i...abundantNumbers.length
      sum = abundantNumbers[i] + abundantNumbers[j]
      abundantSums.push(sum) if sum <= 28123
    end
  end


abundantSums = abundantSums.uniq.sort #remove duplicates and sort the array

notSums = []

for i in 1..28123 #find numbers which are not the sum of 2 abundant numbers and push them into the array "notSums"
  notSums.push(i) if (abundantSums.include? i) == false 
end
print notSums.inject(0, :+) #print out sum of array elements that are not sums of abundant numbers

Answer 1

При построении метода, который возвращает массив собственных факторов заданного положительного интергера, мы можем использовать метод Prime :: prime_division , который определяет простое разложение каждого положительного целого числа. Например,

require 'prime'

Prime.prime_division(180)
  #=> [[2, 2], [3, 2], [5, 1]]

Это означает, что

180 = 2**2 * 3**2 * 5**1

Более того, каждый фактор 180 равен

2**n2 * 3**n3 * 5**n5

, где 0 << n2 << 2, 0 << n3 << 2 и 0 <= n5 <= 1. Факторы * - это все факторы, кроме 180, число которых

(2+1)*(2+1)*(1+1) - 1 #=> 17

Поэтому мы можем определить метод OP factors (который я переименовал proper_factors) следующим образом.

def proper_factors(n)
  first, *rest = Prime.prime_division(n).
                       map { |m,pow| (0..pow).map { |p| m**p } }
  first.product(*rest).
        map { |arr| arr.reduce(:*) } - [n]
end

proper_factors(180)
  #=> [1, 5, 3, 15, 9, 45, 2, 10, 6, 30, 18, 90, 4, 20, 12, 60, 36]

Затем создайте массив чисел от 12 до 28123.

max_val = 28123    
abundants = (12..max_val).select { |n| proper_factors(n).sum > n }
  #=> [12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80,
  #    ...
  #    12078, 12080, 12084, 12090, 12096, 12100, 12102, 12104, 12108, 12110,
  #    ...
  #    28086, 28092, 28098, 28100, 28104, 28110, 28112, 28116, 28120, 28122]
abundants.size
  #=> 6965

Сумма положительных чисел, которые не равны сумме двух чисел, равных сумме, равна сумме чисел от 1 до 28123 (сумма арифметического ряда) минус сумма чисел от 1 до 28123, равная сумме двух обильные числа. Числа, равные сумме двух чисел, легче вычислить, чем числа, у которых нет этого свойства, поэтому мы рассчитаем желаемую сумму как разницу между двумя суммами.

Сумма чисел от 1 до 28123 равна

all_sum = 28123*(1+28123)/2
  #=> 395465626

Теперь мы вычислим сумму чисел от 1 до 28123, равную сумме двух чисел с избытком. Для этого мы просто накапливаем (в массиве) суммы всех пар чисел, которые не превышают 28123. Конечно, это даст много дубликатов, поэтому мы должны uniq указать массив перед суммированием его значений. (Вместо этого мы можем накапливаться в наборе.)

half_max = max_val/2
  #=> 14061
last_abundants_idx = abundants.size - 1
  #=> 6964

sum_nbrs_sum_two = abundants.each_with_index.with_object([]) do |(n,i),found|
  break found if n > half_max
  (i..last_abundants_idx).each do |j|
    m = n + abundants[j]
    break if m > max_val
    found << m
  end
end.uniq.sum
  #=> 391285755

Здесь массивы found и found.uniq соответственно содержат 12148815 и 26667 элементов. ¹

Последний шаг следующий.

all_sum - sum_nbrs_sum_two
  #=> 4179871

^{1 Обратите внимание, что в третьей строке содержится диапазон (i..last_abundants_idx), а не (i+1..last_abundants_idx), для включения числа 2*abundants[i]. Это верно для всех i, но для большинства i, 2*abundants[i] равно сумме двух разных чисел. Фактически, если i.. было изменено на i+1.., сумма (391285755) уменьшается только на 64.}

Answer 2

Проблема заключалась в том, как обрабатывались факторы, в массиве содержались дубликаты факторов, и это исправление:

def factors(num) # function that returns array of factors  
  factorsNums = []   
  for i in 1..Math.sqrt(num).ceil
    if num % i == 0
      factorsNums.push(i) if i != num && !factorsNums.include? i
      factorsNums.push(num / i) if ((num / i) < num) && ((factorsNums.include? (num / i)) == false)
    end   
  end   
  factorsNums 
end