Longest Sequence Of Consecutive Odd Integers | Programming Praxis

Longest Sequence Of Consecutive Odd Integers | Programming Praxis
Today's exercise is to find the longest sequence of consecutive odd integers that add to a given sum. For instance, given the target 160701, the three consecutive odd integers 53565, 53567 and 53569 sum to 160701, but the 391 consecutive odd integers from 21 to 801 also sum to 160701, and are the longest sequence of consecutive odd integers to do so, so they are the correct answer.

The sum of the first k odd numbers is k*k. Therefore, the sum of consecutive odd numbers is the difference between two perfect squares. For example, 160701 = 160801 – 100 = 401*401 – 10*10 = sum from 11th odd number to the 401st odd number (note: the sum of the first 10 odd numbers are subtracted, so the 11th odd number is the first one in the sequence of consecutive odd numbers).

If the search starts from zero, then the first sequence found that sums to n is necessarily the longest, because adding another term at the high end will require subtracting at least one term from the small end.

def findsumofodd(n):

    wanted = set()

    k, k2 = 0, 0

    limit = n//2 + 1

    while k <= limit:

        if k2 in wanted:

            j = int(sqrt(k2 - n)) + 1

            return 2*j - 1, 2*k - 1

 

        wanted.add(n + k2)

         

        k2 += 2*k + 1

        k += 1

A couple more Python solutions, the first moves the starting position b up from 0, maintaining end position a with sum s such that s >= n (so it’s quite like Paul’s first solution). The second is based on Mike’s insight that we are after a factorization of n of the form (a+b)(a-b) and is basically Fermat’s factorization algorithm (it could be improved with a better check for t being an exact square):

def isqrt(n):

    if n == 0: return 0

    x = n

    while True:

        y = (x + n//x)//2

        if (y >= x): return x

        x = y

 

def solve0(n):

    if n%4 == 2: return None

    a,b = isqrt(n), 0

    if a*a < n: a += 1

    s = a*a # sequence sum: n <= s

    while True:

        if s == n: return (b+1,a)

        s -= 2*b+1

        b += 1

        while s < n:

            s += 2*a+1;

            a += 1

 

def solve1(n):

    if n%4 == 2: return None

    a = isqrt(n)

    if a*a < n: a += 1

    while True:

        t = a*a - n

        b = isqrt(t)

        if b*b == t: return (b+1,a)

        a += 1

Read full article from Longest Sequence Of Consecutive Odd Integers | Programming Praxis