본문바로가기
[오일러 프로젝트] 소수판사: 소용돌이 모양으로 나열된 숫자에서 대각선 위의 소수 비율을 구하라
수학동아 2021.08.25 09:54 조회 147

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

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

 

 

최근 막을 내린 드라마 ‘악마판사’ 본 적 있으신가요? 드라마에서는 다양한 범죄에 대해 전 국민이 투표에 참여하고 다수가 바라는 쪽으로 결론이 납니다. 하지만 이렇게 내린 결론이 진정한 정답인지 계속 생각해보게 되죠. 그렇다면 이 문제는 어떨까요? 여러 숫자가 정신없이 나열된 속에서 단 하나의 답을 찾는 순간, 저절로 외치게 될 거예요. ‘사이다!’

 

 

<오일러 프로젝트 58번>

7×7 크기의 정사각형 격자에 1부터 49까지의 자연수를 채웁니다. 이때 격자의 한가운데에 1을 놓고 시계 반대 방향으로 숫자를 적으면 아아래와 같이 자연수 소용돌이가 만들어집니다. 이 격자에서 대각선에 놓인 수 13개 중 8개가 소수이고 비율은 8/13 ≈ 62%입니다. 이런 방법으로 자연수를 써서 소용돌이를 만들 때, 대각선에 놓인 소수 비율이 10% 미만일 때는 언제일까요?

 

58번 문제를 풀기 위해서는 나선 모양의 숫자들, 특히 대각선에 있는 수자들 사이의 규칙을 찾아야 합니다. 먼저 격자 중심의 1부터 살펴보겠습니다.

 

 

1을 둘러싸는 3×3 크기의 첫 번째 정사각형을 보면, 오른쪽 위 귀퉁이부터 1에 2를 더한 3, 3에 2를 더한 5, 5에 2를 더한 7, 그리고 7에 2를 더한 9로 3, 5, 7, 9가 순서대로 있습니다. 그 다음 1을 둘러싸는 5×5 정사각형 둘레에는 3×3 정사각형의 마지막 숫자인 9에 4를 더한 13부터 13+4=17, 17+4=21, 21+4=25로 13, 17, 21, 25가 대각선 귀퉁이에 있습니다.

 

즉 1에 2를 반복해 더하면 첫 번째 정사각형의 대각선 위 숫자가 나오고, 첫 번째 정사각형의 마지막 숫자인 9에 4(=2×2)를 반복해 더하면 두 번째 정사각형의 대각선 위 숫자가 나온다는 것을 알 수 있습니다. 따라서 n번째 정사각형의 대각선 오른쪽 위 숫자를 구하려면 (n-1)번째 정사각형의 대각선 오른쪽 아래 숫자에 2n을 반복해 더합니다.

 

또 1을 중심으로 정사각형의 오른쪽 아래에 있는 대각선 위 숫자는 모두 제곱수입니다. 따라서 소수의 개수를 셀 때는 오른쪽 아래 대각선 부분은 제외합니다.

 

 

몇 가지 간단한 규칙을 코드로 만들어 대각선 위의 숫자들을 찾고, 소수가 얼마나 있는지 알아내 58번 문제를 풀어볼까요?

 

 

파이썬 완전정복! ‘나선 모양의 수열 만들고 소수 찾기’

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

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

 

1. 코드로 자연수 소용돌이 재현하기

n번째 정사각형에서 대각선 오른쪽 위의 숫자를 구하려면, (n-1)번째 정사각형의 대각선 오른쪽 아래 숫자에 2n을 반복해 더해야 합니다. 이 규칙을 이용해 1부터 N까지의 수로 만들어지는 자연수 소용돌이의 대각선에 있는 수를 찾는 코드를 알아봅시다.

 

 

2. 대각선에 놓인 숫자가 소수인지 판별하기

오일러 프로젝트 7번 문제 ‘10,001번째 소수 구하기’를 풀면서 다뤘던 소수를 판별하는 함수 is_prime(n)을 응용합니다. 1 또는 2가 아닌 자연수 n이 있을 때, 먼저 n을 2로 나눠 짝수인지 알아봅니다. 만약 짝수라면 소수가 아니므로 False를 출력하고, 홀수라면 n을 √n이하의 자연수 k로 나눠 소수인지 확인합니다. 이때 부등식 k≤√n의 양변을 제곱하면 k2≤n이 되므로, 이 조건을 만족하는 k값을 3부터 2씩 늘려가며 n이 나눠떨어지는지 확인합니다.

 

 

 

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

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

 

 

#9 58번 문제의 답을 구할 함수 e058_1()을 정의합니다.

#10 나선에 들어갈 숫자 n과 1을 둘러싸는 정사각형의 순서 k의 초깃값을 1, 대각선에 놓인 숫자 중 소수의 개수를 나타내는 p의 초깃값을 0으로 둡니다.

#11, 12, 13 n에 2k를 반복해 더하며 대각선에 놓여 있는 숫자들을 구합니다.

#14 n에 2k를 4번 더해 구해지는 오른쪽 아래의 숫자들은 모두 제곱수이므로 소수가 아닙니다. 따라서 1, 2, 3번째로 구해지는 값만 소수인지 판별하고, 소수가 나올 때마다 p에 1을 더합니다.

#15 대각선에 놓여 있는 수는 처음 1부터 시작해 k 번째 정사각형의 네 귀퉁이에 있는 수까지 모두 더해 4k+1개입니다. 58번 문제에서는 소수의 비율인 p/(4k+1)가 1/10 보다 작은 경우를 찾아야 하므로 부등식 p/(4k+1) < 1/10 을 만족해야 합니다. 분모를 양쪽에 각각 곱하면 10p < 4k+1이므로, 이 식을 만족하는 k가 나온다면 코드 실행을 멈추고 빠져나옵니다.

#16, 17, 18 정사각형의 개수 k를 늘려가며 코드를 실행하고, 조건을 만족하는 k가 나오면 정사각형의 한 변의 길이인 2k+1을 출력합니다.

 

 

BONUS 오일러 퀴즈

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

 

① 소수의 비율이 보다 작아지는 경우는 언제일까요? p/(4k+1) < 1/5를 이용해 코드를 만들어보세요.

 

② 대각선의 숫자들을 잘 살펴보면, 아래와 같은 수열이 만들어집니다. 이 수열을 이용해 문제의 답을 구할 수 있는 코드를 만들어보세요.

3, 13, 31, 57, 91, … / 5, 17, 37, 65, 101, … / 7, 21, 43, 73, 111, …

 

 

수학에는 58번 문제처럼 속 시원하게 풀 수 있는 문제도 많지만, 아직 답을 알 수 없는 문제들이 많이 있습니다. ‘수학 난제’라고 불리는 문제로, 기존에 나온 수학적인 방법에 새로운 방법을 더해 풀어야 하죠. 그래서 수학자들은 지금 이 시각에도 수학 난제를 해결하기 위한 방법과 규칙을 찾아 나름의 판결을 이어나가고 있답니다.

 

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

  • ☎문의 02-6749-3911