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

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：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

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

caobynk

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

严重支持

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

#欧拉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个人回帖

老忘

#-*- 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

# -*- 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

#答案为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

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

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

小火木

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))

昨、夜星辰

适用于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_

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

#定义一个求真因子之和的函数
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

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

391285755

wangzhenas

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

不能表示为两个过剩数之和的正整数之和为：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

#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))

诸天花雨

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

挥舞乾坤

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))