증가/감소 숫자


10진수로 하자.

어느 수를 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)을 계산할 수 있다.

*혼자 풀고 있는 중입니다.


댓글 남기기

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.

%d 블로거가 이것을 좋아합니다: