모세르-드 브루인 수열 생성기 | 4의 거듭제곱 계산기

모저-드 브루인 수열이란?

모저-드 브루인 수열은 각각 서로 다른 4의 거듭제곱의 합으로 나타낼 수 있는 정수의 목록이다. 수열은 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85로 시작하며 끝없이 계속된다. 수학자 레오 모저와 니콜라스 호베르트 드 브루인의 이름을 딴 것이다. 정수 수열 온라인 백과사전에서는 A000695로 분류된다.

어떤 수가 이 수열에 속하는 것은 그 수의 4진법 표현이 0과 1이라는 숫자만 사용하고, 2나 3은 전혀 사용하지 않을 때뿐이다. 예를 들어 21을 4진법으로 나타내면 111이므로 수열에 속한다. 22를 4진법으로 나타내면 112이므로 수열에 속하지 않는다.

모저-드 브루인 수열의 공식

이 수열은 서로 동치인 세 가지 방법으로 정의할 수 있다.

서로 다른 4의 거듭제곱의 합

어떤 정수 n이 다음과 같이 나타낼 수 있다면 그 수는 수열에 속한다.

$n = \sum_{i \in S} 4^i$

여기서 S는 음이 아닌 정수들의 집합이며, 4의 각 거듭제곱은 최대 한 번만 사용된다.

4진법 숫자 판정

수를 4진법으로 나타낸다. 모든 숫자가 0 또는 1이면 그 수는 수열에 속한다. 숫자 중 하나라도 2 또는 3이면 속하지 않는다.

이진수에서 4진법으로의 치환

n = 0부터 항을 세면, n번째 항은 다음과 같다.

$M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$

여기서 $b_i$는 n의 이진 숫자들이다. 말로 하면 n을 이진법으로 나타낸 뒤, 각 이진 숫자를 같은 위치의 4진법 숫자로 읽는다. 생성기는 비트를 확인하고 수를 더하기만 하면 되므로 이 방법을 사용한다.

n번째 항을 계산하는 방법

M(n)을 구하기 위해 생성기는 n = 0부터 시작하여 각 인덱스 n에 대해 다음을 수행한다.

1. n의 이진 표현을 확인한다.
2. 위치 j에서 1인 모든 비트에 대해 4^j를 누적 합계에 더한다.
3. 0인 비트는 건너뛴다.
4. 누적 합계가 M(n)이다.

계산 예시: M(5)

• 5를 이진법으로 나타내면 101이다.
• 비트 0(가장 오른쪽)은 1이므로 4⁰ = 1을 더한다.
• 비트 1은 0이므로 아무것도 더하지 않는다.
• 비트 2는 1이므로 4² = 16을 더한다.
• 합계: 1 + 16 = 17.

따라서 M(5) = 17이다. 계수는 M(0)부터 시작하므로 생성기가 만들어 내는 여섯 번째 값이다.

예시: 처음 32개 항

어떤 수가 수열에 속하는지 확인하는 방법

수를 4진법으로 변환한 뒤 숫자들을 읽는다.

• 85: 4진법에서 85는 1111이다(64 + 16 + 4 + 1). 0과 1만 나타나므로 85는 수열에 속한다.
• 90: 4진법에서 90은 1122이다. 2가 포함되어 있으므로 90은 수열에 속하지 않는다.

증가율

인덱스에 비트가 하나 추가될 때 더해지는 값이 대략 네 배가 될 수 있으므로 수열은 빠르게 증가한다. M(19)은 261이다. M(99)은 5,125이다. 이 생성기가 만들 수 있는 가장 큰 항인 M(999)은 349,205이다. 인덱스가 커질수록 항 사이의 간격도 계속 커지므로 수열은 희소하다. 무한히 많은 항이 있지만 대부분의 정수는 수열에 나타나지 않는다.

모저-드 브루인 수열 생성기 사용 방법

1. 생성할 항의 개수를 입력한다. 비워 두면 기본값은 20이다.
2. 항의 목록은 M(0)부터 시작하여 자동으로 갱신된다.
3. 결과 복사 버튼으로 전체 목록을 복사한다.

이 도구는 1부터 1000까지의 정수를 허용한다. 소수, 음수, 숫자가 아닌 입력은 거부된다. 20개 항을 요청하면 M(0)부터 M(19)까지 반환되며, 마지막으로 표시되는 값은 261이다. 모든 계산은 브라우저에서 수행되므로 결과가 즉시 나타나고 서버로 데이터가 전송되지 않는다.

관련 수열

• 2의 거듭제곱 (OEIS A000079): 1, 2, 4, 8, 16, 32 등이다. 이는 일반적인 이진수의 구성 요소다.
• 서로 다른 3의 거듭제곱의 합 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13 등이다. 모저-드 브루인 수열과 같은 개념이지만, 4진법 대신 3진법으로 구성된다.
• 피보나치 이진 숫자 (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10 등이다. 이진 표현에 서로 이웃한 1이 두 개 연속으로 나타나지 않는 수다.

역사

레오 모저(1921-1970)는 정수론, 조합론, 기하학을 연구한 오스트리아계 캐나다인 수학자였다. 니콜라스 호베르트 드 브루인(1918-2012)은 조합론, 그래프 이론, 컴퓨터 과학 분야의 연구로 알려진 네덜란드 수학자였으며, 그의 연구와 무관한 드 브루인 수열은 부호 이론에서 널리 사용된다. 두 사람 모두 덧셈 기저를 연구했다. 덧셈 기저는 4의 거듭제곱과 같이, 표현 가능한 모든 수가 정확히 하나의 합 표현을 갖도록 하는 정수 집합이다. 두 사람의 이름을 딴 수열은 이러한 기저의 한 예다.

자주 묻는 질문

모저-드 브루인 수열은 어디에 사용되는가?

이 수열은 가법적 정수론과 조합론, 특히 합 자유 집합과 덧셈 기저 연구에서 등장한다. 컴퓨터 과학에서는 진법 변환과 비트 단위 연산을 가르치는 데에도 사용된다.

모저-드 브루인 수열은 어떻게 생성하는가?

인덱스 n을 이진법으로 나타낸 다음, 각 이진 숫자를 같은 위치의 4진법 숫자로 읽는다. n = 5(이진수 101)이면 4² + 4⁰ = 17이 된다.

어떤 수가 수열에 속하는지 어떻게 확인할 수 있는가?

그 수를 4진법으로 변환한다. 모든 숫자가 0 또는 1이면 수열에 속한다. 숫자 중 하나라도 2 또는 3이면 속하지 않는다.

n번째 항의 공식은 무엇인가?

M(n) = 모든 i에 대한 $b_i \cdot 4^i$의 합이며, 여기서 $b_i$는 n의 이진 숫자다.

수열은 무한한가?

그렇다. 항은 무한히 많지만 n이 커질수록 항 사이의 간격이 더 커진다.

이진수와 어떻게 다른가?

이진수, 즉 서로 다른 2의 거듭제곱의 합은 모든 음이 아닌 정수를 나타낼 수 있다. 모저-드 브루인 수열은 대신 4의 거듭제곱을 사용하므로 대부분의 정수가 빠진다.