Longest Sequence Of Consecutive Odd Integers

October 20, 2015

The longest sequence is the one with the smallest starting point, so we will start from 1 and work our way up using the following algorithm:

(define (lscsi1 target)
  (let loop ((lo 1) (hi 1) (sum 1))
    ; (for-each display `(,lo " " ,hi " " ,sum #\newline))
    (cond ((< target hi) (values 0 0 0))
          ((< sum target) (loop lo (+ hi 2) (+ sum hi 2)))
          ((< target sum) (loop (+ lo 2) hi (- sum lo)))
          (else (values lo hi (+ (/ (- hi lo) 2) 1))))))

>pre>> (lscsi1 160701)
21
801
391

If the current sum is too low, we increase hi. If the current sum is too high, we increase lo. The sum quickly increases to a value slightly larger than the target, then lo and hi dance until the target is reached.

An alternative given at http://stackoverflow.com/a/33113763/448810 uses some math. The sum of a sequence of n odd integers with average (midpoint) m is n × m, and the first and last numbers in the sequence are mn + 1 and m + n − 1; further, both n and m must have the same even/odd parity. If you start at 1, the sum of the sequence is m × n = (first + n − 1) × n = n × n, so the longest sequence for any target is the square root of the target. Thus, we search for n starting from the square root and working downward until m is an integer and the same parity as n:

(define (lscsi2 target)
  (let loop ((n (isqrt target)))
    (let ((m (quotient target n)))
      (cond ((positive? (modulo target n))
              (loop (- n 1)))
            ((= (modulo n 2) (modulo m 2))
              (values (- m n -1) (+ m n -1) n))
            (else (loop (- n 1)))))))
> (lscsi2 160701)
21
801
391

We used isqrt from the Standard Prelude. You can run the program at http://ideone.com/d7nDRV, which also shows a good example of the dance of lscis1.

Pages: 1 2

6 Responses to “Longest Sequence Of Consecutive Odd Integers”

  1. Francesco said

    Not the haskellest/most efficient implementation but…

    g n = f n [] (enumFromThenTo 1 3 n) []
        where f n e []     r = r
              f n e (a:as) r | sum e <  n          = f n (e ++ [a]) as     r
                             | sum e >  n          = f n (tail e)   (a:as) r
                             | length e > length r = f n (tail e)   (a:as) e
                             | otherwise           = f n (tail e)   (a:as) r
    
  2. Paul said

    Two solutions in Python. The functions powerset is from the itertools documentation, is_prime and rho_factors are from the Primes Essay (ProgrammingPraxis). isqrt is the integer square root.

    from operator import mul
    from functools import reduce
    
    NO_SOLUTION = (0,0,0)
    
    def solve(n):
        if n % 4 == 2:
            return NO_SOLUTION
        lo, hi, s = 1, 1, 1
        it = 0
        while lo <= n:
            if s < n:
                hi += 2
                s += hi
            elif s > n:
                s -= lo
                lo += 2
            else:
                break
        else:
            return NO_SOLUTION
        nrterms = (hi - lo) // 2 + 1
        return lo, hi, nrterms
    
    def solve2(n):
        """ The number of terms is equal to the highest divisor D of n, that
               is lower than the square root of n.
            The midpoint of the range is n // D
            If n is even both the number of terms and the midpoint should be even.
            If n is even: remove  a factor 4 and multiply the highest divisor by 2,
               to make sure that the number of terms and the midpoint are even.
            There is no solution if n = 2  mod 4 (as there is only one factor 2)
        """
        if n % 4 == 2:
            return NO_SOLUTION
        if is_prime(n):
            return n, n, 1
        m, fac = (n // 4, 2) if n % 2 == 0 else (n, 1)
        divisors = set(reduce(mul, arr, 1) for arr in powerset(rho_factors(m)))
        divisors = sorted((d for d in divisors if d <= isqrt(m)), reverse=True)
        nrterms = divisors[0] * fac
        mid = n // nrterms
        return mid - nrterms + 1, mid + nrterms - 1, nrterms
    
  3. Mike said

    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.

    from math import sqrt
    
    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
    

    N.B.: 53569 is the 26785th odd number and 53565 is the 26783rd odd number.

    26785**2 – (26783 – 1)**2 = 717436225 – 717275524 = 160701

  4. matthew said

    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
    
  5. fisherro said

    A quick & dirty version in C++. (Although, except for iostreams, it is a C version as well.)

    #include <iostream>
    
    //Longest sequence of consecutive odd integers
    void lsqcoi(int target)
    {
        int longest_start = 0;
        int longest_end = 0;
        int longest_count = 0;
        for (int start = 1; start <= target; start += 2) {
            //We could bail if longest_count > ((target - start) / 2).
            int total = start;
            int count = 1;
            int next = start;
            while (true) {
                if (total == target) {
                    if (count > longest_count) {
                        longest_start = start;
                        longest_end = next;
                        longest_count = count;
                    }
                }
                if (total >= target) break;
                next += 2;
                ++count;
                total += next;
            }
        }
        if (0 == longest_count) {
            std::cout << "Found no sequence of odd integers that sum to " <<
                target << ".\n";
        } else if (longest_start == longest_end) {
            std::cout << "The longest count of odd integers that sum to " <<
                target << " is itself!\n";
        } else {
            std::cout << "The " << longest_count << " odd integers from " <<
                longest_start << " to " << longest_end << " is the longest "
                "sequence of consecutive odd integers that sum to " << target <<
                ".\n";
        }
    }
    
    int main()
    {
        lsqcoi(1);
        lsqcoi(2);
        lsqcoi(4);
        lsqcoi(160701);
    }
    
  6. fl84sg said

    a production of my pencil and keyboard, supported by a bit of mathematics

    #include <stdio.h>
    #include <math.h>
     
    void longest_streak(int num) { //a function which prints out the interval of solution
            int start, count;
            count = sqrt(num); //the largest count of numbers to be summed is less than square root of num  
     
            while(count > 0 && (num % (--count + 1) != 0 || (num / (count + 1) - count) % 2 == 0) );  
            //count can't be less than 1 the loop continues unless a divisor of num is found which results into an odd starting number
           
            start = num / (count + 1) - count;
            printf("%d equates sum of odd integers from %d to %d\n", num, start, start + 2 * count);
    }
     
    void main() {
            longest_streak(2); //it is obvious that 2 and any other prime number cannot be written as sum of odd integers
            longest_streak(6); //six tends to be an exception and i don't know why, if you know just let me know
            longest_streak(160701);
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: