和の二乗と二乗の和の差

30分プログラム、その265。和の二乗と二乗の和の差 via Project Euler - PukiWiki。

最初の10個の自然数について、その和の二乗と、二乗数の和は以下の通り。

1² + 2² + ... + 10² = 385
(1 + 2 + ... + 10)² = 3025

これらの数の差は 3025 - 385 = 2640 となる。

同様にして、最初の100個の自然数について和の二乗と二乗の和の差を求めよ。

たぶん、という式を使うのが正しいのだろう。でも、100程度なら力技でも十分だよね。The Art of Unix Programing(asin:4756149480)にも『まずは力づくで解け』と書いてあるし。

とはいっても、力技だけだと恥かしいので、式変形に基づくコードも書いた。いまひとつ、美しくないけど。

使い方

$ python problem6.py
25164150

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# problem6.py -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/03/18 21:37:41
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

def blut_force(n):
    xs = range(n+1)
    a = sum(xs)**2
    b = sum(map(lambda x: x*x,xs))
    return a - b

def rotate(xs):
    return xs[1:] + [ xs[0] ]

def smart(n):
    def loop(n,xs):
        if xs == []:
            return n
        else:
            x = xs[0]
            xss = xs[1:]
            return loop(n+2*x*sum(xss),xss)
    return loop(0,range(1,n+1))
    
print smart(100)

参考

• 過去の30分プログラム
• Problem6 - Project Euler