심술꾸러기수 구하기

심술꾸러기 수란 2, 3, 5 의 곱으로만 이루어진 수를 말한다.

       1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 ....

와 같은 수들인데 14같은 경우는 2 x 7 이므로 심술꾸러기 수가 아니다.

문제는 n번째 심술꾸러기 수를 구하는 프로그램을 만드는 겁니다.

입력 > number : 1500 <enter>

출력 > the number is XXXXXXXX

(( 풀이 ))

심술꾸러기 수 n 은 다음의 공식으로 이루어진다.

            n = 2ⁱ * 3^j * 5^k

단순히 loop 를 돌리면

    for( int i = 0 ;....) {
        for ( int j = 0 ; ... ) {
            for( int k = 0 ; ... ) {
                    number = Math.pow(2, i)*Math.pow(3,j)*Math.pow(5, k);
                    ...
            }
        }
    }

와 같지만 위 방식은 심술꾸러기 수를 오름차순으로 찾아내지 못하기 때문에 어디까지 loop 를 돌려야할지 알 수 없다. 또한 찾아낸 수를 정렬해야하는 오버헤드가 존재한다.

여기서 제시하는 방법은 출력되는 수를 두가지로 분리해서 생각하는 것이다.
 
original number     1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18,  ....
---------------------------------------------------------------------------------------------------
2-base                               4          8,                        16, ....             32, .....
3-base                                               9                               ,  ... 27, ........
5-base                                                                               ... 25, ....          125, .....
composite             1, 2, 3,   , 5, 6,          10, 12,15,        18, .......

2-base 3-base 처럼 순수 제곱수의 집합과 compsite로 표시한 복합수의 곱으로 표시하는 것.

아래는 composite 의 경우에 존재하는 패턴을 보여준다.

 L0   [2] [3] [5]      L1  [2] [3] [5]           ...... Ln  [2]     [3]     [5]
  1     0    0   0       30   1    1   1                           n       n       n
  2     1    0   0       60   2    1   1                           n+1   n       n
  3     0    1   0       90   1    2   1                           n       n+1   n
  5     0    0   1     150   1    1   2                           n       n       n+1
  6     1    1   0     180   2    2   1                           n+1   n+1   n
10     1    0   1     300   2    1   2                           n+1   n       n+1
15     0    1   1     450   1    2   2                           n       n+1   n+1
 
2, 3, 5를 차례로 번갈아가면서 곱해나가면 오름차순으로 값을 얻어낼 수 있다. 2base, 3base, 5base 그리고 composite 형식의 네가지 값의 집합은 각각 오름차순으로 정렬되어 있기 때문에 이 값들을 하나로 정렬하는 것이 훨씬 오버헤드가 적게된다.

이 경우  n-base 들간에 서로 중복된 숫자가 없음을 증명해야 한다.

(a) 2-base 와 3-base 의 독립교차증명

두 수를 다음과 같이 정의한다.

                      m = 2ⁱ
                      n = 3^j                                            *

m = n 을 만족하는 i > 1, j > 1 인 정수 i, j 가 존재한다고 가정한다.

m은 짝수이므로 n도 짝수이다. 하지만 n은 홀수의 곱이므로 짝수가 될 수 없다.

따라서 m = n 을 만족하는 정수 i, j 는 존재하지 않는다.

(b) 2-base 와 5-base 의 독립교차 증명

두 수를 다음과 같이 정의한다.

                      m = 2ⁱ
                      n = 5^k                                            *
 
m = n 을 만족하는 i > 1, k> 1 인 자연수 i, k 가 존재한다고 가정한다.

a에서와 마찬가지로 홀수인 5의 거듭제곱은 항상 홀수이므로 가정을 만족하는 정수 i, k 는 존재하지 않는다.

(c) 3-base 와 5-base 의 독립교차 증명

두 수를 다음과 같이 정의한다.

                      m = 3^j
                      n =  5^k                                            *

m = n 을 만족하는 j > 1, k > 1 인 자연수 j, k 가 존재한다고 가정한다.

m = n 이므로

                M = 3^j/5             , N = 5^k/3

인 정수 M,N 역시 존재한다.

5^k 은 다음과 같다.

 5^k = (3+2)^k = A_k3^k-02¹ + A_k-13^k-1 2¹ +A_k-23^k-22² + .... + A₁3¹2^k-1+A₀3⁰2^k
   (  Ax = _kC_x )
 
 N = A_k3^k-12¹ + A_k-13^k-2 2¹ +A_k-23^k-22² + .... + A₁3¹2^k-1 + A₀3^-12^k

N에서  3^-12^k  는 정수가 아니므로 가정에 모순이다.

마찬가지로 M도 존재할 수 없다.

따라서 가정을 만족하는 자연수 j, k 는 존재하지 않는다.
 

(a), (b), (c)에 의해서 2-base, 3-base, 5-base 는 모두 독립교차함을 증명했다. 자, 이제 남은 일은 각각의 숫자 집합을 번갈아가며 하나씩 뽑는 일만 남았으나... 졸리므로 다음에 이어서.. -_-;