Geek asks and answers

Project Euler # 23, cannot find a problem in the program

Link: http://projecteuler.net/problem=23

An ideal number is a number for which the sum of its own divisors is exactly equal to the number. For example, the sum of the corresponding divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is an ideal number.

A number n is called insufficient if the sum of its own divisors is less than n, and this is called plentiful if this sum exceeds n.

Since 12 is the smallest bountiful number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two bountiful numbers 24. By mathematical analysis it can be shown that all integers greater than 28123 can be written as the sum of two bountiful numbers. However, this upper limit cannot yet be reduced by analysis, although it is known that the largest number, which cannot be expressed as the sum of two bountiful numbers, is less than this limit.

Find the sum of all positive integers that cannot be written as the sum of two bold numbers.

Answer to the problem: 4179871, my program shows 3797954.

First of all, I make a function to fill the rich [] array with all the plentiful numbers below 28124. This works fine, because I googled the plentiful numbers, and they exactly match my array.

-, 1-28123, , " ". hold [].

, , , [] [] hold [] 0. ( [ [ 0 n] + [0 n]] = 0) hold [], 3797954

, , , . ?

#include <iostream>
#include <cmath>

using namespace std;

int hold[28124];
int abundant[7000]; //hold abundant numbers, there are only 6919 abundant numbers below 28123

bool abundance(int x){  //returns true if x is abundant
    int counter = 1;    //holds "proper divisors" of numbers, default by 1 because every int is divisible by 1
    for (int i = 2; i < sqrt(x); i++){   //finds all divisors 2 - sqrt(n)
        if (x % i == 0){
            counter += i;
            counter += x / i;
        }
    }
    int y = sqrt(x);   
    if (x % y == 0){   //adds sqrt(n) if its modulus to n is 0
            counter += sqrt(x);
        }
    if (counter > x){
        return true;
    } else {
        return false;
    }
}

int main()
{
    int counter = 0;
    for (int i = 0; i < 28124; i++){ //assumes every number cannot be written as the sum of two abundant numbers,
        hold[i] = i;                 //goes up to 28123 because "it can be shown that all integers greater
    }                                //than 28123 can be written as the sum of two abundant numbers." - project euler
    for (int j = 10; j < 28124; j++){ 
        if (abundance(j) == true){  //copies all abundant numbers up to 28123 to abundant[]
            abundant[counter] = j;
            counter++;
        }
    }

    for (int m = 0; m < counter; m++){  //adds all numbers in abundant[], with all numbers in abundant[]
        for (int n = 0; n < counter; n++){
            if (abundant[m]+abundant[n] < 28124){
                hold[abundant[m]+abundant[n]] = 0; //sum of the abundant numbers in hold[] is set to 0
            } //hold[] now holds all numbers that cannot be written as the sum of 2 abundant numbers
        }
    }
    int counter2 = 0;
    for (int x = 0; x < 28124; x++){
        counter2 += hold[x];
    }
    cout << counter2 << endl;

}
+5
3

abundance, , :

int y = sqrt(x);   
if (x % y == 0){   //adds sqrt(n) if its modulus to n is 0
    counter += sqrt(x);
}

x % (int)sqrt(x) == 0 , sqrt(x) . 2. sqrt(2) 1.414, 1 . 2 % 1 == 0, .

, , :

int y = sqrt(x);   
if (y * y == x){   //adds sqrt(n) if sqrt(n) is an integer
    counter += y;
}

.

+7

- , . , , , , , . , .

+1
my_set = set([i for i in range(1, 28123)])
print ('original sum',sum(my_set))
my_list = list(my_set)
my_l1 =[]
for k in range(12, int(my_list[-1]/2+1)):
    a = 0
    for j in range(1, int(k/2+1)):
        if k%j == 0:
            a += j

    if a > k:
        my_l1.append(k)
        my_set.remove(k*2)
#Calculating the sum of all the numbers which can be written as the sum of two abundant numbers   
l = 0
my_l2 = set([])
for d in my_l1:
    l += 1
    k = l
    while k < len(my_l1):
        a_s = d + my_l1[k]
        my_l2.add(a_s)
        k += 1
my_set.difference_update(my_l2)
print ('sum of all abbundant numbers:',sum(my_set))

23 Project Euler, ? , .

0

More articles:


All Articles