34. Digit Factorials [각 자릿수의 팩토리얼의 합과 원래 값이 같은 수 찾기]

 

 

 

 

​문제 (English)

145 is a curious number, as $1! + 4! + 5! = 1 + 24 + 120 = 145$ .

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

 

Note: As $1!=1$ and $2!=2$ are not sums they are not included.

 

Answer: 40730

문제 분석

---

어떤 수에서, 각 자릿수에 해당하는 0~9까지의 값에 대해 팩토리얼을 한 후 전부 더했을 때, 그 값이 원래 수와 같은 수를 찾으라는 문제.

 

해당 조건을 만족하는 수를 10부터 시작해서 1씩 증가시키면서 찾으면 되겠다.

그런데, 얼마까지 수를 증가시키면서 찾아야 할까? 이 부분이 문제를 푸는 키 포인트가 되겠다.

 

풀이 1 

---

얼마까지 수를 증가시키면서 찾아야 할까?

 

자릿수 관점에서 생각해 보자. 얼마만큼의 자릿수, 예를 들어 2자리인지 5자리까지 일 지를 생각해 보는 것이다.

어떤 두 자릿수 $x$라고 할 때, 이 $x$의 최댓값은 99이고, 이에 대한 팩토리얼 합은 $2 \times 9!$이다. 3자리 수 최댓값인 999에 대해서는 $3 \times 9!$

일반화를 해보면 어떤 d 자리의 수 x는 $d \cdot 9!$ 보다 작다.

$$ x \le d \cdot 9! \tag {1}$$

 

일반적으로 d 자리의 수의 범위는 아래와 같다.

$$ 10^{d-1} \le x \le 10^{d}-1 \tag {2}$$

 

식 1과 식 2를 연합해 보면,

 

$$ 10^{d-1} \le d \cdot 9! \tag {3}$$

로그를 취하면,

$$ d-1 \le log_{10}{d} + log_{10}{9!}$$

$9!=362880$이기에 $log_{10}{9!}=5.56$

따라서,

$$ d-log_{10}{d} \le 6.56 \tag {4}$$

 

식 4를 만족시키는 d의 값을 2부터 시작해서 증가시키면서 찾아보자.

d=7까지는 6.56보다 작아서 식 3을 만족하지만, d=8부터는 만족하지 않는다. 즉, 7자리 값까지만 조사해 보면 되겠다.

 

위의 유도과정을 식 3에서 굳이 로그를 취해서 계산하지 않고, 식 3에서 바로 생각해도 된다.

식 3의 의미는, 왼쪽 편의 $10^{d-1}$은 d자리 정수가 가질 수 있는 가장 작은 값을 의미하고, 오른 편의 $d \codt 9!$은 d자리의 최댓값일 때의 팩토리얼 합 값이다. 예를 들어 d=2라면 $10 \le \le factorial_sum(99)$

당연한 수식이다.

 

이 식 3을 이용해서 엑셀에서 계산해 보면, 

식 4에서 유도한 것과 동일하게 d=7일 때까지만 수식을 만족한다.

즉, 8자리의 가장 큰 수인 99999999에 대해 팩토리얼 합을 구하면 2,903,040으로 7자리 수밖에 안된다. 즉, 팩토리얼 합을 했을 때 자기 자신이 되는 수라는 조건을 8자리부터는 만족시킬 수 없는 것. 가장 큰 수라는 99999999 조차도 팩토리얼 합이 7자리이기 때문.

 

 

이제, 작성해야 할 코드를 생가해보면,

• 팩토리얼 구하는 코드를 짜야겠다. 그래야, 각 자릿수별 팩토리얼을 구할 수 있을 테니.  $\rightarrow $ fn factorial
• 각 자릿수 별 팩토리얼은, 0~9까지 10개가 전부이니, 미리 구해서 10개짜리 배열로 저장해 두고 쓰면 편하겠다. $\rightarrow$ fact_arr
• 어떤 수를 전달하면 그 수에 대한 자릿수별 팩토리얼 합을 구하는 함수 제작 $\rightarrow$ fn sum_of_factorial

팩토리얼 구하는 함수는,

fn factorial(n:u32) -> u32 {
    let mut ans:u32 = 1;
    for i in 2..=n { ans *= i;}
    return ans;
}

주의할 것은 0! = 1이라는 점

 

0~9까지의 수에 대해 팩토리얼을 구해서 배열로 리턴하는 함수 코드는,

fn get_fact_arr() -> Vec<u32> {
    let mut v:Vec<u32> = vec![1;10];
    for i in 2..=9 {v[i] = factorial(i as u32);}
    return v;
}

0! = 1, 1!=1이기에, 배열 초기값을 1로 해두고, 2부터 팩토리얼 값을 구하면 된다.

 

팩토리얼 합을 구하는 함수는,

fn sum_of_factorial(num:u32, fact_arr:&Vec<u32>) -> u32 {
    let mut sum:u32 = 0;
    let mut n = num;
    while n > 0 {
        sum += fact_arr[(n%10) as usize];
        n /= 10;
    }
    return sum;
}

n에 대해 각 자릿수 값을 구하기 위해서 쓰는 전형적인 방법은 n % 10으로 끝 자리를 구하고, n = n / 10으로 그 끝자리를 없애나가면서 구하는 것

 

파라미터로 전해진 num을 mut로 처리해서 구할 수도 있겠다. 굳이 n으로 복제해서 사용하지 않아도 됨.

 

n이 u32이고, Rust에서 배열의 인덱스는 usize 타입이라야 해서, usize로 타입 캐스팅을 해줘야 한다. 

fact_arr[(n%10) as usize]

 

작성된 전체 코드는 아래와 같고, 이와 같이 구해지는 수는,

$$ 145, 40585$$

 

구해진 수의 합은,

$$ 40730$$

풀이 2 

---

HackerRank에 있는 문제는 조금 다르다. 

원래 Euler Project의 문제는, 팩토리얼 합이 원래의 수와 같은 값을 찾는데 반해, HackerRank의 문제는, 팩토리얼 합이 원래의 수로 나눠 떨어지는 수를 찾는 것으로 조금 변형시켰다.

 

 

이 경우, 10에서 n까지의 수에 대해 조건을 만족시키는지 구하면 된다.

조건은 팩토리얼 합이 원래의 수로 나눠 떨어지는 것.

 

if sum_of_factorial(i, &fact_arr) % i == 0

 

구하는 함수 solve1의 전체 코드는,

fn solve1(n:u32)->u32{
    let mut v:Vec<u32> = Vec::new();
    let fact_arr = get_fact_arr();
    for i in 10..n {
        if sum_of_factorial(i, &fact_arr) % i == 0 {v.push(i);}
    }
    
    if v.len() > 0 { return v.into_iter().sum();}
    else {return 0; }
    
}

 

총평

---

팩토리얼만 구할 수 있으면, 주어진 문제의 조건을 그대로 코딩만 하면 되는 간단한 문제이다. 

다만 Euler Project 문제의 경우, 해당 조건을 만족하는 대상의 대는 정수를 어디까지(어느 자리까지) 조사를 해야 하는 지를 먼저 수학적으로 알아내야 하는 것이 조금 어려운 점이다.

 

전체 소스코드

---

p34.rs 

#[test]
fn test(){
    assert_eq!(40730,solve());
}

#[cfg(test)]
fn solve() -> u32{    
    let mut v:Vec<u32> = Vec::new();
    let fact_arr = get_fact_arr();
    for i in 11..9999999 {
        if sum_of_factorial(i, &fact_arr) == i {v.push(i);}
    }
    println!("{:?}",v);
    return v.into_iter().sum();
}

#[cfg(test)]
fn get_fact_arr() -> Vec<u32> {
    let mut v:Vec<u32> = vec![1;10];
    for i in 2..=9 {v[i] = factorial(i as u32);}
    return v;
}

#[cfg(test)]
fn factorial(n:u32) -> u32 {
    let mut ans:u32 = 1;
    for i in 2..=n { ans *= i;}
    return ans;
}

#[cfg(test)]
fn sum_of_factorial(num:u32, fact_arr:&Vec<u32>) -> u32 {
    let mut sum:u32 = 0;
    let mut n = num;
    while n > 0 {
        sum += fact_arr[(n%10) as usize];
        n /= 10;
    }
    return sum;
} 

//-------------------
// HackerRank
#[test]
fn test1(){
    assert_eq!(19, solve1(20));
    assert_eq!(0, solve1(10));
    assert_eq!(27093, solve1(10000));
}

#[cfg(test)]
fn solve1(n:u32)->u32{
    let mut v:Vec<u32> = Vec::new();
    let fact_arr = get_fact_arr();
    for i in 10..n {
        if sum_of_factorial(i, &fact_arr) % i == 0 {v.push(i);}
    }
    
    if v.len() > 0 { return v.into_iter().sum();}
    else {return 0; }
    
}

 

끝