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

欧拉计划 · 发表于 2015-4-23 16:30:20

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

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

x

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 · 发表于 2016-8-27 19:28:57

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

复制代码

愤怒的大头菇 · 发表于 2016-8-29 22:07:42

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 · 发表于 2016-9-20 17:18:28

本帖最后由 jerryxjr1220 于 2016-10-11 23:17 编辑

优化了算法，用标记法，只要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)

复制代码

芒果加黄桃 · 发表于 2017-1-11 22:05:59

本帖最后由芒果加黄桃于 2017-1-11 22:08 编辑

# 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

渡风 · 发表于 2017-1-21 23:43:43

此代码使用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 · 发表于 2017-3-15 14:55:41

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

由我们主宰 · 发表于 2018-3-18 18:36:43

#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 · 发表于 2018-4-22 22:18:55

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 · 发表于 2018-4-22 22:19:29

4179871 9s

k往事如烟k · 发表于 2019-3-25 14:37:28

本帖最后由 k往事如烟k 于 2019-3-25 14:38 编辑

测试

cwhsmile · 发表于 2019-4-27 01:27:12

本帖最后由 cwhsmile 于 2019-4-27 12:44 编辑

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

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)

复制代码

王小召 · 发表于 2019-6-6 10:54:10

结果：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))

复制代码

永恒的蓝色梦想 · 发表于 2019-7-22 21:18:02

本帖最后由永恒的蓝色梦想于 2020-9-11 13:45 编辑

None

debuggerzh · 发表于 2020-8-4 17:13:10

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 · 发表于 2022-1-2 20:45:04

/*
答案：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;
}

复制代码

叶落了 · 发表于 2023-6-21 11:10:55

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

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

叶落了 · 发表于 2023-6-21 11:11:37

#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 · 发表于 2023-10-10 11:46:21

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

复制代码

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

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

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

评分