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, …
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 …
April 25, 2023, 4:06 p.m.
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 …
April 10, 2023, 1:32 p.m.
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 …
April 10, 2023, 11:43 a.m.
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 …
March 24, 2023, 11:23 a.m.
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, …
March 13, 2023, 5:46 p.m.
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 …
March 12, 2023, 10:05 p.m.
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 …
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 …
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 …
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, …
Feb. 22, 2023, 11:22 a.m.
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 …
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 …
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 …
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 …
Jan. 19, 2023, 12:20 p.m.
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. …
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 …
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. …