幸運数

30分プログラム、その173。幸運数なるものを求めてみる。

求め方は、

• 自然数の数列Lを用意する
• Lから偶数を削除する
• 2*L[1]番目の数字を削除する
• 2*L[2]番目の数字を削除する
• ...
• 2*L[n]番目の数字を削除する

エラトステネスのふるいに似ているけれど、先頭から何番目かを元に削除するという部分が異なる。

使い方

>>> print sieve(range(1,11))
[1, 3, 7, 9]

ソースコード

コードは短かいけれど、えらい苦労した。

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# lucky.py - lucky number
#
# Copyright(C) 2007 by mzp
# Author: MIZUNO Hiroki <hiroki1124@gmail.com> 
# http://mzp.sakura.ne.jp/
#
# Timestamp: 2007/11/04 08:48:01
#
# This program is free software; you can redistribute it and/or
# modify it under the same terms as Python itself.
#

# l = [1,2,3,4,...]
def sieve(l,index=0):
    if len(l) <= index:
	return l
    else:
	top = 2 if l[index] == 1 else l[index]
	# top*n番目の数を削除する
	xs = [x for (x,i) in zip(l,range(1,len(l)+1)) if i % top != 0]
	return sieve(xs,index+1)

print sieve(range(1,100))

参考

• 過去の30分プログラム
• 幸運数 - Wikipedia