import math

countup = dict()
limit = 20001

for newkey in range(0, limit):
  countup[newkey] = 0

for root1 in range(0, limit):
  for root2 in range(root1, limit):
    newsum = root1*root1 + root2*root2
    if newsum > limit - 1:
      break
    countup[newsum] += 1

del countup[0]
total = 0
count = 0
for k in countup:
  if countup[k] > 0:
    total += countup[k]
    count += 1
  #if countup[k] > 2:
  #  print k, countup[k]

print 'total ' + str(total) + ' in ' + str(count) + ' gives mean ' + str(1.0*total/count)

Timeout