Counting problems look different every time, but nearly all of them come down to two questions: does the order matter, and can the same item be picked again? This article answers both with everyday examples, each computed exactly with our combinatorics and number theory calculator, and then turns to the other half of the tool: primes, and why splitting a number into them can be so much harder than building it.
The four formulas
| Each item at most once | Items may repeat | |
|---|---|---|
| Order matters | Permutations: nPr = n! / (n − r)! | n^r |
| Order does not matter | Combinations: nCr = n! / (r! (n − r)!) | C(n + r − 1, r) |
The factorial n! = 1 × 2 × … × n counts the ways to arrange n distinct things in a row. Everything else in the table is a factorial with some arrangements removed because they should not be counted separately.
Four everyday examples
A podium. Eight runners, gold, silver and bronze. Order matters (gold is not bronze) and nobody wins two medals: 8P3 = 8 × 7 × 6 = 336.
A pizza. Choose 3 different toppings from 10. Order does not matter (ham-mushroom-olive is the same pizza as olive-ham-mushroom): C(10, 3) = 10 × 9 × 8 ÷ 3! = 720 ÷ 6 = 120. If the shop lets you pick a topping twice ("double cheese"), it becomes a combination with repetition: C(10 + 3 − 1, 3) = C(12, 3) = 220.
A code. A 4-character code from 26 letters, repeats allowed, order matters: 26⁴ = 456,976. A 4-digit PIN: 10⁴ = 10,000. That is why a 4-digit PIN relies on a limited number of attempts, not on the number of possibilities.
A lottery. A Mega 6/45 ticket picks 6 different numbers from 45 and the order of the draw does not matter: C(45, 6) = 8,145,060. A 6/55 game: C(55, 6) = 28,989,675. Every combination is equally likely, including 1-2-3-4-5-6.
A useful check: nPr = nCr × r!. The 120 topping sets, each arranged in 3! = 6 orders, give 720 = 10P3.
How fast these numbers grow
Factorials outgrow everything familiar. 21! = 51,090,942,171,709,440,000 already exceeds the range of a 64-bit integer, and 52!, the number of ways to shuffle a deck, has 68 digits: any well-shuffled deck is almost certainly in an order no deck has been in before. The calculator works with exact whole numbers of any length, so it can show all 35,660 digits of 10,000! where an ordinary calculator would show an overflow or a rounded "2.846 × 10³⁵⁶⁵⁹".
Primes: easy to multiply, hard to split
Now the other direction. Take two primes, 1,000,000,007 and 1,000,000,009. Multiplying them takes a moment by hand: 1,000,000,016,000,000,063. Going back, finding the two primes from the product, is the factoring problem.
The naive method, trial division, tries every possible divisor up to the square root. For our 19-digit product that is about a billion candidates. The calculator instead uses Pollard's rho, a clever random walk that finds a prime factor p in about √p steps: roughly 30,000 steps here, which is why it factors this number instantly.
Now scale it up. The work grows with the size of the smallest prime factor:
| Smallest prime factor | Rough steps for Pollard's rho (√p) |
|---|---|
| 10 digits | 100,000 |
| 20 digits | 10,000,000,000 |
| 40 digits | 10²⁰ |
| 300 digits | 10¹⁵⁰ |
With two 20-digit primes, the calculator's two-second budget runs out and it shows the unfactored part in brackets. Specialised algorithms do far better than rho (the general number field sieve is the record holder; RSA-250, an 829-bit number of 250 digits, was factored in 2020 after thousands of core-years of computing), but every known method on ordinary computers still takes impractically long for numbers of 600 digits and more.
The RSA intuition
RSA encryption is built on exactly this asymmetry. Someone picks two large random primes p and q, publishes their product n = p × q, and keeps p and q secret. Encrypting uses only n and a public exponent, with a modular power: c = mᵉ mod n. Decrypting needs a private exponent d, the modular inverse of e modulo (p − 1)(q − 1), and computing (p − 1)(q − 1) requires knowing p and q. Anyone who could factor n could compute d.
You can try the building blocks in the calculator's GCD and modular tab: 4¹³ mod 497 = 445 is a toy "encryption", and 3⁻¹ mod 11 = 4 is a toy inverse, found with the extended Euclidean algorithm. Real keys use the same operations on numbers hundreds of digits long. Choosing the primes needs fast primality tests: the calculator's Miller–Rabin test is proven exact below 3.3 × 10²⁴, and beyond that the Baillie–PSW test has no known counterexample.
This is an intuition, not a recipe: real RSA also needs padding, careful key generation and constant-time code. Never build your own encryption for real data.
Common mistakes
- Using a permutation when order does not matter. Choosing a 3-person committee from 10 is C(10, 3) = 120, not 10P3 = 720.
- Forgetting repetition. Ice-cream scoops where flavours may repeat are combinations with repetition, not plain combinations.
- Multiplying probabilities from different formulas. Use one model for the whole problem: if the outcomes are combinations, count favourable combinations too.
- Trusting floating-point for big counts. A spreadsheet's COMBIN on large n rounds silently; exact BigInt arithmetic does not.
- Thinking "probable prime" means "possibly composite in practice". For Baillie–PSW, no counterexample has ever been found; still, it is not a proof.
- Concluding a number is prime because factoring failed. A timeout means "not factored in time", not "prime": the primality test is the one that decides.
For working with the results of experiments rather than counting them, the statistics calculator computes means, spreads and binomial probabilities.