Problem23 (1) -力づくで挫折-

30分プログラム、その289。Problem23 via Project Euler。

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28であるので, 28は完全数である.
真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.
12は, 1+2+3+4+6=16となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.
2つの過剰数の和で書き表せない正の整数の総和を求めよ.

そのまま素直に実装したら、とても計算が完了しなかった。まあ、予想通り。

使い方

$ python problem23.py
^CTraceback (most recent call last):
  File "problem23.py", line 36, in <module>
    print main(28123)
  File "problem23.py", line 32, in main
    xrange(1,n))
  File "problem23.py", line 31, in <lambda>
    combination_list     = filter(lambda x: not is_combination(x,abudant_list),
  File "problem23.py", line 26, in is_combination
    return True
KeyboardInterrupt

ソースコード

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

def divisor(n):
    return filter(lambda x: n % x == 0,xrange(1,n))

def is_abundant(n):
    return sum(divisor(n)) > n

def is_combination(n,l):
    """is n expressed by some combination of l"""
    for x in l:
        if n - x in l:
            return True
    return False

def main(n):
    abudant_list = filter(is_abundant,xrange(12,n))
    combination_list     = filter(lambda x: not is_combination(x,abudant_list),
                                  xrange(1,n))
    return sum(combination_list)

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

参考

• 過去の30分プログラム
• Problem 23 - PukiWiki