Наименьшее натуральное число, сумма делителей которого не меньше миллиона

Question

Рассмотрим последовательность: 1, 6, 48, 360, 3120, 27720, ?

Энный элемент этой последовательности равен наименьшему натуральному числу, имеющему эн-значную сумму делителей (включая 1 и само число). Например, сумма делителей числа 360 равна 1170, а у всех чисел, меньших 360, сумма делителей меньше 1000.

Какой член этой последовательности скрывается под знаком вопроса? Иными словами, каково наименьшее натуральное число, сумма делителей которого не меньше миллиона?

Мой швахкод (эвфемизм к слову «авнакод») работает слишком медленно:

def sumdiv(n):
    summa=0
    for a in range (1, n+1):
        if n%a==0:
            summa+=a
    return summa 
    
i=1
while sumdiv(i)<1000000:
    i+=1
print(i, sumdiv(i))

Пожалуйста, подскажите, как его ускорить?

Answer 1

Можно запустить тоже самое, что у вас на С++. Вывело ответ(249480) за 2-3 минуты.

int64_t sumdiv(int64_t n) {
  int64_t sum = 0;
  for(int i = 1; i <= n; ++i) {
    if(n % i == 0) {
      sum += i;
    }
  }
  return sum;
}

int main()
{
  int64_t sum = 1;
  int64_t i = 1;
  while(sum < 1000000) {
    i += 1;
    sum = sumdiv(i);
    if(i % 1000 == 0) {
      std::cout << "CURRENT: " << i << " " << sum << std::endl;
   }
  }
  std::cout << "RES: " << sum << " " << i << std::endl;
  return 0;
}

И более быстрая версия того же самого(от Qwertiy) (0.9 сек)

int64_t sumdiv(int64_t n) {
  int64_t sum = 0, i;
  for(i = 1; i * i < n; ++i) {
    if(n % i == 0) {
      sum += i + n/i;
    }
  }
  return sum + (i*i==n ? i : 0);
}
 
int main()
{
  int64_t sum = 0;
  int64_t i = 1;
  while(sum < 1000000) {
    i += 1;
    sum = sumdiv(i);
  }
  std::cout << "RES: " << sum << " " << i << std::endl;
  return 0;
}

Answer 2

Давайте представим себе, что у нас есть разложение числа на его собственные множители (множители, отличные от единицы и от самого числа): N = m1*m2*m3*...*mk

Тогда все деители этого числа - это все комбинации множителей.

Соответственно, сумма делителей - это сумма всех уникальных комбинаций из произведений этих множителей.

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

Поэтому, думаю, такой алгоритм будет работать быстрее, чем перебор всех делителей.

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

Сейчас я постараюсь написать этот алгоритм на питончике - давно не пользовался им, а иногда он очень выручает.

Answer 3

По аналогии с решетом Эратосфена: https://ideone.com/17WrNg

n = 1000000
d = [1] * (n+1)
 
for x in range(2, len(d)):
  for y in range(x, len(d), x):
    d[y] += x
 
i = next(i for i,x in enumerate(d) if x >= n)
print(i)

Если верить онлайн-калькулятору (самому было лень писать), то число имеет 160 делителей

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 22, 24, 27, 28, 30, 33, 35, 36, 40, 42, 44, 45, 54, 55, 56, 60, 63, 66, 70, 72, 77, 81, 84, 88, 90, 99, 105, 108, 110, 120, 126, 132, 135, 140, 154, 162, 165, 168, 180, 189, 198, 210, 216, 220, 231, 252, 264, 270, 280, 297, 308, 315, 324, 330, 360, 378, 385, 396, 405, 420, 440, 462, 495, 504, 540, 567, 594, 616, 630, 648, 660, 693, 756, 770, 792, 810, 840, 891, 924, 945, 990, 1080, 1134, 1155, 1188, 1260, 1320, 1386, 1485, 1512, 1540, 1620, 1782, 1848, 1890, 1980, 2079, 2268, 2310, 2376, 2520, 2772, 2835, 2970, 3080, 3240, 3465, 3564, 3780, 3960, 4158, 4455, 4536, 4620, 5544, 5670, 5940, 6237, 6930, 7128, 7560, 8316, 8910, 9240, 10395, 11340, 11880, 12474, 13860, 16632, 17820, 20790, 22680, 24948, 27720, 31185, 35640, 41580, 49896, 62370, 83160, 124740, 249480

А их сумма получается 1045440.

БЛОГ НА HUSL

Наименьшее натуральное число, сумма делителей которого не меньше миллиона

Ответы (3 шт):