Optimizing Sum of Non-Abundant Numbers

[Arman777]

I need to find the sum of all the numbers who cannot be expressed by the sum of 2 abundant number. I am trying to think a mathematical approach but I am kind of stuck. (I am trying to write a code about it my code works but I need a faster way to solve it since it would take a day to solve it with my code).

The real problem is this I guess, Whats is the numerical property that the sum of 2 abundant number has but the other number hasn't?

I thought many things but none of them gives me anything useful. It seems like there's no pattern. But maybe I am missing something who knows

 

[jedishrfu]

So you're referring to abundant numbers:

https://en.wikipedia.org/wiki/Abundant_number

Right?

I ask because "abundant" normally means "plentiful" and I was having trouble understanding your post.

https://www.merriam-webster.com/dictionary/abundant

There are some computational problems where there is no algorithmic solution other than brute force and so it will take a long time to compute. It seems this problem is one of them.

It seems you have to factor each number, sum its proper divisors and then determine if the sum is greater than the number.

You could build a list of prime factors and then use modulo arithmetic to see if the prime factor is a factor of your current number and then you mix and match
prime factors to create a set of proper divisors for your number which you can then sum.

 

[Arman777]

Right?

Yes I was referring that

There are some computational problems where there is no algorithmic solution other than brute force and so it will take a long time to compute. It seems this problem is one of them.

There are 6965 abundant numbers that I have to sum up with each other...Maybe you are right I can only use brute force but my code structure makes it solve longer..I ll think about it.

the code for abundant number "finder" is like this

def div(N):
    A=[]
    for i in range(1,N):
        if N%i==0:
            A.append(i)
    s=sum(A)
    return s

def abundant(N):
     if N<div(N):
        return True
     else:
        return False
K=[]
for i in range(28123):
    if abundant(i)==True:
        K.append(i)

Its really simple it calculates this in 10-20 sec but then in the sum process things take longer time. I was just curious that, If there were any numerical properties that I can use..I guess not. Thanks for your help

 

[jedishrfu]

I think you can reduce the N to N/2 in the div() method right? because the next number in the list is N the number itself.

http://www.positiveintegers.org/IntegerTables/1-100

As an example, the number 100 has these divisors:

1, 2, 4, 5, 10, 20, 25, 50, 100

There are no divisors after 50 ie N/2 other than N

That should double your search speed at least.

 

[mfb]

1/2+1/3+1/6 = 1.
1/2+1/4+1/5+1/10 > 1
There are two large classes of abundant numbers which rely on this. Using them and a couple of odd abundant numbers from your list you can find an upper limit for your search.
Simple brute force (for each number, see if you find a pair that sums to this number) would work from there on with significant computing time.
You can speed it up more:
* Odd abundant numbers are rare, and odd sums have to be the sum of one odd and one even abundant number. That narrows down the search a lot.
* The largest even number which is not the sum of two abundant number is so small you can find it by hand.
With these two things you should be able to compute the sum in a few seconds.

 

[Arman777]

I manage to solve the problem, Here the code that I used if you wonder

#!/usr/bin/python
import time
start=time.time()
def div(N):
    A=[]
    for i in range(1,N//2+1):
        if N%i==0:
            A.append(i)
    s=sum(A)
    return s

def abundant(N):
     if N<div(N):
        return True
     else:
        return False
K=[]
for i in range(28123):
    if abundant(i)==True:
        K.append(i)

H=[]
for i in range(len(K)):
    for j in range(i,len(K)):
        q=K[i]+K[j]
        if q<=28123:
            H.append(q)
G=list(set(H))
l=sum(G)
g=(28123*28124)/2
print("The sum is", g-l)
end=time.time()
Time=end-start
print("Time:",Time)

As an example, the number 100 has these divisors:

1, 2, 4, 5, 10, 20, 25, 50, 100

There are no divisors after 50 ie N/2 other than N

That should double your search speed at least.

yes it exactly doubled
I tried with your approach and I get the result in $17.737668991088867$ second but if I used just N I get the result in $33.31437921524048$ second

 

[Arman777]

1/2+1/3+1/6 = 1.
1/2+1/4+1/5+1/10 > 1
There are two large classes of abundant numbers which rely on this. Using them and a couple of odd abundant numbers from your list you can find an upper limit for your search.
Simple brute force (for each number, see if you find a pair that sums to this number) would work from there on with significant computing time.
You can speed it up more:
* Odd abundant numbers are rare, and odd sums have to be the sum of one odd and one even abundant number. That narrows down the search a lot.
* The largest even number which is not the sum of two abundant number is so small you can find it by hand.
With these two things you should be able to compute the sum in a few seconds.

I understand your approach but I think it would make things a bit more complicated like I can miss a abundant number or something like that ?

 

[jedishrfu]

Yes, you always have to fine tune algorithms. Its the edge cases that give you trouble.

 

[Arman777]

Yes, you always have to fine tune algorithms. Its the edge cases that give you trouble.

Yes...I was doing wrong cause I was summing things multiple times and adding the numbers again multiple times.

You may wonder what's is the q<=28123 means After that number every possible number can be written as the sum of 2 abundant numbers so that was my limit.

 

[mfb]

for i in range(len(K)):
for j in range(i,len(K)):

Okay, that is the brute force approach.

You may wonder what's is the q<=28123 means After that number every possible number can be written as the sum of 2 abundant numbers so that was my limit.

How do you know that without looking it up?

 

[jedishrfu]

But I don’t think the converse is true. If a number is the sum of two abundant numbers then it’s also an abundant number.

 

[Arman777]

Okay, that is the brute force approach.

How do you know that without looking it up?

Yes.Well if there was a any property of the numbers that i have mentioned earlier then It would take like 4-5 seconds to solve or maybe less

in the code first i wrote 2 functions to define abundant numbers. Then I summed then up properly to find the numbers that can be wriiten by the sum of the 2 abundant number. After that I deleted the repeated terms. Finally I summed these numbers again and removed it from "the number" to find the answer.

If I had the property, I would just use the property to find the numbers then I would put them into an array and just sum the numbers without doing anything special (means by just using sum(list)) and then I would remove it from (28123*28124/2).

It says in the question. Its a project euler question number 23

First I thought brute force isn't going to work because it was taking so long due to the summing part of the code, but then I realized it was my mistake due to the summing process. So I fixed the summing part and got the result fast enough.

 

[Arman777]

But I don’t think the converse is true. If a number is the sum of two abundant numbers then it’s also an abundant number.

Yes the sum of 2 abundant number doesn't have to be abundant number. For example
20 is abundant 24 is abundant but 44 is not an abundant number.

 

[mfb]

Okay.
Here are the observations I meant:
Every multiple of 6 apart from 6 itself is an abundant number as it has 1/2, 1/3 and 1/6 of it as divisor plus something else (e.g. 1).
20 and 40 are abundant numbers. If divided by 6, they have remainder 2 and 4, respectively.

Excluding numbers up to 50:
- every multiple of 6 can be written as sum of two abundant numbers, sum two multiples of 6
- every multiple of 6 plus 2 can be written as sum of two abundant numbers, use 20 plus a multiple of 6
- every multiple of 6 plus 4 can be written as sum of two abundant numbers, use 40 plus a multiple of 6
This means every even number above 50 can be written as sum of two abundant numbers.
Doing some casework for small even numbers we see that all numbers from 2 to 22 and 26, 28, 34, 46 cannot be written as sum, but all others can.

Odd abundant numbers are rare. Odd sums of abundant numbers have to have an odd abundant number as summand, looping over them and checking if the corresponding even number is abundant (for each target number) is much faster than looping over all pairs of abundant numbers. You can also skip all odd numbers divisible by 3 starting at 945+12.

 

[Arman777]

Okay.
Here are the observations I meant:
Every multiple of 6 apart from 6 itself is an abundant number as it has 1/2, 1/3 and 1/6 of it as divisor plus something else (e.g. 1).
20 and 40 are abundant numbers. If divided by 6, they have remainder 2 and 4, respectively.

Excluding numbers up to 50:
- every multiple of 6 can be written as sum of two abundant numbers, sum two multiples of 6
- every multiple of 6 plus 2 can be written as sum of two abundant numbers, use 20 plus a multiple of 6
- every multiple of 6 plus 4 can be written as sum of two abundant numbers, use 40 plus a multiple of 6
This means every even number above 50 can be written as sum of two abundant numbers.
Doing some casework for small even numbers we see that all numbers from 2 to 22 and 26, 28, 34, 46 cannot be written as sum, but all others can.

Odd abundant numbers are rare. Odd sums of abundant numbers have to have an odd abundant number as summand, looping over them and checking if the corresponding even number is abundant (for each target number) is much faster than looping over all pairs of abundant numbers. You can also skip all odd numbers divisible by 3 starting at 945+12.

Let me try to write a code for this, later I ll share it here.

 

[Arman777]

Odd abundant numbers are rare. Odd sums of abundant numbers have to have an odd abundant number as summand, looping over them and checking if the corresponding even number is abundant (for each target number) is much faster than looping over all pairs of abundant numbers. You can also skip all odd numbers divisible by 3 starting at 945+12.

I am not sure how can I code this. I mean without defining the odd abundant numbers.

 

[Arman777]

Well, any case it would faster yes. If that's the problem. But I wouldn't prefer this method. Since the time difference will be just 10 seconds. But thanks I see your points.

Edit: Let's think like this, all even numbers after 50 can be expressed by the sum of 2 abundant numbers right. Before 50 is easy and can be found by hand.

But as you said for odd numbers we need to find odd abundant numbers. In that sense again we need to find all even abundant numbers. So that we can find the odd numbers.

I guess eventually we need to find the all abundant numbers first but instead of summing all of them with each other (which what I did) we just have to add the even abundant numbers with the odd abundant numbers?

 

[mfb]

Since the time difference will be just 10 seconds.

Well, I wrote that post under the assumption that brute force took too long.

But as you said for odd numbers we need to find odd abundant numbers. In that sense again we need to find all even abundant numbers. So that we can find the odd numbers.

Sure, but you had that code already. There are something like 100 (?) odd abundant numbers below 28,000. If a number is divisible by 3 you can skip it. If not, you can loop over the list of odd abundant numbers and see if target-number is in the list of even abundant numbers. This gives about 10,000 * 100 steps (numbers to test times odd abundant numbers) instead of something like 10,000*10,000 (number of abundant numbers squared).

 

[Arman777]

Well, I wrote that post under the assumption that brute force took too long.Sure, but you had that code already. There are something like 100 (?) odd abundant numbers below 28,000. If a number is divisible by 3 you can skip it. If not, you can loop over the list of odd abundant numbers and see if target-number is in the list of even abundant numbers. This gives about 10,000 * 100 steps (numbers to test times odd abundant numbers) instead of something like 10,000*10,000 (number of abundant numbers squared).

I tried your approach and here is the code. If you have a question you can ask it or change it.

#!/usr/bin/python
import time
start=time.time()
def div(N):
    A=[]
    for i in range(1,N//2+1):
        if N%i==0:
            A.append(i)
    s=sum(A)
    return s

def abundant(N):
     if N<div(N):
        return True
     else:
        return False
K=[]
for i in range(945,28123,2):  #defining the odd abundant numbers
    if abundant(i)==True:
        K.append(i)
L=[]
for i in range(0,28123,2):     #defining the even abundant numbers
    if abundant(i)==True:
        L.append(i)

C=[32,36,38,40,42,44,48,24,30,50]

for i in range(len(K)):     #summing odd abundant numbers to even abundant numbers
    for j in range(len(L)):
        r=K[i]+L[j]
        if r<=28123:
            C.append(r)
      
G=list(set(C))
l=sum(G)
g=(28123*28124)/2-(14061*14062)+(25*26)     #(14061*14062)+(25*26)  is the sum of even numbers between 50 and 28123
print("The sum is", g-l)
end=time.time()
Time=end-start
print("Time:",Time)

Time is :$12.1127479076385$ second
Mine was $17.77777361869812$ second
I mean I am not sure how can I more improve it

Edit:There are just $62$ odd abundant numbers and $6903$ even abundant numbers.between between $1$ and $28123$.