어느 수를 10진 기수법으로 써 놓고 왼쪽에서 오른쪽으로 읽으면서, 어느 자릿수의 숫자라도 그 왼쪽에 있는 숫자를 초과하지 않으면 그 수는 감소하는 수이다. 반대로, 항상 같거나 크다면 그 수는 증가하는 수이다.
증가하지도 않고 감소하지도 않는 수는 bouncy number라고 한다.
10^6이하의 수 중에는 12951개의 bouncy number가 있고, 10^10이하의 수 중에는 277032개가 있다고 한다.
구골(10^100)이하의 수 중에는 몇개의 bouncy number가 있는가?
출처 http://projecteuler.net/problem=113
풀어보자.
1.
우선, 어떤 양의 정수 N보다 작은 bouncy number의 수를 B(N)라 하고, increasing number의 수를 I(N), decreasing number의 수를 D(N)라고 하자. 임의의 양의 정수 N에 대하여, N=B(N)+D(N)+I(N)가 성립한다. N, B, D, I의 정의에 의해 당연하다.
2.
예를 들어, n자리수의 increasing number의 수를 I[n]이라고 하자. 그럼 n자리수인 양의 정수 N에 대하여, N이하의 increasing number의 수 I(N)은 I(N)=I[0]+I[1]+I[2]+…+I[n] 이다.
이 사실은 I가 아니라 D에 대해서도 성립한다.
즉, D(N) = D[0]+D[1]+…+D[n] 이다.
3.
어떤 양의 정수 n(n>3)에 대하여 I[n]이 알려져 있다고 하자.
I[n+1] = ??
어떤 점화식이 존재할 것이다.
4.
I에 대한 3의 내용을 D에 대해서도 마찬가지로 증명할 수 있다.
5.
1, 2, 3, 4를 정리하면 B(10^100)을 계산할 수 있다.
*혼자 풀고 있는 중입니다.
