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

[Lloyd Kvam]

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))
so
         for y in range(2, 7):
could become
	for y in (4,5,6):

One further point.  Along the way, the code deviated from the algorithm.
All of the y's are supposed to result in 1, that is: x % y == 1 for all y
for an x to be printed.

...		for y in (4,5,6):
... 			if x % y != 1:
... 				break
... 		else:	
... 			print x
...
301
721
1141
1561
1981
2401
2821
....

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.

Jeff Shannon wrote:

> Clay Shirky wrote:
> 
>>> for x in range(20000):
>>>      if [x%y for y in range(2, 7)] == 1 and x % 7 == 0:
>>>              print x
>>
>>
>>
>> This is awfully hard to read -- any reason you're trying to cram so much
>> stuff on one line? Is this what you are trying to do?
>>
>> for x in range(20000):
>>     for y in range(2, 7):
>>         if x % y == 1 and x % 7 == 0:
>>             print x
>>             break
>>
>> If so, it will be easy to start altering from there.
> 
> 
> Another thing to consider here -- you've got two loops ('for x...' and 
> 'for y...'), and a compound 'if' statement.  Note that one half of the 
> 'if' statement (and thus the entire test) will be true for only one 
> value in seven of the outer loop, and that the value of the inner loop 
> makes *no* difference to this.  This means that, by splitting into two 
> if statements, we can run the inner loop one-seventh as many times.
> 
> for x in range(20000):
>     if x % 7 == 0:
>         for y in range(2, 7):
>             if x % y == 1:
>                 print x
>                 break
> 
> This will avoid setup and execution of the inner loop for the six out of 
> seven times that x % 7 is *not* equal to zero.  This may be a fairly 
> minor point when you're saving ~17,000 runs of the inner loop, but if 
> your search range grows, it could be *quite* helpful.
> 
> This is a slight variant on the standard optimization method of lifting 
> loop-invariants out of the loop -- in this case, the invariant means 
> that the if statement will never be true.  By lifting that part of the 
> if statement outside of the inner loop, we can optimize away the entire 
> inner loop for certain values of x.  And while some might warn about the 
> dangers of premature optimization (for it *is* dangerous), in this case 
> I think it also results in a clearer, more easily read structure (the 
> opposite of many optimization methods).
> 
> Jeff Shannon
> Technician/Programmer
> Credit International
> 
> 
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
> 

-- 
Lloyd Kvam
Venix Corp.
1 Court Street, Suite 378
Lebanon, NH 03766-1358

voice:	603-443-6155
fax:	801-459-9582