All the data you need.

## Tag: Number Theory

Density of square-free numbers, cube-free numbers, etc.
An integer n is said to be square-free if no perfect square (other than 1) divides n. Similarly, n is said to be cube-free if no perfect cube (other than 1) divides n. In general, n is said to be k-free if it has no divisor d > 1 where …
Digitally delicate primes
A digitally delicate prime is a prime number such that if any of its digits are changed by any amount, the result is not prime. The smallest such number is 294001. This means that variations on this number such as 394001 or 291001 or 294081 are all composite. A recently …
Refinements to the prime number theorem
Let π(x) be the number of primes less than x. The simplest form of the prime number theorem says that π(x) is asymptotically equal to x/log(x), where log means natural logarithm. That is, This means that in the limit as x goes to infinity, the relative error in approximating π(x) …
The smallest number with a given number of divisors
Suppose you want to find the smallest number with 5 divisors. After thinking about it a little you might come up with 16, because 16 = 24 and the divisors of 16 are 2k where k = 0, 1, 2, 3, or 4. This approach generalizes: For any prime q, …
Test for divisibility by 13
There are simple rules for telling whether a number is divisible by 2, 3, 4, 5, and 6. A number is divisible by 2 if its last digit is divisible by 2. A number is divisible by 3 if the sum of its digits is divisible by 3. A number …
At the next prime, turn left
The previous post mentioned a Math Overflow question about unexpected mathematical images, and reproduced one that looks like field grass. This post reproduces another set of images from that post. Start anywhere in the complex plane with integer coordinates and walk west one unit at a time until you run …
Sum of divisor powers
The function σk takes an integer n and returns the sum of the kth powers of divisors of n. For example, the divisors of 14 are 1, 2, 4, 7, and 14. If we set k = 3 we get σ3(n) = 1³ + 2³ + 4³ + 7³ + …
An almost integer pattern in many bases
A few days ago I mentioned a passing comment in video by Richard Boucherds. This post picks up on another off-hand remark from that post. Boucherds was discussing why exp(π √67) and exp(π √163) are nearly an integer. exp(π √67) = 147197952744 – ε1 exp(π √163) = 262537412640768744 – ε2 …
Continued fractions with period 1
A while back I wrote about continued fractions of square roots. That post cited a theorem that if d is not a perfect square, then the continued fraction representation of d is periodic. The period consists of a palindrome followed by 2⌊√d⌋. See that post for details and examples. One …
A bevy of ones
Take any positive integer d that is not a multiple of 2 or 5. Then there is some integer k such that d × k has only 1’s in its decimal representation. For example, take d = 13. We have 13 × 8457 = 111111. Or if we take d …
Binomial coefficients mod primes
Imagine seeing the following calculation: The correct result is and so the first calculation is off by 25 orders of magnitude. But there’s a variation on the calculation above that is correct! A theorem by Édouard Lucas from 1872 that says for p prime and for any nonnegative integers m …
Bit flipping to primes
Someone asked an interesting question on MathOverflow: given an odd number, can you always flip a bit in its binary representation to make it prime? It turns out the answer is no, but apparently it is very often the case an odd number is just a bit flip away from …
Square roots of Gaussian integers
In previous post I showed how to compute the square root of a complex number. I gave as an example that computed the square root of 5 + 12i to be 3 + 2i. (Of course complex numbers have two square roots, but for convenience I’ll speak of the output …
How probable is a probable prime?
A probable prime is a number that passes a test that all primes pass and that most composite numbers fail. Specifically, a Fermat probable prime is a number that passes Fermat’s primality test. Fermat’s test is the most commonly used, so that’s nearly always what anyone means by probable prime …
Relatively prime determinants
Suppose you fill two n×n matrices with random integers. What is the probability that the determinants of the two matrices are relatively prime? By “random integers” we mean that the integers are chosen from a finite interval, and we take the limit as the size of the interval grows to …
Prime plus power of 2
A new article  looks at the problem of determining the proportion of odd numbers that can be written as a power of 2 and a prime. A. de Polignac conjectured in 1849 that all odd numbers have this form. An immediate counterexample is 3, and so apparently the conjecture …
Powers that don’t change the last digit
If you raise any number to the fifth power, the last digit doesn’t change. Here’s a little Python code to verify this claim. >>> [n**5 for n in range(10)] [0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049] In case you’re not familiar with Python, or familiar with Python …
Various kinds of pseudoprimes
Every condition that all primes satisfy has a corresponding primality test and corresponding class of pseudoprimes. The most famous example is Fermat’s little theorem. That theorem says that for all primes p, a certain congruence holds. The corresponding notion of pseudoprime is a composite number that also satisfies Fermat’s congruence. …