小练习：20160620 算出所有不能写成两个过剩数之和的正整数之和

冬雪雪冬 · 发表于 2016-6-19 20:54:15

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2016-6-27 10:14 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题，并且你每做对一题，就可以下载到参考答案的pdf文件，看看你的实现方法与参考答案有什么不同，以利于迅速提高自己的水平。

登录/注册后可看大图

好了言归正传，我们开始做小练习。

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即6.27 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。

题目：

如果一个数的所有真因子之和等于这个数，那么这个数被称为完全数。例如，28 的所有真因子之和为 1 + 2 + 4 + 7 + 14 = 28，所以 28 是一个完全数。

如果一个数的所有真因子之和小于这个数，称其为不足数，如果大于这个数，称其为过剩数。

12 是最小的过剩数，1 + 2 + 3 + 4 + 6 = 16。因此最小的能够写成两个过剩数之和的数字是 24。经过分析，可以证明所有大于 28123 的数字都可以被写成两个过剩数之和。但是这个上界并不能被进一步缩小，即使我们知道最大的不能表示为两个过剩数之和的数字要比这个上界小。

找出所有不能表示为两个过剩数之和的正整数之和。

奖励：
对所有完成程序并得出正确答案的将给予加分奖励，优秀的将额外加分。
在完成一批题目后，将根据每期的完成情况总评评出最佳，会有神秘大奖。

lizuolong · 发表于 2016-6-20 00:04:37

这个是新的题目吗，上期好像暧昧公布呢

caobynk · 发表于 2016-6-20 08:26:57

def getdivisor(n):
from math import sqrt
result = 1
for i in range(2, int(sqrt(n)+1)):
if n%i == 0: result = result + i +n/i
if n%sqrt(n) == 0 : result -= sqrt(n)
return result
def getabundant(n):
result = [12]
for i in range(13, n):
if getdivisor(i)>i:
result.append(i)
return result
if __name__ == '__main__':
abundant = getabundant(28112)
result = list(range(1, 28125))
k = 0
a = 2*abundant[k]
while (a <= 28124):
for i in range(k, len(abundant)):
if (abundant[k]+abundant[i])<=28124 :
result[abundant[k]+abundant[i]-1] = 0
else:
break
k += 1
a = 2*abundant[k]
result = set(result)
print(sum(result))

复制代码

DingRan · 发表于 2016-6-20 11:22:49

严重支持

def guosheng(x):
s = 0
for i in range(1, int(x**0.5)+1):
if x % i == 0:
s += i
a = x / i
if a != i:
s += a
if (s - x) > x:
return True
else:
return False
dic = [None]
for i in range(1, 28123):
dic.append(guosheng(i))
def check(x):
for i in range(1, int(x/2)+1):
if dic[i]:
if dic[x-i]:
return True
return False
s = 0
for num in range(1, 28124):
if not check(num):
s += num
print(s)

复制代码

运行结果

>>>
4179871
>>>

复制代码

lizuolong · 发表于 2016-6-20 12:44:37

#欧拉23
import time
times=time.time()
def gsc_all(n):
result = set()
for single in range(12,n+1):
singles = {1}
for i in range(2,int(single**.5)+1):
if not single % i:
singles.update({i, single // i})
if sum(singles) > single :
result.update({single})
singles = singles & {1}
result_temp =set()
result=sorted(result) #这个集合排序找了很久，百度都是list.sort排序
#这里时间最多，已经找不到优化了
for i in result:
for y in result:
z=i+y
if z<n+1:
if z not in result_temp:
result_temp.update({i+y})
else:
break
return (n*(n+1)/2 -sum(result_temp))
print(gsc_all(28123))
print(time.time()-times)

复制代码

人太少了，我昨天回帖到现在才2个人回帖

老忘 · 发表于 2016-6-20 15:50:58

#-*- coding: UTF-8 -*-
import time
start = time.clock()
def aa(num):#借助bhsx同学的真因子和的算法
count = num
dict = {}
get = dict.get
for i in range(2, count // 2 + 1):
for j in range(i, count // i - 1):
sum = i * j
dict[sum] = get(sum, 1) + i + (j if j != i else 0)
return dict
input_num=28123
list_1=[]#初始化过剩数列表
dict_1={}#初始化二个过剩数之和为key的字典
for k,v in aa(input_num).items():#判断过剩数并存入列表list_1
if k<v:
list_1.append(k)
for i in range(0,len(list_1)):#二个过剩数求和
for j in range(0,i+1):
z=list_1[i]+list_1[j]
if z<=input_num:#过剩数和小于input_num，则将和作为key存入dict_1
dict_1[z]=1
else:#过剩数和大于等于input_num则跳出
break
print(input_num*(input_num+1)/2-sum(dict_1.keys()))
end = time.clock()
print ("read: %f s" % (end - start))

复制代码

holdme · 发表于 2016-6-20 16:45:48

本帖最后由 holdme 于 2016-6-22 15:23 编辑

# -*- coding: utf-8 -*-
"""
Created on Thu Jun 16 15:58:04 2016
@author: Yohino_Lab_D4
"""
from math import sqrt, floor
from itertools import combinations_with_replacement
import time
start = time.clock()
def divisors_sum(n):
"""求n所有真因子的和"""
if(n == 1):
return (0)
divs = set([1])
r = floor(sqrt(n))
if(r**2 == n):
divs.add(r)
f = 2
step = 1
if(n & 1 == 1):
f = 3
step = 2
while(f <= r):
if(n % f == 0):
divs.add(int(n/f))
divs.add(int(f))
f = f + step
return sum(divs)
def judge_abund(n):
'''判断n是否为过剩数'''
if divisors_sum(n) > n:
return True
else:
return False
def nonabun_sums(limit = 28123):
abund_list = [i for i in range(limit) if judge_abund(i)]
abund_sum_list = set(x+y for x,y in combinations_with_replacement(abund_list,2))
return sum(i for i in range(limit) if i not in abund_sum_list)
print('所有不能表示为两个过剩数之和的正整数之和为：%s'%str(nonabun_sums()))
print('用时%s秒'%str(time.clock()-start))

复制代码

结果：

所有不能表示为两个过剩数之和的正整数之和为：4178876
用时3.2573017684944183秒

复制代码

Spicebush · 发表于 2016-6-20 17:31:36

本帖最后由 Spicebush 于 2016-6-24 15:07 编辑

#答案为4179871
import math
def d(n):
if n>1:
factor={1}
half=math.sqrt(n)
for i in range(2,int(math.sqrt(n))+1):
if n%i==0:
factor.add(i)
factor.add(n//i)
return sum(factor)
else:
return 0
#以上摘自小火木之前在欧拉计划中编的程序,学习了，谢谢！
l_gs = [x for x in range(12, 28112) if d(x)>x]
fw = range(len(l_gs))
l = {0}
n = 0
SUM = sum(range(1,28124))
for j in fw:
if l_gs[j] > 14061:
break
else:
for k in fw[n:]:
s = l_gs[j] + l_gs[k]
if s > 28123:
break
else:
if s not in l:
SUM -= s
l.add(s)
n += 1
print(SUM)

复制代码

leozyre · 发表于 2016-6-21 08:29:21

python2.7

import math
def dec(num):
sum = 1
for i in range(2,int(math.sqrt(num))+1):
if num%i == 0:
sum += i
if num/i != i:
sum += num/i
if sum > num:
return num
alist = []
flag = 0
asum = 0
blist = []
for i in range(11,28123):
if dec(i):
alist.append(i)
for bnum in alist[::-1]:
for cnum in alist:
if bnum > cnum:
dnum = bnum - cnum
if dnum in alist:
blist.append(bnum)
break
else :
break
for i in range(1,28123):
if i not in blist:
asum += i
print asum

复制代码

答案是297576966

mather · 发表于 2016-6-21 17:08:19

本帖最后由 mather 于 2016-6-21 17:09 编辑

over_nums = []
cano_nums = []
for n in range(1,28124):
is_break = False
for i in over_nums:
if n-i not in over_nums:
continue
else:
is_break = True
break
if not is_break:
cano_nums.append(n)
factor = [1]
nums = n
upper = n
for i in range(2,nums+1):
if i < upper:
if nums%i == 0:
if i != nums/i:
factor = factor + [i,int(nums/i)]
else:
factor.append(i)
upper = i if i>=nums/i else nums/i
else:
break
if sum(factor)>n:
over_nums.append(n)
print(sum(cano_nums))

复制代码

计算时间有点长~~！后面再看能不能优化~
结果：4179871

小火木 · 发表于 2016-6-21 23:15:10

import math
def d(n):
if n>1:
factor={1}
half=math.sqrt(n)
for i in range(2,int(math.sqrt (n))+1):
if n%i==0:
factor.add(i)
factor.add(n//i)
return sum(factor)
else:
return 0
data=[n for n in range(2,28123) if d(n)>n]
temp=[i for i in range(1,28123)]
for i in data:
for j in data[data.index(i): ]:
try:
temp[i+j-1]=0
except:
break
print('不能表示为过剩数之和的正整数之和为：%d'%sum(temp))

复制代码

昨、夜星辰 · 发表于 2016-6-22 13:45:54

适用于Python2：

def is_abundant_number(number):
factor_list = [i for i in range(1, int(number ** 0.5) + 1) if not number % i]
factor_list.extend([number / i for i in factor_list if i < number ** 0.5])
return True if sum(factor_list) > 2 * number else False
if __name__ == '__main__':
m = 20161
abundant_number_list = [i for i in range(12, m + 1) if is_abundant_number(i)]
set1 = set(range(1, m + 1))
set2 = set()
length = len(abundant_number_list)
for x in range(length):
if abundant_number_list[x] > m / 2:
break
for y in range(x, length):
s = abundant_number_list[x] + abundant_number_list[y]
if s > m:
break
set2.add(s)
print sum(set1 - set2)

复制代码

运行结果与时间：

space_ · 发表于 2016-6-22 20:28:30

import time
start= time.clock()
def isAbundant(num):
sum = 0
for i in range(1,num//2+1):
if(num % i ==0):
sum += i
if(sum > num):
return True
return False
sum = 0
arr = []
sumArr = []
for i in range(1,28123):
if(isAbundant(i)):
arr.append(i)
for i in range(len(arr)) :
for j in range(i,len(arr)) :
if (arr[i]+arr[j]) < 28123 :
sumArr.append(arr[i] + arr[j])
sumArr = set(sumArr)
for i in range(1,28123):
if(i not in sumArr):
sum += i
print(sum)
end = time.clock()
print ("time: %f s" % (end - start))

复制代码

答案：4179871

tengfei8382 · 发表于 2016-6-23 13:20:34

#定义一个求真因子之和的函数
def proper(num):
sum = 1
for x in range(2,num//2+1):
if num % x == 0:
sum += x
return sum
#定义一个函数，当它为两个过剩数之和时返回False ，否则返回Ture
def decide(num):
for each in abun_set:
if num > each and ((num-each) in abun_set):
return True
elif num < each:
return False
abun_set ={x for x in range(12,28123-11) if x < proper(x)}
abun_sum = sum(x for x in range(1,28124) if decide(x))
print(abun_sum)
#print(abun_set)

复制代码

tengfei8382 · 发表于 2016-6-23 13:21:06

tengfei8382 发表于 2016-6-23 13:20

391285755

wangzhenas · 发表于 2016-6-24 02:03:25

import time
import itertools
from functools import reduce
def primefactors(n):
f = 2
while f * f <= n:
while not n % f:
yield f
n //= f
f += 1
if n > 1:
yield n
t = time.time()
#to get all the abundunt numbers below 28123
s = {i for i in range(1,28124) if sum({reduce(lambda x,y:x*y,item) for num in range(1,len(list(primefactors(i)))) for item in itertools.combinations(list(primefactors(i)),num)})+1 > i}
l = sorted(list(s))
summ_l = sum(range(1,28124))
summ = 0
for i in range(1,28124):
for j in l:
if i -j <= 0:
break
if j in s and i-j in s:
summ += i
break
result = summ_l-summ
print(result)
print(time.time()-t)

复制代码

shichaoufo · 发表于 2016-6-24 20:17:50

不能表示为两个过剩数之和的正整数之和为：4179871

def guoshen(n):
he = 0
y = 0
x = n // 2 + 1
for i in range(x,0,-1):
if n % i == 0:
he += i
if he > n:
y = 1
break
return y
g_list = []
result = 0
for i in range(12,28123):
if guoshen(i):
g_list.append(i)
for i in range(1,28124):
panduan = 1
for j in g_list:
if j<i:
cha = i - j
if cha in g_list:
panduan = 0
break
else:
break
if panduan:
result += i
print("不能表示为两个过剩数之和的正整数之和为：%d" % result)

复制代码

bhsx · 发表于 2016-6-25 11:46:06

#python3.4
import time
t1 = time.perf_counter()
n = 28123
count = n // 2
dict = {}
get = dict.get
for i in range(2, count // 2 + 1):
for j in range(i, n // i + 1):
sum_num = i * j
dict[sum_num] = get(sum_num, 1) + i + (j if j != i else 0)
pass
#print(dict)
aa = [i for i, j in dict.items() if j > i]
bb = (j + k for i, j in enumerate(aa) for k in aa[i:])
bb = set(bb)
cc = [i for i in range(1, n+1) if i not in bb]
print(sum(cc))
print('%0.9f' % (time.perf_counter() - t1))

复制代码

诸天花雨 · 发表于 2016-6-25 14:06:10

def is_gss(num):
ret = 1
for i in range(2, num // 2 + 1):
if not num % i:
ret += i
if ret > num:
return True
else:
return False
gss = []
for i in range(12, 28123):
if is_gss(i):
gss.append(i)
ret = []
for i in gss:
for j in gss:
if i + j:
ret.append(i + j)
ret = set(ret)
ans = 0
for i in range(1, 28123):
if i not in ret:
ans += i
print(ans)

复制代码

4179871

挥舞乾坤 · 发表于 2016-6-25 18:07:29

def d(n):
# 是否过剩数
result = set()
for i in range(2,int(n**.5)+1):
if not n % i:
result.update({i, n // i})
return n > 1 and sum(result) + 1 > n
limite = range(20613)
abdn = []
result = [i for i in limite]
for i in limite:
if d(i):
abdn.append(i)
for e in abdn:
temp = i+e
if temp > 20612:
break
result[temp] = 0
print(sum(result))

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习：20160620 算出所有不能写成两个过剩数之和的正整数之和

马上注册，结交更多好友，享用更多功能^_^

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分