Как улучшить код по суммированию натуральных чисел?

Question

Задача: Дано целое положительное число N. Выведите максимально возможную сумму последовательных целых чисел от 1 до n так, чтобы эта сумма была строго меньше заданного значения N. Мой код:

n = int(input())
def get_num(n):

    sum = 0
    for i in range(1, n + 1):
        sum += i
        if sum >= n:
            print(sum - i)
            break
    return sum
get_num(n)

Как можно улучшить? Задача решена конечно, но криво. Не могу понять как правильно прописать момент с суммой, где она меньше числа n. Если убрать print(sum - i), то вывод уже идет некорректный.

Answer 1

Например, исправить можно так:

def get_num(n):
    summ = 0
    i = 1
    while summ + i < n:
        summ += i
        i +=1
    return summ

А по уму вместо перебора нужно использовать формулу суммы арифметической прогрессии и решить квадратное неравенство

import math
def get_num2(n):
    x = math.ceil((math.sqrt(1 + 8 * n) - 1)/2) - 1
    return x*(x+1)//2

Answer 2

Если приводить в порядок ваш код, то надо поправить сумму перед возвращением:

def get_num(n):
    s = 0
    for i in range(1, n + 1):
        s += i
        if s >= n:
            s -= i
            break
    return s


print(get_num(int(input())))

for в решении смотрится странно. Без него будет проще:

def get_num(n):
    t = 0  # next term in sum
    s = 0  # current sum
    while s < n:
        t += 1
        s += t
    return s - t  # correct last term

Последовательное сложение не наш способ. Решим задачу аналитически.


∑_i=1ⁿi < N	исходное неравенство
∑_i=1ⁿi ≤ N - 1	замена неравенства на нестрогое
n(n + 1)/2 ≤ N - 1	сумма арифметической прогрессии
4n(n + 1) ≤ 8N - 8
4n² + 4n + 1 - 1 ≤ 8N - 8
(2n + 1)² ≤ 8N - 7
2n + 1 ≤ √(8N - 7)
2n + 1 ≤ ⌊√(8N - 7)⌋	левая часть целая, берём из правой целую часть
n ≤ (⌊√(8N - 7)⌋ - 1) / 2
n ≤ ⌊(⌊√(8N - 7)⌋ - 1) / 2⌋	левая часть целая, берём из правой целую часть

Целую часть корня ⌊√⌋ извлекает math.isqrt. Деление в конце ⌊... / 2⌋ целочисленное - //.

Можно считать:

def get_num(n):
    m = (math.isqrt(8 * n - 7) - 1) // 2
    return m * (m + 1) // 2

БЛОГ НА HUSL

Как улучшить код по суммированию натуральных чисел?

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