Stefan Behnel wrote:
> Andre Alexander Bell, 18.06.2010 11:23:
>> On 06/16/2010 12:47 PM, Lie Ryan wrote:
>>> Probably bending the rules a little bit:
>>>
>>>>>> sum(x**2 - 8*x - 20 for x in range(1, 2010, 5))
>>> 536926141
>>
>> Bending them even further, the sum of the squares from 1 to N is given by
>>
>> (1) N*(N+1)*(2*N+1)/6.
>>
>> The given problem can be divided into five sums of every fifth square
>> starting from 1,2,3,4,5 respectively. This is given by
>>
>> (2) S(a,k) = sum_{i=1}^k (5*i-4+a)^2
>>
>> for a in range(5) and we are finally interested in
>>
>> (3) S(k) = S(0,k) + S(1,k) + S(2,k) - S(3,k) - S(4,k)
>>
>> Substituting (2) and (1) in (3) gives (in python code)
>>
>>>>> S = lambda k: (50*k**3 - 165*k**2 - 47*k) / 6
>>>>> S(2010/5)
>> 536926141
>>
>> However, this only works for full cycles of (1,1,1,-1,-1) and you would
>> have to add/subtract the modulus parts yourself. (e.g. if you are
>> interested in your sum from 1..2011...
>
> The thing is, if you can't do the math in the time that your processor
> needs to run the brute force loop, it's often not worth doing the math at
> all.
By that standard using Cython for the problem doesn't pay either;)
Peter
--
http://mail.python.org/mailman/listinfo/python-list
