프로베니우스 수(맥너겟 수) 계산기
정해진 단위 몇 가지로 만들 수 없는 가장 큰 수를 구합니다. 6·9·20개들이 치킨 너겟으로 살 수 없는 최대 개수가 43이라는 문제이며, 만들 수 없는 수의 개수와 목록, 그리고 답이 아예 없는 경우인지까지 함께 판정합니다.
공백이나 쉼표로 나눠 적습니다. 8가지까지, 1 이상의 정수만.
6 · 9 · 20으로 만들 수 없는 가장 큰 수
43
44부터는 어떤 수든 만들 수 있습니다. 그 아래에서 만들 수 없는 수는 모두 22개입니다.
만들 수 없는 수
1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43
0부터 하나씩 「만들 수 있는가」를 체로 걸러 낸 목록입니다. 마지막 값이 곧 프로베니우스 수이고, 개수는 아래 나머지별 최솟값에서 계산한 값과 맞아떨어집니다 — 원리가 겹치지 않는 두 방법이 같은 답을 냅니다.
나머지별로 만들 수 있는 가장 작은 값
| 6으로 나눈 나머지 | 가장 작은 값 | 그 나머지의 최대 미달성 |
|---|---|---|
| 0 | 0 | — |
| 1 | 49 | 43 |
| 2 | 20 | 14 |
| 3 | 9 | 3 |
| 4 | 40 | 34 |
| 5 | 29 | 23 |
가장 작은 단위 6으로 나눈 나머지마다 「만들 수 있는 가장 작은 값」을 구해 두면, 거기서 6을 뺀 값이 그 나머지에서 만들 수 없는 가장 큰 수입니다. 그중 가장 큰 것이 프로베니우스 수입니다. 나머지가 같은 수들은 6씩 더해 가며 얼마든지 올라갈 수 있으므로, 한 번 만들 수 있게 되면 그 위로는 전부 만들 수 있기 때문입니다.
계산 방법
- 1단위를 공백이나 쉼표로 나눠 적습니다.
- 2만들 수 없는 가장 큰 수를 확인합니다.
- 3만들 수 없는 수의 목록에서 마지막 값이 그 답인지 봅니다.
- 4나머지별 최솟값 표에서 답이 어떻게 나오는지 확인합니다.
- 5최대공약수가 1이 아닌 단위를 넣어 왜 답이 없는지 봅니다.
자주 묻는 질문
정해진 단위 몇 가지를 몇 개든 써서 만들 수 없는 가장 큰 수입니다. 6개·9개·20개들이로만 파는 치킨 너겟이라면 43개를 살 수 없고, 44개부터는 어떤 개수든 살 수 있습니다. 그래서 이 값을 맥너겟 수라고도 부릅니다.
단위들의 최대공약수가 1이 아니면 그 배수만 만들 수 있어 나머지 수는 아무리 커도 못 만들기 때문입니다. 4와 6뿐이라면 짝수만 만들 수 있어 홀수는 영원히 못 만들고, 그러면 「가장 큰」 값이라는 것이 없습니다. 한국 동전 10·50·100·500도 최대공약수가 10이라 10원 단위가 아닌 금액은 만들 수 없습니다.
있습니다. 최대공약수가 1인 a와 b에 대해 답은 a×b − a − b이고, 만들 수 없는 수의 개수는 (a−1)(b−1)/2입니다. 3과 5라면 15 − 3 − 5 = 7이고 만들 수 없는 수는 1, 2, 4, 7의 네 개입니다.
일반 공식이 알려져 있지 않습니다. 대신 정확히 구하는 방법은 있습니다. 가장 작은 단위로 나눈 나머지마다 「만들 수 있는 가장 작은 값」을 구한 뒤 그중 최댓값에서 가장 작은 단위를 빼면 됩니다. 나머지가 같은 수들은 가장 작은 단위씩 더해 가며 얼마든지 올라갈 수 있으므로, 한 번 만들 수 있게 되면 그 위로는 전부 만들 수 있기 때문입니다.
6·9·20으로 43은 만들 수 없지만 44부터는 모두 만들 수 있기 때문입니다. 44 = 20 + 6×4, 45 = 9×5, 46 = 20×2 + 6, 47 = 20 + 9×3, 48 = 6×8, 49 = 20×2 + 9입니다. 연속한 여섯 개를 만들 수 있으면 거기에 6을 계속 더해 그 위를 모두 덮을 수 있습니다.
보는 방향이 반대입니다. 거스름돈 계산기는 주어진 금액을 어떤 동전으로 만들지를 찾고, 이 도구는 아예 만들 수 없는 수가 어디까지인지를 찾습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 단위가 둘일 때는 닫힌 식 a×b − a − b, 그리고 만들 수 없는 수의 개수 (a−1)(b−1)/2와 대조했습니다. 최대공약수가 1인 모든 짝(a는 2~40, b는 a+1~60)에서 두 값이 일치합니다.
- 셋 이상은 0부터 하나씩 「만들 수 있는가」를 체로 걸러 본 결과와 대조했습니다. 못 만드는 수의 마지막 값과 개수가 나머지별 최솟값에서 계산한 값과 같아야 하며, 아홉 가지 단위 조합에서 확인했습니다. 두 방법은 원리가 전혀 겹치지 않아 서로를 검산해 줍니다.
- 6·9·20 너겟의 43과 못 만드는 수 22개를 검산값으로 고정했고, 44부터 200까지가 모두 만들 수 있는 수인 것도 함께 확인했습니다.
- 나머지별 최솟값이 실제로 만들 수 있는 값이면서 그보다 가장 작은 단위만큼 작은 수는 만들 수 없다는 것도 검사합니다. 이것이 「최댓값에서 가장 작은 단위를 빼면 답」이라는 논리의 근거입니다.
- 최대공약수가 1이 아닌 경우와 단위에 1이 있는 경우를 「못 찾음」으로 뭉뚱그리지 않고 이유를 나눠 답합니다. 앞은 답이 아예 없는 것이고 뒤는 못 만드는 수가 하나도 없는 것이라 뜻이 정반대입니다.
- 단위는 8가지까지, 값은 100,000까지 다룹니다. 가장 작은 단위는 5,000까지입니다 — 나머지별 최솟값을 구하는 최단거리 계산의 정점 수가 곧 그 값이기 때문입니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.