본문바로가기
[오일러 프로젝트] 심야수학괴담회: 아무리 곱하고 더해도 같은 수가 나오는 무서운 수열
수학동아 2021.07.28 16:01 조회 198

 

코.알.못 홍 기자의 코딩 도전기

코딩(프로그래밍)의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갑니다. 오일러 프로젝트는 수학과 코딩 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트입니다. 홍 기자와 함께한다면 수학과 코딩 언어의 하나인 파이썬 모두 정복할 수 있지 않을까요?

 

 

더위에 잠 못 드는 밤.

당신을 시원하다 못해 오싹하게 할 ‘심야(수학)괴담회’에 오신 것을 환영합니다.

이번에는 특별히 수학과 관련된 무서운 이야기를 준비했어요.

어떤 수로 시작해도 마지막은 항상 단 두 개의 수로만 끝나는 이상한 수열이 있다고 합니다.

흐흐흐, 궁금하지 않나요…?

 

 

<오일러 프로젝트 92번>

어떤 자연수의 각 자릿수를 제곱해서 모두 더한 값을 반복해 나열하는 수열을 살펴봅시다. 전에 나왔던 수가 다시 나올 때까지 수를 나열하면 신기하게도 어떤 자연수로 수열을 시작하든지 1이나 89로 끝나는데요, 그렇다면 1000만 미만의 자연수 중에 위의 계산을 거쳐 89에 도달하는 수는 몇 개일까요?

 

 

44와 89로 시작하는 수열을 살펴보겠습니다.

 

 

이처럼 92번 문제의 수열은 어떤 자연수를 골라 시작해도 항상 끝은 1 또는 89로 끝납니다. 정말 신기한 수열이죠? 그럼 이 수열을 코드로 직접 만들어보고, 92번 문제의 답을 찾아보겠습니다!

 

 

파이썬 완전정복! '코드로 수열 예상하기’

92번 문제를 해결하는 데 필요한 파이썬 명령어입니다.

꿀팁 중의 꿀팁, 밑줄 쫙! 핵심만 소개하니 꼭 익혀두세요!

 

1. 수열의 규칙을 코드로 나타내기

92번 문제의 수열은 자연수의 각 자릿수를 제곱해 더하는 방식으로 다음 수를 구합니다. 따라서 어떤 자연수가 주어지면, 그 자연수의 각 자릿수에 해당하는 숫자를 찾을 수 있어야 합니다. 이번에는 주어진 수를 10으로 나눈 몫과 나머지를 구해 자릿수를 찾아보겠습니다.

예를 들어 12345를 10으로 나눈 나머지는 5이고 몫은 1234입니다. 따라서 일의 자릿수는 5이고, 이때 나온 몫을 다시 10으로 나누면 나머지는 4, 몫은 123이지요. 따라서 십의 자릿수는 4임을 알 수 있습니다. 이렇듯 자연수 n을 10으로 계속 나눌 때 나오는 나머지가 자릿수입니다. 이렇게 구한 자릿수를 각각 제곱해 더하면 다음 수 s를 구할 수 있습니다.

 

 

 

2. 수열의 마지막 숫자가 1인지 89인지 알아보기

코드로 수열을 나타냈으니, 이번엔 수열의 마지막 수가 1 또는 89인지 알아볼 차례입니다. 수열 중간에 1이나 89가 나오면 무조건 마지막 값이 1 또는 89이기 때문에 sq_digit(n) 함수로 1부터 1000만 미만까지 자연수 자릿수 제곱의 합을 계속 구하고, 그중에 1 또는 89가 있는지 검사하는 코드를 만듭니다.

 

 

 

도전! 오일러 프로젝트 92번 문제 뽀개기

* 코딩 언어는 Python으로 두고 실행하세요!

 

 

#11 앞서 정의한 sq_digit(n), num_chain_0(n) 함수를 이용해 92번 문제의 답을 얻을 수 있는 함수 e092(N)을 정의합니다.

#12 89로 끝나는 경우의 수를 변수 cnt로 두고, 초깃값을 0으로 설정합니다.

#13 1 이상 N 미만의 자연수 i에 대해 아래의 코드를 실행합니다.

#14, 15 자연수 i부터 시작한 수열의 값 중 89가 나오면 cnt에 1을 더합니다.

#16 1 이상 N 미만의 자연수에 대해 코드를 실행했다면 계산을 멈추고 최종 cnt 값을 돌려줍니다.

#17 N이 1000만일 때 e092(N)을 실행해 답을 얻습니다.

 

 

BONUS 오일러 퀴즈

오일러 프로젝트 92번 문제를 풀어보고, 다음 예제 문제에도 도전해보세요!

 

① 92번 문제를 푸는 전체 코드를 응용해 수열의 마지막 값이 1인 경우의 수를 세보세요. 그리고 89가 나오는 경우의 수와 더해 1000만 미만의 수로 시작한 수열 모두가 1 또는 89로 끝나는지 확인해보세요.

Hint ‘if num_chain_0(i) == 89’에서 숫자를 바꿔 실행해보세요.

 

② 실제로 코드를 실행해보면 꽤 오랜 시간이 걸리는 것을 알 수 있습니다. 계산 시간을 줄이기 위해서는 어떤 방법을 사용할 수 있을지 생각해보세요. 정답은 8월 말, 폴리매스 홈페이지에 올려둘게요!

 

  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911