Primes and Rough Numbers, Basic ideas

Tips & Tricks
Segui


Primes and Rough Numbers, Basic ideas

John D'Errico il 28 Feb 2025 alle 14:32 (Modificato il 28 Feb 2025 alle 16:26)
Ultime attività Replicato da Alley il 4 Mar 2025 alle 9:06

What is a rough number? What can they be used for? Today I'll take you down a journey into the land of prime numbers (in MATLAB). But remember that a journey is not always about your destination, but about what you learn along the way. And so, while this will be all about primes, and specifically large primes, before we get there we need some background. That will start with rough numbers.
Rough numbers are what I would describe as wannabe primes. Almost primes, and even sometimes prime, but often not prime. They could've been prime, but may not quite make it to the top. (If you are thinking of Marlon Brando here, telling us he "could've been a contender", you are on the right track.)
Mathematically, we could call a number k-rough if it is evenly divisible by no prime smaller than k. (Some authors will use the term k-rough to denote a number where the smallest prime factor is GREATER than k. The difference here is a minor one, and inconsequential for my purposes.) And there are also smooth numbers, numerical antagonists to the rough ones, those numbers with only small prime factors. They are not relevant to the topic today, even though smooth numbers are terribly valuable tools in mathematics. Please forward my apologies to the smooth numbers.
https://en.wikipedia.org/wiki/Rough_number
Have you seen rough numbers in use before? Probably so, at least if you ever learned about the sieve of Eratosthenes for prime numbers, though probably the concept of roughness was never explicitly discussed at the time. The sieve is simple. Suppose you wanted a list of all primes less than 100? (Without using the primes function itself.)
% simple sieve of Eratosthenes
Nmax = 100;
N = true(1,Nmax); % A boolean vector which when done, will indicate primes
N(1) = false; % 1 is not a prime by definition
nextP = find(N,1,'first'); % the first prime is 2
while nextP <= sqrt(Nmax)
% flag multiples of nextP as not prime
N(nextP*nextP:nextP:end) = false;
% find the first element after nextP that remains true
nextP = nextP + find(N(nextP+1:end),1,'first');
end
primeList = find(N)
primeList = 1×25
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
Indeed, that is the set of all 25 primes not exceeding 100. If you think about how the sieve worked, it first found 2 is prime. Then it discarded all integer multiples of 2. The first element after 2 that remains as true is 3. 3 is of course the second prime. At each pass through the loop, the true elements that remain correspond to numbers which are becoming more and more rough. By the time we have eliminated all multiples of 2, 3, 5, and finally 7, everything else that remains below 100 must be prime! The next prime on the list we would find is 11, but we have already removed all multiples of 11 that do not exceed 100, since 11^2=121. For example, 77 is 11*7, but we already removed it, because 77 is a multiple of 7.
Such a simple sieve to find primes is great for small primes. However is not remotely useful in terms of finding primes with many thousands or even millions of decimal digits. And that is where I want to go, eventually. So how might we use roughness in a useful way? You can think of roughness as a way to increase the relative density of primes. That is, all primes are rough numbers. In fact, they are maximally rough. But not all rough numbers are primes. We might think of roughness as a necessary, but not sufficient condition to be prime.
How many primes lie in the interval [1e6,2e6]?
numel(primes(2e6)) - numel(primes(1e6))
ans = 70435
There are 70435 primes greater than 1e6, but less than 2e6. Given there are 1 million natural numbers in that set, roughly 7% of those numbers were prime. Next, how many 100-rough numbers lie in that same interval?
N = (1e6:2e6)';
roughInd = all(mod(N,primes(100)) > 0,2);
sum(roughInd)
ans = 120571
That is, there are 120571 100-rough numbers in that interval, but all those 70435 primes form a subset of the 100-rough numbers. What does this tell us? Of the 1 million numbers in that interval, approximately 12% of them were 100-rough, but 58% of the rough set were prime.
The point being, if we can efficiently identify a number as being rough, then we can substantially increase the chance it is also prime. Roughness in this sense is a prime densifier. (Is that even a word? It is now.) If we can reduce the number of times we need to perform an explicit isprime test, that will gain greatly because a direct test for primality is often quite costly in CPU time, at least on really large numbers.
In my next post, I'll show some ways we can employ rough numbers to look for some large primes.
https://www.mathworks.com/matlabcentral/discussions/tips/879746-primes-and-rough-numbers-used-constructively-to-search-for-large-primes
Image

Primes and rough numbers, used constructively to search for large p...

How can we use roughness in an effective context to identify large primes? I can quickly think of quite a few examples where we might do so. Again, remember I will be looking for primes with not ...

www.mathworks.com

4 Commenti

Accedi per partecipare
Alley
Alley il 4 Mar 2025 alle 9:06
Thanks for sharing the valuable information with us.
John D'Errico
John D'Errico il 28 Feb 2025 alle 16:09
Disclaimer: While I am a mathematician, I am not an expert in number theory, and my last courses on anything close to the ideas in these posts are now nearly 50 years past. However, I want very much to teach the MATLAB community that MATLAB is not just a tool to do linear algebra, simulation, differential equations, etc.
Since students are the future, I hope to teach at least one student that things like number theory are interesting. Honestly, when I was in high school, if I had a tool like MATLAB available to me, I would have seen that as hugely interesting, and fun too. The best way to gain the attention of a student is to show how it can be fun.
Chen Lin
Chen Lin il 28 Feb 2025 alle 21:00
Well said, John. Thanks for sharing your knowledge with the community. Your posts will benefit many community members, especially future students.
goc3
goc3 il 28 Feb 2025 alle 16:05
This is an interesting read.
I see you posted three things today. I would recommend editing this post to add a link to the next one in this series at the end of the post.
John D'Errico

John D'Errico

A retired applied mathematician, consultant, sometime mechanical engineer, numerical analyst, woodworker, bridge player. Please DON'T contact me, as too many students then decide I am their personal consultant if I allow it. I won't do consulting by ...
10
Pubblicas
1094
Replicas
28
Seguaci
Segui
Visualizza il profilo

Post di questo autore

Guarda tutto

Tag

Go to top of page