Python solution of Project Euler, problem 6

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

I don't have much to say about this solution. I found this one pretty trivial to implement with Python.  I'm posting my solution just to keep everything in sequence. :)  Basically, the question is asking to find x, where

x = (1 + 2 + .. + 100)² - (1² + 1² + ... + 100²)

def main():
  N = 100
  sum1, sum2 = 0, 0
  for i in range(1, N + 1):
    sum1 += i
    sum2 += pow(i,2)
  return pow(sum1,2) - sum2

if '__main__' == __name__:
  print main()

Edit: the iterative solution was trivial, but the mathematical solution is much more efficient and clever:

Mathematical Solution (credit to Lov Loothra)

N = 100
s1 = N*(N + 1)/2 # sum of first N numbers
s2 = N*(N + 1)*(2*N + 1)/6 # sum of first N squares
print s1*s1 - s2

Python solution of Project Euler, problem 5

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I enjoyed working on this problem. It's short, simple, and didn't take very long. I learned nothing new about Python, but I enjoyed it because of the optimizations I realized that brought the execution time to about 0.4 seconds.  The key optimizations are the following:

1. When checking the divisibility of the numbers [1,20], you really only need to check [11,20] as the [2,10] are implicitly checked (for example, if 20 divides n, we know 10, 5, 4, and 2 divide n, if 14 divides n, we know 7 and 2 divide n, and so on).
2. We can increment each value by 380 to significantly reduce the number of numbers tried. Why 380? Well, my first guess was to just increment by 20, since it's the highest number that must be divisible by a value, but then I realized that 19 * 2, 19 * 3, ..., 19 * 19 are never divisible by 20, so we increment by 19 * 20 = 380. Does this have to do with the fact 19 is prime? I'm not sure, can somebody prove it? The difference in performance was huge between my first solution, where I incremented 20, and the current solution (about a 1000% increase).

Python Implementation:

def main():
  val, found = 380, False
  while not found:
    # numbers below 11 do not need to be checked because they are already
    # implicitly checked by the higher numbers; e.g., if 20 divides val, so
    # does 10, same for 18 and 9, 16 and 8, etc.
    found = val % 20 == 0 and val % 19 == 0 and val % 18 == 0 and \
        val % 17 == 0 and val % 16 == 0 and val % 15 == 0 and \
        val % 14 == 0 and val % 13 == 0 and val % 12 == 0 and val % 11 == 0
    if not found:
      val += 380
  return val

if '__main__' == __name__:
  print main()

The fact that Python short circuits the conditional after the first failure is important. It may also be more elegant to put the values [20,11] in a range and iterate them, but the iteration introduces more operation and a part of my goal is to make these solutions as efficient as possible (while also being readable and not using too many bad practices).

PHP POST variables getting truncated? Check suhosin

I worked on an issue lately where input from a textarea was getting truncated before it reached the PHP $_REQUEST or $_POST variables. The solution was simple, but it took me way too long to figure out, so maybe this will help somebody from Google one day. 


The site I had this problem with used php-cgi and nginx to serve requests. The the first things I checked where configurations in php.ini and nginx.conf (and other included nginx config files).

• php.ini  - make sure post_max_size is high enough.  Mine was set to 8M, which seems to be common.
• nginx.conf - client_max_body_size should also be enough.  This parameter is the maximum number of bytes a client can send to the server per request (I don't think this includes a file upload, may be wrong).

My problem was with suhosin.  Since I wasn't the original architect of this system, I knew nothing about this module.  It is described to "protect servers and users from known and unknown flaws in PHP applications and the PHP core".  


The problem was that the suhosin post.max_value_length parameter wasn't high enough.  By, default, it is 65000 (~63 KB).  I added this parameter to in my .ini config with a high-enough value, restarted php-cgi, and all was good.