Как найти минимальный первый член арифметической прогрессии?

Question

Задача: найти минимальный первый член арифметической прогрессии (т.е. минимально возможный. Если может быть 1 и 3, то ответ - 1) по сумме всех её членов и разности=1, не используя вложенные циклы.

Насколько я понял, у меня математика хромает при нахождении количества членов (n)

код на питоне:

import math

S = int(input())



# сначала я ищу количество членов(n).
# S = (2a1 + d(n - 1)) / 2 * n =>
# => 2S = (2a1 + (n - 1)) * n => 
# => 0 = (2a1 + (n - 1)) * n - 2S => 
# => 0 = ((2a1 * n) - n) + n ** 2 - 2S => 
# => 0 = (2a1 - 1) * n + n ** 2 - 2S
# имеем квадратное уравнение с корнем n

# каждая итерация - квадратное уравнение: 0 = (2a1 - 1) * n + n ** 2 - 2S
# решив его я имею n, S и предполагаемый a1.
# после чего я могу посчитать, прав я в предположении на счёт a1 или нет.
# если всё сходится, прерываю цикл
for a1 in range(1, S):
    D = (2 * a1 - 1) ** 2 - (4 * (-(2 * S)))
    if D > 0:
        n = int(-(2 * a1 - 1) + math.sqrt(D) / 2.0)
        print(D, n, a_1)
        if float((2 * a1 + n - 1) / 2 * n) == float(S):
            break
print(a1)

Answer 1

Для нецелочисленной прогрессии решения нет (оно равно минус бесконечности).

При условии целочисленности прогрессии:

s = int(input())
if s <= 0: print(s)
else: print(-s+1)

На случай, если прогрессия не только целочисленна, но и неотрицательна (и такова же и ее сумма, понятно)...

Первый член прогрессии a связан с суммой S и числом членов n формулой

Очевидно, что чтобы a было целым, надо либо чтобы S делилось нацело на n и n было нечетным, либо n четно, но тогда 2S должно делиться на n.

Так что надо просто поискать соответствующие n в диапазоне [1,2S]. Проще всего — переборно, единственным циклом (условие же — без вложенных :))

Т.е. что-то типа (сделано топорно из-за слабого знания питона, по сути перевод с С плюс отсутствие оптимизации (тупой перебор). Кто умеет — можете смело исправлять код):

def a(S: int):
    m: int
    m = S
    for n in range(2,2*S+1):
        q = 2*S-n*(n-1)
        if q < 0: break
        if q%(2*n) == 0:
            q = q / (2*n)
            if q < m: m = q
    return m


s = int(input())
print(int(a(s)))

Answer 2

формула для прикидки верхнего значения числа n

Умножаем обе части на 2 и переносим слагаемое n*2a1 со знаком минус влево.
Получаем
2*Sn-n*2a1=d*n(n-1)
По условию d=1
2*Sn-n*2a1=n*(n-1)
Теперь просто видим, что при любом значении a1 от нуля до предела 2Sn будет
больше или равно n*(n-1) - равно только при a1=0
2*Sn>=n*(n-1) 
из этого утверждения следует более слабое утверждение о том, что 
2*Sn>=(n-1)(n-1), так как n>n-1,
извлекаем корень из обоих частей - получаем
sqrt(2*Sn)>=n-1,
переносим влево единичку
Получаем доказанное утверждение:
sqrt(2*Sn)+1>=n

БЛОГ НА HUSL

Как найти минимальный первый член арифметической прогрессии?

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