Project Euler 23

problem

A perfect number is a number whose true divisor sum matches itself. For example, the true divisor sum of 28 is 1 + 2 + 4 + 7 + 14 = 28. Since there is, 28 is a perfect number.

A number with a sum of true divisors less than that number is called a deficient number, and a number with a sum of true divisors greater than that number is called an abundant number.

Since 12 is 1 + 2 + 3 + 4 + 6 = 16, it is the smallest abundant number. Therefore, the minimum number that can be written by the sum of the two abundant numbers is 24. From 28123 by mathematical analysis. It is known that any large integer can be written as the sum of two abundant numbers. We know that the maximum number that cannot be represented by the sum of two abundant numbers is less than this upper limit, but we reduce this upper limit. I haven't been able to.

Find the sum of positive integers that cannot be written as the sum of two abundant numbers. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2023

Answer

Practice dictionary comprehension.

Validating elements using sets and dictionaries (O (1)) is faster than searching arrays (O (n)). When looking up a in b, b should be sets or dictionaries, not lists or tuples.

# -*- coding: utf_8 -*-
def factor_sum_seq(max):
  dl = [0] + [1]*(max)
  seq = range(max+1) 
  for i in seq[2:]:
    for j in seq[i*2::i]:
      dl[j] += i
  return dl

def cof():
  MAX = 28123+1 #+It's a pain to calculate 1

  seq = range(MAX)
  dl = factor_sum_seq(MAX)
  abu = [i for i in seq if dl[i] > i and dl[i]<MAX]
  abu2 = {i+j:True for i in abu for j in abu}
  ans = 0
  for i in seq:
    if not (i in abu2):
      ans += i
  print ans

cof()

Even so, it's too late. However, I have no intention of improving it.

Recommended Posts

Project Euler 37
Project Euler 47
Project Euler 31
Project Euler 4
Project Euler 38
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
[Project Euler] problem1
Project Euler15 "Lattice Path"
Project Euler 2 Acceleration 2.21 Save microseconds.
Project Euler Original Method Group 1
What is Project Euler 3 Acceleration?
Functional programming in Python Project Euler 1
Project Euler 10 "Sum of Prime Numbers"
[Note] Project Euler in Python (Problem 1-22)
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Project Euler 4 Attempt to speed up
Functional programming in Python Project Euler 2
Project Euler 11 "Maximum product in grid"
Project Euler # 15 "Lattice Path" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler 9 Retention of calculation results
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
I wrote Project Euler 1 in one liner.
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python