题目23：算出所有不能写成两个过剩数之和的正整数之和

欧拉计划

Non-abundant sums

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

题目：

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

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

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

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

Plusenxue

def isguoshen(x):
    n = 0
    for i in range(1,x):
        if x%i == 0:
            n += i

    if n > x:
        return True
    else:
        return False

guoshen = []
guoshenhe = {0}

for i in range(12,14062):
    if isguoshen(i):
        guoshen.append(i)

for i in range(3490):
    for j in range(i,3490):
        guoshenhe.add(guoshen[i]+guoshen[j])

愤怒的大头菇

import math

def Full(x):
    list1 = [1]
    for i in range(2,int(math.sqrt(x)+1)):
        if x % i == 0:
            list1.append(i)
            if x/i not in list1:
                list1.append(x/i)
                
    if sum(list1) > x:
        return True
    else:
        return False      
list1 = []
for i in range(1,28111):
    if Full(i):
        list1.append(i)
list2 = {0}
for i in range(6961):
    for n in range(i,6961):
        list2.add(list1[i]+list1[n])
list3=[]
for i in range(1,28123):
    if i not in list2:
        list3.append(i)

print(sum(list3))

结果是4179871，10秒不到出结果

jerryxjr1220

优化了算法，用标记法，只要2秒多就出结果

4179871
[Finished in 2.2s]

def y(n):
        lst = [1]
        for i in range(2,int(n**0.5+1)):
                if n%i == 0:
                        lst.append(i)
                        lst.append(int(n//i))
                        lst = list(set(lst))
        return lst

master = [0 for z in range(28124)]
for j in range(1,28124):
        if j == 1:
                master[j] = 1
        elif j == 2:
                master[j] = 1
        else:
                master[j] = sum(y(j))
abundant = []
for k in range(1,28124):
        if k < master[k]:
                abundant.append(k)
not_abundant = [i for i in range(28124)]
for i, a in enumerate(abundant):
        for b in abundant[i:]:
                if a+b < 28124: 
                        not_abundant[a+b] = 0
                else: 
                        break   # no need to go further
print sum(not_abundant)

芒果加黄桃

# encoding:utf-8
# 过剩数
from time import time
N = 28123
def getFactorsSum(N):
    l_result = [1]
    for t in range(2, int(N ** 0.5) + 1):
        if N % t == 0:
            l_result.append(t)
            l_result.append(N // t);
    return sum(list(set(l_result)))
def findAbns():
    l_abns = []
    for i in range(1, N):
        if getFactorsSum(i) > i:
            l_abns.append(i)
    return l_abns   
def euler022():
    l_temp = []
    l_abns = findAbns()
    for i in range(0, len(l_abns)):
        for j in range(i, len(l_abns)):
            tmp = l_abns[i] + l_abns[j]
            if tmp > N:
                break
            l_temp.append(tmp)
    s_abns = set(l_temp)
    s_all = set(i for i in range(1, N + 1))
    l_result = list(s_all - s_abns)
    l_result.sort()
    return l_result
    
if __name__ == '__main__':
    start = time()
    print(sum(euler022()))
    print('cost %.6f sec' % (time() - start))

4179871
cost 4.461165 sec

渡风

此代码使用matlab编程
Problem23所用时间为4.2954秒
Problem23的答案为4179871

%% Problem23
% 题目23：算出两个不能够被两个过剩数之和表示的所有正整数之和
function Output=Problem23(Input)
tic
if nargin==0
Input=28123;
end
Abundant=[];
for ii=2:Input
    if sum(Factor_Rank(ii))>ii
        Temp=[Abundant,ii];
        Abundant=Temp;
    end
end
L=length(Abundant);
Result=1:Input;
for jj=1:L
    Result=setdiff(Result,Abundant+Abundant(jj));%巧妙，将2重循环变为单重循环
end
Output=sum(Result);
toc
disp('此代码使用matlab编程')
disp(['Problem23所用时间为',num2str(toc),'秒'])
disp(['Problem23的答案为',num2str(Output)]) 
end
%% 子程序
%输入一个数，得到其真因子序列，顺序排列，入10，--1,2,5..
function Output=Factor_Rank(Input)
if nargin==0
Input=12;
end
Node=floor(sqrt(Input));
Factor=[];
if Node*Node==Input
    Factor=Node;
    Middle=Node-1;%最中间的约数
else
    Middle=Node;
end
for ii=Middle:-1:2
    if mod(Input,ii)==0
        Temp=[ii,Factor,Input/ii];
        Factor=Temp;
    end
end
Output=[1,Factor];
end

99592938

import time
st = time.clock()
def isabundant(x):
    sum0=1
    for i in range(2,int(x**0.5)+1):
        if not x%i:
            if x==i**2:sum0+=i
            else:sum0+=i+x//i
    if sum0>x:return 1
    else:return 0

l_ab=[]
dic_n={}
for n in range(1,28124):
    if isabundant(n):
        l_ab.append(n)
    dic_n[n]=n
for i in l_ab:
    for j in l_ab:
        if i+j in dic_n:
            del dic_n[i+j]
print(sum(list(dic_n.values())))
et = time.clock()
print('read:%.3f s' %(et-st))

>>>
4179871
read:13.530 s

由我们主宰

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int Judeg(int x)
{
        int i,sum=0;
        for(i=1;i<x;i++)
        {
                if(0==x%i)
                {
                        sum=sum+i;
                }        
        }
        if(sum>x)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}
int main()
{
        int i,j,n,leap;
        double s=0;
        clock_t start,end;
        start=clock();
        for(n=1;n<=28123;n++)
        {
                leap=1;
                for(i=12;i<=n/2;i++)
                {
                        j=n-i;
                        if(Judeg(i)&&Judeg(j))
                        {
                                leap=0;
                                break;
                        }
                }
                if(leap)
                {
                                s=s+n;
                                printf("%d\t",n);
                }
        }
        end=clock();
        printf("\n本次计算用时%f秒\n",(double)(end-start)/CLK_TCK);
        printf("%f\n",s);
        system("pause");
        return 0;
}

hvagab

from math import sqrt

import time

st = time.time()
def f(n):
    l= set()
    for i in range(1,int(sqrt(n))+1):
        if n % i ==0:
            j = n//i
            l.add(i)
            l.add(j)

    return sum(l-{n})

def g(n):
    if f(n)>n:
        return n
    else:
        return 0

lis  = []
for i in  range(12,28123):
    if g(i) !=0:
        lis.append(g(i))

print(lis)
lis1 = set()
for ii in lis:
    for j in lis:
        lis1.add(ii+j)

lis2 = []
for p in range(1,28123):
    if p not in lis1:
        lis2.append(p)
print(sum(lis2))
print(time.time() - st)

hvagab

4179871 9s

k往事如烟k

测试

cwhsmile

方法不好，需要优化的地方多，列表对于超过一万以上的长度不建议用，最好用字典，长度低了就用列表。
慢慢的发现，思维方式不同，做出的结果可以差很多倍。

import time
import math

def test1():
    num = []
    for m in range(2,28124):
        li = [1]
        for n in range(2,int(m**0.5)+1):
            if m%n == 0:
                li.append(n)
                li.append(int(m/n))

        if sum(set(li)) > m:
            num.append(m)
    long = len(num)
    print(long)
    print(num[-10:])
    b = []
    for n in range(long):
        for i in range(n,long):
            temp = num[i]+num[n]
            if temp < 28124:
                b.append(temp)
            else:
                break
    
    print(b[-10:])
    result = 0
    b = set(b)
    print(len(b))
    for j in range(1,28124):
        if j in b:
            continue
        result += j
    return result


li = []
start = time.perf_counter()
print(test1())
end = time.perf_counter()
print(end-start)

上面的代码运行了5秒多，下面是改进的代码，把列表换成了字典，把过剩数相加的取值范围缩减了一下，3秒多运行完毕。

import time
import math

def test1():
    num = []
    for m in range(2,28124):
        li = [1]
        for n in range(2,int(m**0.5)+1):
            if m%n == 0:
                li.append(n)
                li.append(int(m/n))
        if sum(set(li)) > m:
            num.append(m)
            
    long = len(num)
    dict1 = {}
    for a in range(28124):
        dict1[a] = 1
    for n in range(long//2):
        for i in range(n,long-n):
            temp = num[i]+num[n]
            dict1[temp] = 0

    result = 0
    for j in range(28124):
        if dict1[j] == 1:
            result += j
    return result
li = []
start = time.perf_counter()
print(test1())
end = time.perf_counter()
print(end-start)

王小召

结果：4179871
用时：5.985732424725128

import time
import math

def guosheng():
    gs_l = []
    for i in range(12, 28123):
        tmp = []
        for x in range(2, int(math.sqrt(i) + 1)):
            if not i % x:
                tmp.append(x)
                tmp.append(int(i/x))
        if sum(set(tmp)) > i-1:
            gs_l.append(i)

    return sum(range(28124)) - sum(set([gs_l[n1] + gs_l[n2] for n1 in range(len(gs_l)) for n2 in range(n1, len(gs_l)) if gs_l[n1] + gs_l[n2] < 28124]))


start = time.clock()
print("结果：{}\n用时：{}".format(guosheng(), time.clock()-start))

永恒的蓝色梦想

None

debuggerzh

4179871

Process returned 0 (0x0)   execution time : 0.824 s
Press any key to continue.
暴力打表，先求出1~28123的所有过剩数，再二层循环枚举两过剩数之和
以下为关键代码

const int M = 28123 + 1;
const int M_RANGE = 7000 + 5;

int abundant[M_RANGE];
int vis[M] = {0};

int main(){

  int cnt = 0,ans = 0;
        
  for (int i = 1;i < M;i++){
    int factor_sum = 0;
    for (int j = 1;j <= i/2;j++)
      if (i % j == 0) factor_sum += j;
    if (factor_sum > i) abundant[cnt++] = i;
  }
  
  for (int i = 0;i < cnt;i++)
    for (int j = i;j < cnt;j++){
      int sum = abundant[i] + abundant[j];
      if (sum < M && !vis[sum]) vis[sum] = 1;
  }
  
  for (int i = 0;i < M;i++)
    if (!vis[i]) ans += i;
  
  cout << ans << endl;
        return 0;
}

guosl

/*
答案：4179871
耗时：0.0097935秒
*/
#include <iostream>
#include <cmath>
using namespace std;

char a[28124];//打表，a[i]=1表示i是一个过剩数

bool is_abundant(int k)//计算k是否是一个过剩数
{
  int d = (int)sqrt((double)k);
  int s = 1;
  for (int i = 2; i <= d; ++i)
  {
    if (k % i == 0)
    {
      int n = k / i;
      if (i == n)
        s += i;
      else
        s += i + n;
    }
  }
  return (s > k);
}

int main(void)
{
  int nS = 0;
  for (int i = 1; i < 28124; ++i) //打表
  {
    if (is_abundant(i))
      a[i] = 1;
  }
  for (int i = 1; i < 28124; ++i)
  {
    bool bFlg = true;
    for (int j = 1; j <= (i >> 1); ++j) //枚举i的拆分
    {
      if (a[j] == 1 && a[i - j] == 1)
      {
        bFlg = false;
        break;
      }
    }
    if (bFlg)
      nS += i;
  }
  cout << nS << endl;
  return 0;
}

叶落了

cwhsmile 发表于 2019-4-27 01:27
方法不好，需要优化的地方多，列表对于超过一万以上的长度不建议用，最好用字典，长度低了就用列表。
慢慢 ...

过剩数相加的取值范围缩减了一下，具体有什么原理吗，我感觉好像不能完全覆盖。如果数据很大的话

叶落了

#include<stdio.h>
#include<math.h>

int determine(int i);//求质因数之和
int determine(int i)
{
        int k;
        int sum1=0;
       
        for(k=1;k<=pow(i,1.0/2);k++)
        {
                if(i%k==0&&i/k!=k)
                {
                        sum1=sum1+k+i/k;
                }
                if(i%k==0&&i/k==k)
                {
                        sum1=sum1+k;
                }
        }
        sum1=sum1-i;
        if(sum1>i)
        {
                return sum1;
        }
        else
        {
                return 0;
        }
}

int main(void)
{
        int k=0,i,m;
        long int sum0=0;//前28213的和
        int array[10000]={0};//储存过剩数
        int count=0;//过剩数的数量
        long int sum1=0;
       
        for(i=1;i<=28213;i++)
        {
                sum0=sum0+i;
        }
        printf("%lld\n",sum0);
        for(i=12;i<=28213;i++)
        {
                if(determine(i))
                {
                        array[k]=i;
                        count++;
                        k++;
                }
        }
        printf("%d\n",count);
        for(i=24;i<=28213;i++)
        {
                for(m=0;array[m]<=i;m++)//这里不用<=(i-array[m]),因为我曾经犯过错。除非你赋值
                {
                        if(determine((i-array[m])))
                        {
                                sum1=sum1+i;
                                break;
                        }
                }
        }
       
        printf("%lld\n",sum1);
       
        printf("所有不能表示为两个过剩数之和的正整数之和为%d\n",(sum0-sum1));
       
        return 0;
}

mathtimes

4179871 0.5s

fn factors(x: i32) -> Vec<i32> {
    let mut pt: Vec<i32> = vec![1];
    let mut x_sq = (x as f32).sqrt() as i32;
    if x == x_sq * x_sq && x > 1 {
        pt.push(x_sq);
        x_sq -= 1;
    }
    for i in 2..=x_sq {
        if x % i == 0 {
            pt.push(i);
            pt.push(x / i);
        }
    }
    pt
}

fn main() {
    let mut abundant = Vec::new();
    for i in 1..=28123 {
        if factors(i).iter().sum::<i32>() > i {
            abundant.push(i);
        }
    }
    let mut number_table: Vec<bool> = vec![true; 28124];
    for i in &abundant {
        for j in &abundant {
            if i + j < 28124 {
                number_table[(i + j) as usize] = false;
            }
        }
    }
    println!(
        "{}",
        number_table
            .iter()
            .enumerate()
            .map(|(i, &x)| if x { i as i32 } else { 0 })
            .sum::<i32>()
    )
}