자연수 n에 대해서, f(n)을 n의 모든 자리수의 숫자들의 제곱의 합이라고 정의하자.

예를 들어 n=19이면, f(19) = 1² + 9² = 82이다.

이 f를 계속 적용시켜 나가다 보면, 어떤 수들은 결국에 1이 된다. 이런 수들을 그뤠잇 넘버라고 한다. 예컨대, 19는 그뤠잇 넘버이다. 다음을 보면 그 이유를 알 수 있다.

f(19) = 1² + 9² = 82

f(82) = 8² + 2² = 68

f(68) = 6² + 8² = 100

f(100) = 1² + 0² + 0² = 1

모든 자연수들이 그뤠잇 넘버이진 않다. 실은, 수학자들이 이미 자연수 n가 그뤠잇 넘버가 아니면, 어떤 주기를 가지고 순환한다는 것을 증명해 놨다. 예를 들면 다음과 같다.

4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> …

n이 주어졌을 때, n이 그뤠잇 넘버인지 아닌지 알아내는 프로그램을 작성하라.

그뤠잇 넘버 timer 1s memory 128MB

그뤠잇 넘버 1s 128MB