정수 분할 계산기

자연수 n을 순서를 따지지 않고 자연수 몇 개의 합으로 쪼개는 것입니다. 4는 4, 3+1, 2+2, 2+1+1, 1+1+1+1로 정확히 5가지(p(4)=5)로 쪼갤 수 있습니다. 3+1과 1+3은 순서만 다를 뿐 같은 분할로 셉니다 — 순서를 따지면 다른 문제(구성, composition)가 됩니다.

거스름돈 문제와 같은 동적계획법을 씁니다. 부분(part)으로 쓸 수 있는 크기를 1부터 n까지 하나씩 허용해 가며, 지금까지 허용한 크기들만으로 각 금액을 만드는 방법의 수를 누적합니다. n이 커지면 나열은 불가능해도 이 표는 순식간에 정확한 값을 냅니다.

동적계획법과는 완전히 다른 증명(오각수 정리)에서 나온 부호 있는 재귀식으로도 같은 값을 한 번 더 계산해 맞춰 봤습니다. 서로 다른 두 경로에서 독립적으로 나온 값이 일치하면, 어느 한쪽 구현에 실수가 있어도 우연히 같은 값이 나올 가능성이 낮아 더 믿을 수 있습니다.

분할의 개수 자체가 빠르게 늘어나기 때문입니다. p(10)=42지만 p(50)은 벌써 204,226이라 다 나열하면 브라우저가 버벅입니다. 그래서 목록은 n이 12 이하일 때만 보여주고, 그보다 크면 개수(p(n))만 정확히 계산해 보여줍니다.

분할은 순서를 따지지 않는 합이고(3+1과 1+3이 같음), «구성(composition)»이라 부르는 것은 순서를 따지는 합입니다(3+1과 1+3을 다르게 셈). n을 순서까지 따져 자연수의 합으로 쪼개는 방법은 2ⁿ⁻¹가지로 훨씬 간단한 식이 되는데, 이 계산기가 다루는 것은 그보다 훨씬 복잡한 «순서 무시» 쪽입니다.

아니요. 모든 계산은 브라우저 안에서만 이뤄지며 서버로 전송되지 않습니다.