All the data you need.

Tag: Number Theory

Divisibility by any prime
Here is a general approach to determining whether a number is divisible by a prime. I’ll start with a couple examples before I state the general rule. This method is documented in [1]. First example: Is 2759 divisible by 31? Yes, because and 0 is divisible by 31. Is 75273 …
Sums of consecutive reciprocals
The sum of the reciprocals of consecutive integers is never an integer. That is, for all positive integers m and n with n ≥ m, the sum is never an integer. This was proved by József Kürschák in 1908. This means that the harmonic numbers defined by are never integers. …
Average sum of digits
The smaller the base you write numbers in, the smaller their digits sums will be on average. This need not be true of any given number, only for numbers on average. For example, let n = 2021. In base 10, the sum of the digits is 5, but in base …
A connected topology for the integers
You can define a topology on the positive integers by choosing as an open basis sets the series of the form an + b where a and b are relatively prime positive integers. Solomon Golumb defines this topology in [1] and proves that it is connected. But that paper doesn’t …
Factors of consecutive products
Pick a positive integer k and take the product of k consecutive integers greater than k. Then the result is divisible by a prime number greater than k. This theorem was first proved 128 years ago [1]. For example, suppose we pick k = 5. If we take the product …
Ruling out gaps in the list of Mersenne primes
The largest known primes are Mersenne primes, in part because the Lucas-Lehmer algorithm makes it more efficient to test Mersenne numbers for primality than to test arbitrary numbers. These numbers have the form 2n – 1. The Great Internet Mersenne Prime Search (GIMPS) announced today that they have tested whether …
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 …