John Lekberg


JUNTO Practice - "Project Euler Problem 23"

Discussed on 2019-04-04.

Project Euler Problem 23


Solution - Daniel

import math

def getDivisors(num):
    if num == 1:
        return 1
    n = math.ceil(math.sqrt(num))
    total = 1
    divisor = 2
    while divisor < n:
        if num % divisor == 0:
            total += divisor
            total += num // divisor
        divisor += 1
    if n ** 2 == num:
        total += n
    return total

def isAbundant(num):
    if getDivisors(num) > num:
        return True
    else:
        return False

abundentNums = []
for x in range(0, 28124):
    if isAbundant(x):
        abundentNums.append(x)
del abundentNums[0]

sums = [0] * 28124
for x in range(0, len(abundentNums)):
    for y in range(x, len(abundentNums)):
        sumOf2AbundantNums = (
            abundentNums[x] + abundentNums[y]
        )
        if sumOf2AbundantNums <= 28123:
            if sums[sumOf2AbundantNums] == 0:
                sums[
                    sumOf2AbundantNums
                ] = sumOf2AbundantNums

total = 0
for x in range(1, len(sums)):
    if sums[x] == 0:
        total += x

print("\n", total)

Solution - John

import math

abundant = set()

for n in range(1, 28_123):
    sqrt_n = math.sqrt(n)
    
    divisor_sum = 1
    for m in range(2, int(sqrt_n) + 1):
        if n % m == 0:
            divisor_sum += m + (n / m)
    
    if sqrt_n.is_integer():
        divisor_sum -= sqrt_n
    
    if divisor_sum > n:
        abundant.add(n)

nonabundant_sum = 0
for i in range(1, 28_123):
    sum_of_abundants = False
    
    for k in sorted(abundant):
        if k > i / 2:
            break

        if i - k in abundant:
            sum_of_abundants = True
            break

    if not sum_of_abundants:
        nonabundant_sum += i

print(nonabundant_sum)

Solution - Oscar

def get_proper_divisors(num: int) -> set:
    i = num
    j = 2
    divisors = set()
    divisors.add(1)
    while j < i:
        if num % j == 0:
            divisors.add(j)
            i = num // j
            divisors.add(i)
        j += 1
    return divisors


def abundants():
    abundants = set()
    for i in range(12, 28124):
        if i < sum(get_proper_divisors(i)):
            abundants.add(i)
    return list(abundants)


def is_sum(numbers, target_sum):
    i = 0
    j = len(numbers) - 1
    while i < j:
        temp_sum = numbers[i] + numbers[j]
        if temp_sum < target_sum:
            i += 1
        elif temp_sum > target_sum:
            j -= 1
        else:
            return True
    if target_sum in [i * 2 for i in numbers]:
        return True
    return False


abundants = abundants()

sum(
    [k for k in range(1, 28124) if not is_sum(abundants, k)]
)