Треугольное число с большим количеством делителей

Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-е треугольное число равно 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Перечислим делители первых семи треугольных чисел:

1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28
Как мы видим, 28 - первое треугольное число, у которого более пяти делителей.

Каково первое треугольное число, у которого более пятисот делителей?

Решение (F#)

Для начала немного википедии: тругольное число номер N можно вычислить по формуле
N*(N+1)/2, следовательно для N=7, n = 7*8/2 = 28

• объявим функцию divlist создающую список всех множителей числа a с помощью перебора всех чисел от 1 до a/2
• функция divsnum нужна для определения количества множителей треугольного числа номер n по следующему алгоритму:
  1. берем список множителей для n и (n+1)/2, если оно нечетное или для n/2 и n+1, если четное
  2. произведение количеств этих множителей и будет количеством множителей треугольного числа номер n
     например для числа номер 7 (это 28) алгоритм будет работать так: множители числа 7 это 1 и 7 (итого 2 шт), множители числа 4 это 1,2,4 (итого 3 шт) следовательно количество множителей для числа номер 7 (=28) будет 2*3 = 6
• time_from это утилитарная функция, которая возращает прошедшее время с момента t0 в миллисекундах
• запоминаем текущее время
• solv это рекурсивная фукция для решения задачи, если множителей больше 500 то вычисляем треугольное число, если меньше - то проверяем слудеющее

let divlist a =
    seq {
        yield! seq { 1 .. a / 2 }
        a
    }
    |> Seq.filter (fun x -> a % x = 0)

let divsnum n = 
  let d0,d1 = 
    if n%2 = 0 then divlist (n/2), divlist (n+1)
    else divlist n, divlist ((n+1)/2)
  (Seq.length d0)*(Seq.length d1)

let time_from (t: System.DateTime) =
    (System.DateTime.Now - t).TotalMilliseconds

let t0 = System.DateTime.Now

let rec solv n = 
  if divsnum n <= 500 then solv (n+1)
  else n*(n+1)/2

let answer = solv 1

printfn "answer is %d, time %.0f ms" answer (time_from t0) //answer is 76576500, time 1512 ms
//76 576 500 = 12375*12376/2

Оптимизация

• время работы вполне приемлемое, так что сделаем самое очевидное
• в рамках технической оптимизации нужно запоминать множители, т.к. вычисляются они многократно повторно - делать не будем
• алогоритмически можно изменить саму функцию вычисления множителей, например так:

let divlist a =
    seq {
        yield! seq { 1 .. a / 3 }
        a / 2
        a
    }
    |> Seq.filter (fun x -> a % x = 0)

...

let answer = solv 3 //answer is 76576500, time 978 ms

• т.е. выкинуть ненужный интервал от a/3 до a/2 ибо в нем точно ничего нет, но начинать тогда нужно с 3-го числа
• как видно ускорение составило 1.5 раза
• эту функцию можно оптимизировать и далее, например проверять до квадратного корня числа, и брать все обратные:

let isq = float >> sqrt >> int

let divlist (a: int) =
    seq {
        for b in 1 .. isq a do
            if a % b = 0 then
              yield b
              if a/b <> b then yield a/b
    }

• где isq это функция извлечения квадратного корня из целого числа путем преобразования во float затем извлечение корня и далее обратно в целое

let answer = solv 1 //answer is 76576500, time 85 ms

• как видно удалось получить ускорение в 17 раз от базовой реализации путем небольшой алгоритмической оптимизации