All the data you need.

Tag: Number Theory

Recognizing three-digit primes
If a three-digit number looks like it might be prime, there’s about a 2 in 3 chance that it is. To be more precise about what it means for a number to “look like a prime,” let’s say that a number is obviously composite if it is divisible by 2, …
Overpowered proof that π is transcendental
There is no polynomial with rational coefficients that evaluates to 0 at π. That is, π is a transcendental number, not an algebraic number. This post will prove this fact as a corollary of a more advanced theorem. There are proof that are more elementary and direct, but the proof …
Piranhas and prime factors
The piranha problem says an event cannot be highly correlated with a large number of independent predictors. If you have a lot of strong predictors, they must predict each other, analogous to having too many piranhas in a small body of water. The piranha problem is subtle. It can sound …
Density of safe primes
Sean Connolly asked in a comment yesterday about the density of safe primes. Safe primes are so named because Diffie-Hellman encryption systems based on such primes are safe from a particular kind of attack. More on that here. If q and p = 2q + 1 are both prime, q …
Famous constants and the Gumbel distribution
The Gumbel distribution, named after Emil Julius Gumbel (1891–1966), is important in statistics, particularly in studying the maximum of random variables. It comes up in machine learning in the so-called Gumbel-max trick. It also comes up in other applications such as in number theory. For this post, I wanted to …
Prime numbers and Taylor’s law
The previous post commented that although the digits in the decimal representation of π are not random, it is sometimes useful to think of them as random. Similarly, it is often useful to think of prime numbers as being randomly distributed. If prime numbers were samples from a random variable, …
The coupon collector problem and π
How far do you have to go down the decimal digits of π until you’ve seen all the digits 0 through 9? We can print out the first few digits of π and see that there’s no 0 until the 32nd decimal place. 3.14159265358979323846264338327950 It’s easy to verify that the …
Numbering minor league baseball teams
Last week I wrote about how to number MLB teams so that the number n told you where they are in the league hierarchy: n % 2 tells you the league, American or National n % 3 tells you the division: East, Central, or West n % 5 is unique …
John Conway’s mental factoring method and friends
There are tricks for determining whether a number is divisible by various primes, but many of these tricks have to be applied one at a time. You can make a procedure for testing divisibility by any prime p that is easier than having to carry out long division, but these …
Tree structure of Major League Baseball
The previous post took a mathematical look at the National Football League. This post will do the same for Major League Baseball. Like the NFL, MLB teams are organized into a nice tree structure, though the MLB tree is a little more complicated. There are 32 NFL teams organized into …
Divisibility by base + 1
To test whether a number is divisible by 11, add every other digit together and subtract the rest of the digits. The result is divisible by 11 if and only if the original number is divisible by 11. For example, start with n = 31425. Add 3, 4, and 5, …
Rotating multiples of 37
If a three-digit number is divisible by 37, it remains divisible by 37 if you rotate its digits. For example, 148 is divisible by 37, and so are 814 and 481. Before proving the theorem, I’ll state a couple things the theorem does not say. First of all, it does …
Pythagorean triangles with side 2023
Can a Pythagorean triangle have one size of length 2023? Yes, one possibility is a triangle with sides (2023, 6936, 7225). Where did that come from? And can we be more systematic, listing all Pythagorean triangles with a side of length 2023? Euclid’s formula generates Pythagorean triples by sticking integers …
Factoring b^n + 1
The previous post illustrated a technique for finding factors of number of the form bn – 1. This post will look at an analogous, though slightly less general, technique for numbers of the form bn + 1. There is a theorem that says that if m divides n then bm …
Factoring b^n – 1
Suppose you want to factor a number of the form bn – 1. There is a theorem that says that if m divides n then bm – 1 divides bn – 1. Let’s use this theorem to try to factor J = 22023 – 1, a 609-digit number. Factoring such …
Special primality proofs
I’ve written lately about two general ways to prove that a number is prime: Pratt certificates for moderately-large primes and elliptic curve certificates for very large primes. If you can say more about the prime you wish to certify, there may be special forms of certificates that are more efficient. …
Elliptic curve primality certificates
I’ve written recently about a simple kind of primality certificates, Pratt certificates. These certificates are easy to understand, and easy to verify, but they’re expensive to produce. In order to produce a Pratt certificate that n is a prime you have to factor n-1, and that can take a long …
Primes with two non-zero bits
Suppose a number n written in binary has two 1s and all the rest of its bits are zeros. If n is prime, then the 1s must be the first and last bits of n. The first bit is 1 because the first bit of every positive integer is 1. …