023. Non-Abundant Sums (두 과잉수의 합으로 표현할 수 없는 수 구하기)

​문제 (English)

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 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.

 

Answer: 4179871

문제 분석

---

두 과잉수의 합으로 표현할 수 없는 모든 수에 대한 합을 구하라는 문제.

 

n에 대한 약수에서, 자기 자신인 n을 뺀 나머지 약수를 '진약수'라고 한다. 

이 진약수의 합을 $d(n)$으로 표현한다면, 

• 완전수: 진약수의 합이 자기 자신이 되는 수. 즉, $d(n) == n$
• 과잉수: 진약수의 합이 자기 자신보다 큰 수.  $d(n) > n$
• 부족수: 진약수의 합이 자기 자신보다 작은 수. $d(n) < n$

문제에서 주어진 것처럼 28123 보다 큰 정수는 모두 어떤 두 과잉수의 합으로 표현할 수가 있다고 한다. 

따라서, 문제에서, 과잉수의 합으로 표현할 수 없는 정수의 합을 구하라는 것은, 28123보다 작은 정수에 대해서만, 과잉수의 합으로 표현할 수 없는 것을 찾으면 된다. 

 

 

풀이 1 

---

다음과 같은 풀이 수순을 생각할 수 있겠다. 

1) 28123보다 작은 과잉수를 구한다. 

2) 구한 과잉수들의 합 조합을 해보고, 두 합이 28123보다 작은 것들을 체크해 놓는다.

3) 위 2번에서 체크한 수를 뺀 나머지 수들이, 과잉수의 합으로 표현되지 않는 수이다. 이 수들의 합을 구한다.

 

1) 28123보다 작은 과잉수를 구한다.

과잉수는 진약수의 합이 자기 자신보다 큰 수이다. 

진약수는 약수 중에서 자기 자신을 뺀 약수이다. 따라서, 진약수의 합은, 약수의 합을 구한 후 자기 자신을 빼면 된다.

 

따라서, 28123보다 작은 수에 대해서 진약수의 합이 그 수보다 큰 지 비교하면서 과잉수를 찾는다.

#[cfg(test)]
//get all abundant number <= n
fn abundant_num(n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = Vec::new();
    for i in 4..=n {
        let a = sigma_proper(i);
        if a > i {
            v.push(i);
        }
    }
    return v;
}

#[cfg(test)]
//sum of all proper divisors which is sum of all divisors except n
fn sigma_proper(n:usize) -> usize{   
    let a = sigma(n); 
    return a - n;
}

#[cfg(test)]
// calculate sum of all divisios of n
// n = 12, 12=2^2 x 3, sum=(1+2+4)(1+3)=28 {1,2,3,4,6,12}
// n = 10, 10=2 x 5, sum=(1+2)(1+5)=18  {1,2,5,10}
// n = 4, 4 = 2 x 2, sum = (1+2+4) = 7 {1,2,4}
fn sigma(num:usize) -> usize{
    let mut n = num;
    let sqrt_n = (n as f64).sqrt() as usize;
    let primes = find_primes(sqrt_n);

    let mut ans = 1;
    for i in primes {
        let mut sum = 1;
        let mut ii = i;
        while n % i == 0 {  
            sum += ii;
            ii *= i;
            n /= i;
        }
        ans *= sum;
        if n == 1 {break;}
    }
    if n != 1 {ans *= 1+n; } //n=10의 경우, n=5에서 벗어남
   
    return ans;
}

위 코드에서 sigma 함수는 약수의 합을 구하는 함수로, 이 코드의 핵심이다. 여기서는, 약수의 합을 소인수분해를 이용해서 구했다. 이 코드에 대한 설명은 별도로 작성된 약수에 대한 설명 페이지에서 참조.

 

2) 두 과잉수들의 합으로 표현될 수 없는 수들을 찾는다.

28123보다 큰 수들은 모두 두 과잉수들의 합으로 표현할 수 있다고 문제에서 얘기했다. 

그렇다면 28123보다 작은 값들에 대해서, 일일이 과잉수의 합으로 표현될 수 있는지 조사해도 되겠다.

 

그러나, 그보다 좀 더 효율적인 방법은, 과잉수들의 조합으로 만들 수 있는 수들을 체크하고, 체크하지 않은 것만 가려내면 될 것이다.

 

#[cfg(test)]
//get all number of <= n that is not sum of two abundant_num
fn get_not_sum_of_abundant_num(n:usize) -> Vec<usize>{
    let v = abundant_num(n);

    let mut cache = vec![0; n+1];
    for i in 0..v.len(){
        for j in i..v.len(){
            let add = v[i] + v[j];
            if add <= n {cache[add]=1; }
        }
    }

    let mut v:Vec<usize> = Vec::new();
    for i in 1..=n{
        if cache[i] == 0 {v.push(i);}
    }
    return v;
}

  

위와 같이 과잉수의 합으로 표현할 수 없는 수들을 저장하는 함수를 만들어서, 그 수들을 얻어내고 합을 구하면 되겠다.

 

또는, 과잉수의 합으로 표현할 수 없는 수들을 찾아내면서 거기서 바로 합을 구해도 되겠다. 아래 코드가 그것이다.

#[cfg(test)]
//과잉수의 합으로 나타낼 수 없는 수들의 합
fn answer() -> usize{
    let n = 28123;
    let v = abundant_num(n);

    // println!("{:?}",v);

    let mut cache = vec![0; n+1];
    for i in 0..v.len(){
        for j in i..v.len(){
            let add = v[i] + v[j];
            if add <= n {cache[add]=1; }
        }
    }

    let mut sum = 0;
    for i in 1..=n{
        if cache[i] == 0 {sum += i;}
    }
    return sum;
}

 

풀이 2 

---

hackerrank에서는, 어떤 수를 문제로 내고, 이 수가 과잉수이면 YES, 아니면 NO를 출력하는 문제이다. 

 

이 문제에 대한 코드는 아래와 같다. 핵심 함수는 똑같고, 다만, 먼저 과잉수로 표현할 수 없는 수를 벡터로 만들어  놓고, 각 문제에 대해서 이 벡터에 있는지를 파악해서 답을 하는 형태.

use std::io::{self, BufRead};
fn main() {
    let stdin = io::stdin();
    let mut it = stdin.lock().lines();
    let t = it.next().unwrap().unwrap().trim().parse::<usize>().unwrap();
    
    let v = get_not_sum_of_abundant_num(100000);
    for _ in 0..t {
        let n = it.next().unwrap().unwrap().trim().parse::<usize>().unwrap();
        if v.contains(&n) {
            println!("NO");
        }else {
            println!("YES");
        }        
    }
}  

fn get_not_sum_of_abundant_num(n:usize) -> Vec<usize>{
    let v = abundant_num(n);

    let mut cache = vec![0; n+1];
    for i in 0..v.len(){
        for j in i..v.len(){
            let add = v[i] + v[j];
            if add <= n {cache[add]=1; }
        }
    }

    let mut v:Vec<usize> = Vec::new();
    for i in 1..=n{
        if cache[i] == 0 {v.push(i);}
    }
    return v;
}

//get all abundant number <= n
fn abundant_num(n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = Vec::new();
    for i in 4..=n {
        let a = sigma_proper(i);
        if a > i {
            v.push(i);
        }
    }
    return v;
}

fn sigma(num:usize) -> usize{
    let mut n = num;
    let sqrt_n = (n as f64).sqrt() as usize;
    let primes = find_primes(sqrt_n);

    let mut ans = 1;
    for i in primes {
        let mut sum = 1;
        let mut ii = i;
        while n % i == 0 {  
            sum += ii;
            ii *= i;
            n /= i;
        }
        ans *= sum;
        if n == 1 {break;}
    }
    if n != 1 {ans *= 1+n; } 
   
    return ans;
}

//sum of all proper divisors which is sum of all divisors except n
fn sigma_proper(n:usize) -> usize{   
    let a = sigma(n); 
    return a - n;
}

//find all primes <= n
fn find_primes(n:usize) -> Vec<usize> {
    //1. sieve
    let mut sieve:Vec<usize> = vec![1; n+1];
    sieve[0]=0; sieve[1]=0;
    let sqrt_n = (n as f64).sqrt() as usize;
    for i in 2..=sqrt_n {
        for j in (2*i..=n).step_by(i) {
            sieve[j] = 0;
        } 
    }
    //2. primes
    let mut primes:Vec<usize> = Vec::new();
    for i in 2..sieve.len() {
        if sieve[i] == 1 {primes.push(i);}
    }
    return primes;
}

 

총평

---

약수의 합을 어떻게 효율적으로 구할 수 있는지를 물어보는 문제.

그리고, 진약수의 개념, 그리고 과잉수라는 것이 어떤 것인지, 그리고 또 과잉수끼리의 합을 어떻게 효율적인 경우의 수로 나타내는지를 물어보는 문제이다.

 

실제 수행시간에 제한을 두고 문제를 내면, 시간내에 동작하는 효율적인 코드를 작성하기가 꽤나 어려운 문제일 것이다.

 

일반적으로 생각할 수 있는 부분과 효율적인 코드를 항목별로 보면,

구하려는 것	일반적인 방법	효율적인 방법
n에 대한 약수/진약수의 합	- 모든 약수를 구해서 합을 구한다. - 혹은 일반적인 방법으로 소인수분해 후 약수의 합을 구한다.	- 소수를 이용해서 소인수분해후 약수의 합을 구한다.
과잉수의 합으로 표현할 수 없는 수들을 찾는다.	- 28123보다 작은 수에 대해서, 차례로 과잉수의 합으로 표현할 수 있는지 없는지 확인하면서 찾는다.	- 28123보다 작은 과잉수들을 대상으로, 가능한 모든 조합으로 합을 해보면서, 합이 되는 수를 과잉수의 합으로 표현할 수 있는 수로 체크한다.

 

전체 소스코드

---

p23.rs 

#[test]
fn test(){
    // assert_eq!(28, sigma(12)); 
    // assert_eq!(18, sigma(10));
    // assert_eq!(7, sigma(4));
    // assert_eq!(31, sigma(16));

    // assert_eq!(16, sigma_proper(12));
    // assert_eq!(284, sigma_proper(220));

    assert_eq!(4179871, answer());
}

#[cfg(test)]
//과잉수의 합으로 나타낼 수 없는 수들의 합
fn answer() -> usize{
    let n = 28123;
    let v = abundant_num(n);

    // println!("{:?}",v);

    let mut cache = vec![0; n+1];
    for i in 0..v.len(){
        for j in i..v.len(){
            let add = v[i] + v[j];
            if add <= n {cache[add]=1; }
        }
    }

    let mut sum = 0;
    for i in 1..=n{
        if cache[i] == 0 {sum += i;}
    }
    return sum;
}


#[cfg(test)]
//get all number of <= n that is not sum of two abundant_num
fn get_not_sum_of_abundant_num(n:usize) -> Vec<usize>{
    let v = abundant_num(n);

    let mut cache = vec![0; n+1];
    for i in 0..v.len(){
        for j in i..v.len(){
            let add = v[i] + v[j];
            if add <= n {cache[add]=1; }
        }
    }

    let mut v:Vec<usize> = Vec::new();
    for i in 1..=n{
        if cache[i] == 0 {v.push(i);}
    }
    return v;
}

#[cfg(test)]
//get all abundant number <= n
fn abundant_num(n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = Vec::new();
    for i in 4..=n {
        let a = sigma_proper(i);
        if a > i {
            v.push(i);
        }
    }
    return v;
}

#[cfg(test)]
//sum of all proper divisors which is sum of all divisors except n
fn sigma_proper(n:usize) -> usize{   
    let a = sigma(n); 
    return a - n;
}

#[cfg(test)]
// calculate sum of all divisios of n
// n = 12, 12=2^2 x 3, sum=(1+2+4)(1+3)=28 {1,2,3,4,6,12}
// n = 10, 10=2 x 5, sum=(1+2)(1+5)=18  {1,2,5,10}
// n = 4, 4 = 2 x 2, sum = (1+2+4) = 7 {1,2,4}
fn sigma(num:usize) -> usize{
    let mut n = num;
    let sqrt_n = (n as f64).sqrt() as usize;
    let primes = find_primes(sqrt_n);

    let mut ans = 1;
    for i in primes {
        let mut sum = 1;
        let mut ii = i;
        while n % i == 0 {  
            sum += ii;
            ii *= i;
            n /= i;
        }
        ans *= sum;
        if n == 1 {break;}
    }
    if n != 1 {ans *= 1+n; } //n=10의 경우, n=5에서 벗어남
   
    return ans;
}

#[cfg(test)]
//find all primes <= n
fn find_primes(n:usize) -> Vec<usize> {
    //1. sieve
    let mut sieve:Vec<usize> = vec![1; n+1];
    sieve[0]=0; sieve[1]=0;
    let sqrt_n = (n as f64).sqrt() as usize;
    for i in 2..=sqrt_n {
        for j in (2*i..=n).step_by(i) {
            sieve[j] = 0;
        } 
    }
    //2. primes
    let mut primes:Vec<usize> = Vec::new();
    for i in 2..sieve.len() {
        if sieve[i] == 1 {primes.push(i);}
    }
    return primes;
}

 

끝