Как вывести сумму последовательности? python
Как вывести сумму последовательности?
Например, ввод: 12 Последовательность 12=1+2+3+4+5+6+7+8+9+10+11+12, ее сумма должна составить ровно 12 или на одну последовательность выше. В нашем варианте: сумма 12 будет равна 1+2+3+4+5=15
Другими словами: необходимо создать код, который вычисляет сумму последовательных чисел 1 + 2 + 3 + ... до тех пор, пока ее значение не станет хотя бы числом, введенным пользователем.
Ответы (2 шт):
Если брут-форсом, то так:
n, i = int(input()), 0
while sum(range(i)) < n:
i += 1
else:
print(sum(range(i)))
Для реально больших чисел, конечно, можно придумать более эффективный алгоритм, но над этим уже думайте сами.
Сумма арифметической прогрессии от 1 до n равна n(n + 1)/2. Требуется для заданного s отыскать минимальное n: n(n + 1)/2 ≥ s.
n2 + n ≥ 2s — раскрываем скобки.
4n2 + 4n ≥ 8s
(2n)2 + 2(2n) + 1 - 1 ≥ 8s
(2n + 1)2 - 1 ≥ 8s
(2n + 1)2 ≥ 1 + 8s
2n + 1 ≥ √(1 + 8s) — нас интересует только один, положительный, корень из квадрата.
2n + 1 ≥ ⌈√(1 + 8s)⌉ — cлева целое число, значит и выражение справа можно округлить вверх.
2n ≥ ⌈√(1 + 8s)⌉ - 1
n ≥ (⌈√(1 + 8s)⌉ - 1)/2
n ≥ ⌈(⌈√(1 + 8s)⌉ - 1)/2⌉ — cлева целое число, значит и выражение справа можно округлить вверх.
n = ⌈(⌈√(1 + 8s)⌉ - 1)/2⌉ — ищем минимальное n, можно заменить неравенство на равенство.
Нужно вычислить ⌈√n⌉, где n целое. math.isqrt вычисляет ⌊√n⌋ = math.isqrt(n). Там же можно найти совет для округления вверх: ⌈√n⌉ = math.isqrt(n - 1) + 1.
Второе неочевидное место: ⌈n/2⌉, где n целое. Оператор // делит округляя вниз: ⌊n/2⌋ = n // 2. А нам нужно вверх: ⌈n/2⌉ = (n + 1) // 2.
Подставим операции языка программирования в формулу:
n = ⌈(⌈√(1 + 8s)⌉ - 1)/2⌉
n = ⌈(math.isqrt(1 + 8s - 1) + 1 - 1)/2⌉
n = (math.isqrt(1 + 8s - 1) + 1 - 1 + 1) // 2
n = (math.isqrt(8s) + 1) // 2
import math
s = int(input())
n = (math.isqrt(8 * s) + 1) // 2
m = n * (n + 1) // 2
print(m)