Smooth numbers
Take 5 minutes to learn about smooth numbers (with optional code!)
What is the purpose of this post and why should you read it?
The purpose of this post is to introduce you to the concept of “smooth numbers.” They are part of number theory and are just interesting to learn about.
As usual, I’ll also provide a Python code notebook file that you can use to explore smooth numbers.
Why should you read this post?
I think smooth numbers are just interesting to ponder and to visualize, and I hope you agree.
I have a few bits of humor scattered around.
The time you spend reading this post is definitely better than doom-scrolling reddit but probably worse than going for a run in a beautiful park with a dog.
What’s a “smooth number”?
Maybe you think it’s this:
Or maybe you think a “smooth number” is One Cool Operator:
For any kids reading this: Smoking is NOT COOL. Don’t do it. 6 was afraid of 7 because 7 died of smoking-related cancer and increased 8’s risk of cancer by proximity.
Anyway, both of those guesses are wrong.
The serious answer
A B-smooth number is a positive integer whose largest prime factor is ≤B (remember that a prime number is an integer divisible without remainders by no other integers except itself and 1, e.g., 1, 2, 3, 5, 7, 13, …). The B is for bound.
To find the smoothness of a number, start by prime-factoring it. For example, the number 30 can be prime-decomposed like this:
Then we look at the largest prime factor, which is 5. Thus, the number 30 is 5-smooth.
But wait a minute: 5 is also less than 7 (another prime number), and the definition of smoothness is that the largest prime factor is ≤B. If we set B=5, then 5≤5, but if we set B=7, then 5≤7.
So in fact, the number 30 is 5-smooth and 7-smooth. And it’s 11-smooth and 13-smooth, etc. Thus, a number can be multiple B-smooth. It’s a big number tent. But 30 is not 3-smooth, so I guess the tent isn’t that big.
On this website, you can see lists of various B-smooth numbers (they use the letter p instead of B).
Who cares about smooth numbers?
With regards to smooth numbers, all humans can be grouped into four categories:
Don’t know about or care about smooth numbers. Probably the majority of humans, tbh.
Find smooth numbers momentarily interesting. This is you if you take 5 minutes to read this post, admire the bizarre beauty of math and numbers, and then go back to your normal (unsmooth) life.
Find smooth numbers theoretically fascinating. People who study pure math and number theory learn about and investigate smooth numbers because they have interesting properties, are related to prime number theory, and so on. It’s OK to think that math is cool (don’t believe me — ask the One Cool Operator).
Use smooth numbers in computational math like cryptography. Smooth numbers actually have quite a few applications, including in estimating the computational complexity of certain math problems, implementing numerical methods, and in cryptography algorithms including RSA (e.g., ensuring that security codes are sufficiently difficult to factor and therefore difficult to hack).
Finding B-smooth numbers in Python
The rest of this post is about finding those really cool numbers, and visualizing them. They have some interesting characteristics.
You can simply read the rest of this post without using the Python code. That’s fine and I hope you enjoy it!
If you want the code to produce the figures below, then you can get it here on my GitHub.
Part 1: Find the largest prime factors
To get the largest prime factor of a number, do a prime factorization and then simply find the largest of those factors.
The easiest way to prime-factorize a number in Python is using the SymPy library.
In code it looks like this:
The procedure is quite simple: Loop over integers, use SymPy’s function primefactors() to get all prime factors, and then store the largest of those factors. The function returns an empty list for integers 0 and 1, which causes np.max() to crash. That’s why I start the for-loop at 2.
The figure below shows the largest prime factor for the integers 2 through 10,000.
It looks very cool, like a laser-light show or a 1990’s video game. Basically, that plot shows that the larger the number, the larger its largest prime factor can be.
Out of curiosity, I also plotted the cosine of the max prime factors by their square root:
I don’t think there’s any deep, hidden meaning in this plot. It just looks neat.
Part 2: Find the B-smooth numbers
Once you know the maximum prime factor, finding B-smooth numbers is easy: Just find all the numbers that have a max prime factor less than B.
Those are all the 5-smooth numbers up to 10,000. We can check that against the following website:
Part 3: More fun (the magic of 19)
The plot below shows the frequencies of maximum prime factors. It shows the number of integers up to 10k that have the x-axis value as the max prime factor.
Apparently, lots of integers have 19 as their maximum prime factorization
I asked ChatGPT if that was meaningful, and I got a completely vacuous answer that said absolutely nothing in many words:
OK that’s it for now. I hope you enjoyed this little journey into number theory! Don’t forget that the code file that creates this post is freely available for you to play around with.