[Tutor] Re: Creatively solving math problems -----help

[Andrei]

Lloyd Kvam wrote:

> One further optimization:
> x % 6 == 1  implies that x % 3 ==1 and x % 2 == 1 (the factors of the 
> modulus
> must also result in 1 (asserted without proof))

Seems perfectly OK to me.

> so
>         for y in range(2, 7):
> could become
>     for y in (4,5,6):
> 
> Danny's one liner:
 > [ x for x in range(20000) if [x%i for i in range(2,8)]==[1]*5+[0] ]
 > shows the mod values that we want.  [1]*5+[0] might be easier to read as
 > [1,1,1,1,1,0]
 > though counting 1's isn't great either.

Actually, it was my oneliner. [1]*5 was indeed to avoid typing the wrong number 
of 1's - and it's marginally shorter too! Danny's solution is far more excentric 
- and certainly no oneliner :). Nevertheless, I think a solution with explicit 
loops is preferred in this sutuation. Funny how the whole discussion turned into 
an optimization when all Conrad needed was the % operator.

Anyway, it's possible to save a bit of time in the list comprehension too using 
the suggestions provided (not checking 2&3 because 6 already checks them and 
only evaluating if x%7==0) *wink*. I've done some tests and it seems there's a 
way to add to the spared time: replace the range() and [1]*4 with their 
hand-written counterparts. Time for the benchmarks:

 >>> import timeit as t
 >>> a = t.Timer("[ x for x in range(20000) if [x%i for i in 
range(2,8)]==[1]*5+[0] ]")
 >>> b = t.Timer("[ x for x in range(20000) if not x%7 if [x%i for i in 
(4,5,6)]==[1,1,1] ]")
 >>> c = t.Timer("[ x for x in xrange(20000) if not x%7 if not x%6-1 if not 
x%5-1 if not x%4-1 ]")
 >>> [ min(X.repeat(30,1)) for X in [a,b,c] ]
[0.17663669544572258, 0.022738923522410914, 0.0077345025697468373]
    ^-- best result for a      ^-- best for b      ^-- best for c (lower=better)

Just to be on the safe side, test if all lists are the same (up to 100k instead 
of 20k):
 >>> [ x for x in range(100000) if [x%i for i in range(2,8)]==[1]*5+[0] ]==[ x 
for x in range(100000) if not x%7 if [x%i for i in (4,5,6)]==[1,1,1] ]==[ x for 
x in xrange(100000) if not x%7 if not x%6-1 if not x%5-1 if not x%4-1 ]
True

And the winner is, at nearly 23 times the speed of the original oneliner...

[ x for x in xrange(20000) if not x%7 if not x%6-1 if not x%5-1 if not x%4-1 ]

Well, that was fun.


Andrei

=====
Mail address in header catches spam. Real contact info (decode with rot13):
cebwrpg5 at bcrenznvy.pbz. Fcnz-serr! Cyrnfr qb abg hfr va choyvp cbfgf. V ernq gur 
yvfg, fb gurer'f ab arrq gb PP.