Generating a maximal geometric progression of integers I'm working on a program that generates a maximal geometric progression of at least 3 integers when given a number that the greatest value shouldn't exceed.

My current code works, and it's quick(ish) with small numbers, but anything past 100 takes far longer than I'd like, as I need to calculate numbers in ranges from \$10^7\$ to \$10^{20}\$.

If possible, I'd like to eliminate using Threads, as Python's are known for their lackluster performance.

from itertools import izip,islice,tee,takewhile
from threading import Thread
from Queue import Queue

#initialize the queue
g=Queue()

#checks that all values end with `.0`
def int_check(l):
    for i in l:
        if i-int(i)!=0: return False
    return True

#checks if a generated list fits the criteria
def check(obj):
    cpy0,cpy1=tee(obj)
    iter0,iter1=tee(float(x)/y for x,y in izip(cpy0,islice(cpy1,1,None)))
    return all(x==y for x,y in izip(iter0,islice(iter1,1,None))) and len(obj)&gt;2 and int_check(obj)

#thread target
def calc(s,n,q):
    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]&lt;=n:
            t.extend([t[-1]*((0.0+r)/100)])

        if check(t):
            q.put(takewhile(lambda i: i&lt;=n,t))

#starts threads, calculates final value, and manages queue
def geo_prog(n):
    #Queue -&gt; list
    def dump_queue(q):
        q.put('EOQ')
        res=[]
        return (i for i in iter(q.get,'EOQ'))

    for s in xrange(int(n/4),int(n*0.8)+1):
        t=Thread(target=calc,args=(s,n,g))
        t.start()
        t.join()

    return max(map(sum,dump_queue(g)))

#ex usage
print geo_prog(100)


Examples

geo_prog(4) -&gt; 7.0
geo_prog(10) -&gt; 15.0
geo_prog(12) -&gt; 21.0
geo_prog(100) -&gt; 240.0
No threading, please!!

First of all, get rid of the threads all-together. That should speed things up: Python threads are (sort-of) fine when things are blocking on IO, but in this case everything is CPU-based, and that means the GIL (global interpreter lock) makes sure that only one thread is running.

Also, the following code is a bit curious:

for s in xrange(int(n/4),int(n*0.8)+1):
    t=Thread(target=calc,args=(s,n,g))
    t.start()
    t.join()


I know that threading is a bit of a problem anyway here, but I would just like to comment on this specifically: by writing t.join() you are waiting on the thread to finish before starting the next iteration. This gets read of the threading all together, as there will only be two threads alive at a given time: 1 worker thread, and the main thread waiting on the worker to die.

I'd suggest writing it as:

threads = []
for s in iterable:
    t = Thread(...)
    threads.append(t)
    t.start()

for t in threads:
    t.join()


Naming and describing

Ok, with threading out of the way, I'm having a difficult time finding what the application is supposed to do.

It does something with an n, and each worker with an s and an n. What are those? The code could be a lot clearer in this regard.

Anyway, let us clean things up a bit first, and maybe I can find a pattern to help you improve the algorithm.

Performance

Checking for integer-valued lists.

Let's start looking at int_check.

def int_check(l):
    for i in l:
        if i-int(i)!=0: return False
    return True


You're checking if a number is integral by doing a lengthy calculation. Why not just

if i.is_integer(): return False

? Available since Python 2.6. https://docs.python.org/2/library/stdtypes.html#float.is_integer

Also, looping is expensive! Suggestion, use a comprehension together with the all.

def int_check(l):
    return all(i.is_integer() for i in l)


You should also name it better:

def is_integer_list(l):
    return all(i.is_integer() for i in l)


Useless duplication of lists

Let's look at the following code:

def check(obj):
    cpy0,cpy1=tee(obj)
    iter0,iter1=tee(float(x)/y for x,y in izip(cpy0,islice(cpy1,1,None)))
    return all(x==y for x,y in izip(iter0,islice(iter1,1,None))) and len(obj)&gt;2 and int_check(obj)


First of all, let us do some short-circuiting. You're doing a lot of logic to see if it is a nice geometric progression, and after all the hard work, you check some very easy conditions. Turn that around!

def check(obj):
    if len(obj) &lt;= 2 or not int_check(obj):
        return False
    cpy0,cpy1=tee(obj)
    iter0,iter1=tee(float(x)/y for x,y in izip(cpy0,islice(cpy1,1,None)))
    return all(x==y for x,y in izip(iter0,islice(iter1,1,None)))


I'm doubtful of you using tee for this. But I don't see a better builtin for it either. But I see a lot of logic here which I'd like to separate a bit more:

def steps(iterable):  # Needs better name, please help me!
    iterator = iter(iterable)  # Cast iterable to iterator.
    cur = next(iterator)
    for val in iterator:
        yield cur, val
        cur = val


A quick test to see that it does what we want.

&gt;&gt;&gt; list(steps(range(10)))
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]


Using that, we get

def check(obj):
    if len(obj) &lt;= 2 or not int_check(obj):
        return False
    ratios = (float(x)/y for x, y in steps(obj))
    return all(x == y for x, y in steps(ratios))


Don't know if it's faster, but at least it is more readable! And I expect faster. But the main gain might be in the next section

The main loop

Your code was written as

def calc(s,n,q):
    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]&lt;=n:
            t.extend([t[-1]*((0.0+r)/100)])

        if check(t):
            q.put(takewhile(lambda i: i&lt;=n,t))


Since I want to get rid of the threading, I'll assume q is a list instead of a queue.

def calc(s,n,q):
    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]&lt;=n:
            t.extend([t[-1]*((0.0+r)/100)])

        if check(t):
            q.append(takewhile(lambda i: i&lt;=n,t))


(In reality I'd rather yield the results instead of adding to a queue. Anyhow, I'm shelving that for now)

takewhile vs slicing.

In the q.put you write takewhile. By the while loop above, you already know that will be all but the last value.

So, write

q.append(t[:-1])


Or, even

t.pop()
q.append(t)


That should be faster, because now the lambda i: i &lt;= n doesn't have to be executed anymore.

Useless recalculation

Having written the above loop now as

def calc(s,n,q):
    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]&lt;=n:
            t.extend([t[-1]*((0.0+r)/100)])

        if check(t):
            t.pop()
            q.append(t)


We can turn our focus to the expression t.extend(...) above:

    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]&lt;=n:
            t.extend([t[-1]*((0.0+r)/100)])


Now in each iteration of the while loop, (0.0+r)/100 gets recalculated. Why not

    for r in xrange(125, n*100+1,5):
        r_ = float(r) / 100
        t=[s]
        while t[-1]&lt;=n:
            t.extend([t[-1]*r_)


Incorrect algorithm

The worst part, I think, is that your code works by trying different ratios, and will miss some geometric sequences.

For instance, the sequence

81, 90, 100  # r == 100.0 / 90.0 == 90.0 / 81.0 (approx 1.1111111)


While your code will only try 1.25, 1.30, 1.35, ... .

Now, maybe there is some high-level mathematical proof that the solution will always involve a ratio which can be expressed as (125 + 5*k)/100, but I don't think so.

I would suggest turning the problem up-side-down. The following is an O(n^2 * log(n)) suggestion (estimated, but I think correct. Maybe even O(n^2)).

for x1 in xrange(1, n):
    for x2 in xrange(x1, n):
        # Using that
        #     x1 == a
        #     x2 == a * r
        # we get that
        #     r == x2 / x1
        ratio = float(x2) / x1
        # Continue as before, starting from t = [x1, x2]


Another point of incorrectness

In check, you check that the length is > 2, but then you filter on &lt;=n. This should be the other way around.

A tiny suggestion.

Floating point arithmetic is challenging for problems like these. Maybe look into the fractions module?

from fractions import Fraction

...
ratio = Fraction(x2, x1)
...


Now, Fraction does not have an is_integer, but you can do the following:

&gt;&gt;&gt; Fraction(5, 1).denominator == 1
True


Hope that all helps.

Corner cases

As an addendum, here are some cases your code flagged incorrectly:

&gt;&gt;&gt; geom_prog(16)
28.0  # 4 + 8 + 16


but it should be at least 37: 9 + 12 + 16.

&gt;&gt;&gt; geom_prog(100)
244.0  # 64 + 80 + 100


but it should be at least 271: 81 + 90 + 100 (maybe even more, but doubt it).