튀에–모스 수열 계산기
이진수에 1이 홀수 개면 1, 짝수 개면 0인 튀에–모스 수열을 만들고 성질을 확인합니다. 같은 덩이가 세 번 연달아 나오지 않는다는 것, 그리고 이 순서로 번갈아 고르면 먼저 고르는 쪽의 이득이 줄어든다는 것을 직접 세어 보여줍니다.
튀에–모스 수열 32항
01101001100101101001011001101001
n의 2진수에 1이 홀수 개면 1입니다. 이 가운데 1이 16개입니다.
처음 열여섯 항이 나오는 과정
| n | 2진수 | 1의 개수 | t(n) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 2 | 10 | 1 | 1 |
| 3 | 11 | 2 | 0 |
| 4 | 100 | 1 | 1 |
| 5 | 101 | 2 | 0 |
| 6 | 110 | 2 | 0 |
| 7 | 111 | 3 | 1 |
| 8 | 1000 | 1 | 1 |
| 9 | 1001 | 2 | 0 |
| 10 | 1010 | 2 | 0 |
| 11 | 1011 | 3 | 1 |
| 12 | 1100 | 2 | 0 |
| 13 | 1101 | 3 | 1 |
| 14 | 1110 | 3 | 1 |
| 15 | 1111 | 4 | 0 |
0부터 2^(k+1)−1까지를 t(n) 값으로 가릅니다. 8까지.
0 ~ 7을 둘로 가른 뒤 거듭제곱의 합
| 거듭제곱 | t(n)=0 쪽 | t(n)=1 쪽 | 같은가 |
|---|---|---|---|
| 0제곱 | 4 | 4 | = |
| 1제곱 | 14 | 14 | = |
| 2제곱 | 70 | 70 | = |
| 3제곱 | 368 | 416 | ≠ |
t(n)=0인 쪽: 0, 3, 5, 6 / t(n)=1인 쪽: 1, 2, 4, 7
2제곱까지는 양쪽 합이 똑같고 3제곱에서 처음 깨집니다. 수열과는 전혀 다른 곳에서 나온 등식이라, 수열을 한 항이라도 틀리게 만들면 이 표가 바로 어긋납니다 — 그래서 이 표가 곧 검산입니다.
계산 방법
- 1항의 개수를 정하면 수열이 나옵니다.
- 2만드는 방법 세 가지가 모두 같은 답을 내는지 확인합니다.
- 3같은 덩이가 세 번 연달아 나오는 자리가 있는지 검사 결과를 봅니다.
- 4나눠 먹기 순서로 바꿔 ABBA BAAB… 를 확인합니다.
- 5프루에의 정리 표에서 몇 제곱까지 합이 같은지 봅니다.
자주 묻는 질문
자연수 n을 2진수로 적고 1의 개수가 홀수면 1, 짝수면 0을 적습니다. n = 0, 1, 2, 3…에 대해 0, 1, 1, 0, 1, 0, 0, 1…이 됩니다. 0에서 시작해 0을 01로, 1을 10으로 바꾸기를 되풀이해도 같은 수열이 나옵니다.
같은 덩이가 세 번 연달아 나오는 자리가 하나도 없다는 뜻입니다. 000이나 010101 같은 꼴이 어디에도 없습니다. 더 강하게는 같은 덩이가 두 번 나오고 그 첫 글자가 한 번 더 붙는 꼴(예: 01010)도 없습니다. 1912년 악셀 튀에가 보인 성질이고, 여기서 조합론적 단어론이라는 분야가 시작됐습니다.
둘이 번갈아 고를 때 ABAB…가 아니라 ABBA BAAB… 순서로 고르면 먼저 고르는 쪽의 이득이 크게 줄어듭니다. 이 순서가 바로 튀에–모스 수열입니다. 테니스 타이브레이크에서 서브를 1-2-2-1-1-2로 넘기는 것도 같은 꼴입니다.
0부터 2^(k+1)−1까지를 튀에–모스 값이 0인 쪽과 1인 쪽으로 가르면, 0제곱부터 k제곱까지의 합이 양쪽에서 똑같다는 정리입니다. k = 2라면 {0,3,5,6}과 {1,2,4,7}로 갈리고 개수 4 = 4, 합 14 = 14, 제곱합 70 = 70입니다. 세제곱에서 처음 깨집니다.
2진수에 1이 홀수 개인 수를 오디어스(odious), 짝수 개인 수를 이븐(evil) 수라고 부릅니다. 튀에–모스 값이 1이면 오디어스, 0이면 이븐입니다. 조합 게임 이론에서 이 구분이 승패를 가르는 자리가 있어 이름이 붙었습니다.
수열을 그대로 이진 소수로 읽은 값으로 약 0.4124540336입니다. 2진수로 0.0110100110010110…이고, 초월수임이 알려져 있습니다.
전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 만드는 방법 세 가지(비트 세기, 0→01·1→10 치환, 앞의 것 뒤에 그 반대 붙이기)가 1,024항까지 완전히 같은 답을 내는 것을 검사합니다. 원리가 다른 세 경로라 서로를 검산합니다.
- t(2n) = t(n), t(2n+1) = 1 − t(n)이라는 재귀식도 500항까지 확인합니다.
- 정답지는 프루에의 정리입니다. k = 1부터 8까지 모두 k제곱까지 양쪽 합이 같고 k+1제곱에서 처음 깨지는 것을 검사합니다. 수열과는 전혀 다른 곳에서 나온 등식이라 수열을 하나라도 틀리면 여기서 어긋납니다.
- 거듭제곱의 합은 배정밀도로 담을 수 없는 자릿수라 BigInt로 정확히 셉니다. k = 8이면 26자리까지 갑니다.
- 같은 덩이가 세 번 연달아 나오는 자리가 600항까지 하나도 없는 것, 겹침(wwx) 꼴도 400항까지 없는 것을 확인했습니다. 검사기 자체가 제대로 잡는지도 010101 같은 인공 예제로 따로 검사합니다.
- 프루에–튀에–모스 상수 0.4124540336401076을 검산값으로 고정했습니다.
- 항은 4,096개까지, 프루에 표는 k = 8(512개까지 가르기)까지 다룹니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.