프로젝트 오일러 92번

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

-------------------------------------------------------------------------------

다음의 수열은 이전 항의 자릿수 제곱의 합이 다음 항이 되는 수열이다.

예를 들어, \(44\) 의 다음 항은 \(4^2 + 4^2 =32\) 로 만들고, 또 다시 다음 항은 \(3^2 + 2^2 = 13\) 과 같은 방식으로 만들어 나간다.

이렇게 항들을 만들어 나가면서 이전에 나왔던 항이 또 다시 나오게 되면 더 이상의 항을 만들지 않고 멈춘다.

예를 들어, 다음과 같이 1이 또다시 나오거나 혹은 89가 또다시 나오게 되면 더 이상의 항을 만들지 않고 멈추게 된다. 

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
놀라운 사실은 첫 번째 항을 얼마로 하든지 결국 1이나 89라는 숫자를 만나게 된다는 것이다. 

\(10^7\) 미만의 수들을 첫 째항으로 하여 위와 같이 항들을 만들어 나갈 때, 89에 도달하게 되는 수는 몇 개나 있을까?

 

처음에 이 문제를 풀때는 그냥 1부터 천만까지 루프를 이용하여 happy number인지 아닌지를 확인했다.(happy number 란 각 자리의 숫자들 제곱의 합이 결국 1에 도달하는 숫자들이다.) 물론 코딩은 쉬웠지만 무려 4분을 넘게 기다려야 답이 나왔다. 뭔가 더 좋은 방법을 고민하다가 happy number의 체크리스트를 만들고, unhappy number(happy number 가 아닌수)의 체크리스트를 만들어, 새로 확인하려는 숫자가 이 두 리스트 중 어디에 있는지 확인하는 방식으로 접근해 보기도 했지만, 리스트 안에 어떤 수가 있는지 있는지 없는지 확인하는데에도 시간이 적지 않게 소모되는 것을 확인하고 포기하였다.

또한 같은 것이 있는 순열을 이용하여 접근해 보기도 했다. 예를 들어, 11234가 happy number이기 때문에 11234로 만들 수 있는 모든 순열은 모두 happy number가 되기 때문에 이를 모두 제외하는 방식으로 접근하는 것이다. 이것도 시간이 만나치 않게 걸리는 것으로 확인이 되었다.

결국 써치 끝에 찾아낸 가장 나이스한 방법이 Dreamshire 에서 본 방법이다. 이분 이 문제들을 어떻게 푸시는지 모르겠지만, 100만년이 지나도 나는 이 분을 따라가지 못할 것 같다. 정말 그 접근방법이 놀랍다. 그래서 그분의 방법을 소개해 보기로 한다.

--------------------------------------

가장 중요한 차이점은 역방향으로 접근한다는 것이다.

천만은 \(10^7\) 이고, \(1~10^7\) 까지 각 자리의 제곱들의 합은 \(9,999,999\) 일 때 최댓값 \(9^2 \times 7=567\) 을 갖는다.

각 자리 숫자들 제곱의 합이 \(1\sim 567\) 이 되는 수가 몇 개가 있는지를 카운트하는 방법이다.

천만까지 보기는 너무 힘들기 때문에 일단 100까지 보는 것으로 하여 방법을 익혀보자.

 

\(1~100\)까지 각 자리 숫자들의 제곱의 합이 가질 수 있는 최댓값은 \(9^2 \times 2 =162\) 가 된다. 일단 그 합이 \(0\)이 되는 경우까지 가정하여 길이가 \(163\)인 배열을 하나 만든다. (합이 \(0\)이 되는 경우가 왜 필요한지는 조금 후에 알게 된다.) 그 배열을 \(\rm arr\)라고 한다면 \(\rm arr\)의 모든 칸을 \(0\)으로 채운다.

 

제일 먼저 한 자리 자연수들의 제곱의 합을 체크하여 해당 칸에 값을 1씩 증가시키는 것이다.

따라서 \[\rm arr[0]=1,\; arr[1]=1, \;arr[4]=1, \;arr[9]=1, \; arr[16]=1,\;\] \[\rm arr[25]=1, \;arr[36]=1,\; arr[49]=1,\; arr[64]=1, \;arr[81]=1\] 이 된다. \(\rm  arr[0]=1\)을 만드는 이유는 조금 후에 알게 된다.

 

이제 두 자리 자연수까지의 각 자리 숫자 제곱의 합을 구하여 \(\rm arr\)의 해당 칸의 값을 \(1\)씩 증가시킨다.

십의 자리에 올 수 있는 수는 \(1\) 부터 \(9\) 까지의 수이므로 십의 자리가 \(1 \sim 9\)일때를 나눠서 계산한다.

예를 들어, 두 자리 자연수 각 자리의 숫자 제곱의 합이 \(1\)이 되는 경우는 몇 가지가 있을까?

십의 자리 숫자가 \(1\)이라면 일의 자리 숫자가 \(0\)이 되어야만 각 자리 숫자 제곱의 합이 \(1\)이 되는 것을 알 수 있다.

따라서 새로운 \(\rm arr[1]=arr[1]+arr[1-1^2]\) 가 된다. 우변의 \(\rm arr[1]\) 은 한 자리에서 수에서 그 합이 \(1\) 이 되는 경우이고, \(\rm arr[1-1^2]\)은 두 자리 수에서 그 합이 \(1\) 이 되는 경우이다. 후자의 경우 \(10\)이 해당되는데, 이것을 카운트 하기 위해 이전 단계에서 \(\rm arr[0]\) 에 \(1\)을 채워 넣은 것이다.

만약 두 자리 수까지 각 자리 숫자 제곱의 합이 \(5\) 가 되는 경우는 몇 개 있을까?

십의 자리 수가 \(1\) 인 경우 일의 자리 수 제곱이 \(4\)가 되어야 하고, 십의 자리 수가 \(2\) 라면 일의 자리 수 제곱이 \(1\)이 되어야 한다. 따라서 \(\rm arr[5]=arr[5]+arr[5-1^2]+arr[5-2^2]\) 이 되는 것이다. 따라서 \(\rm arr[5]=0+1+1=2\)가 된다. 실제로 두 자리 수까지 각 자리 숫자 제곱의 합이 \(5\) 가 되는 수는 \(12, 21\) 두 개가 있다는 것을 알 수 있다.

 

이런식으로 백만 자리 수까지 계속 반복하여 얻은 \(\rm arr\) 에 대해서 마지막으로 \(\rm arr\) 의 인덱스가 unhappy number인 경우만을 다 더하면 우리가 구하고자 하는 수가 된다. 이렇게 하면 1초도 되기 전에 답을 구할 수가 있다.

 

원래 원칙은 답은 제공하지 않고 힌트만 제공하지만 오늘 받은 충격을 고려할 때, 다른 분들도 나와 비슷한 고민을 하지 않을까 하는 생각에 이번 문제는 소스코드까지 공개하기로 한다. 물론 내가 코딩한 것은 아니고 위에서 소개한 훌륭하신 분이 코딩한 것을 python 3 버전으로 살짝 번형하였다. (그 분께서 python 2.7을 사용하시는 관계로)

 

def sqsum(n):
	total=0
	temp=list(str(n))
	for i in temp:
		total+=int(i)**2
	return total

def unhappy(n):
	while n>1 and n!=89 and n!=4:
		n=sqsum(n)
	return n>1

L=2
Lc=9**2*L+1	
t=[0]*Lc
solutions=[0]*Lc
for i in range(10):
	solutions[i*i]=1
print(solutions)
for i in range(2, L+1):
	for j in range(Lc):
		t[j]=sum(solutions[j-k*k] for k in range(10) if k*k<=j)
		print(t)
	solutions=list(t)
	print(solutions)
	

print(sum(solutions[i] for i in range(1, Lc) if unhappy(i)))

 

정말 아름답다