The definition of small is that they have O(lg n) bits. One way is just to test the integers 2,3,... for primality and keep the first n primes, but this takes at least O(n log n) time (times the cost of primality testing) using a naive algorithm. Is it possible to do it in linear time?
How can one efficiently generate n small relatively prime integers?
-
0If they're very small can't you just use a sieve? – 2010-11-11
4 Answers
You can find the first n primes in time $n\log n/\log\log n$ with the Atkin-Bernstein sieve. This is better than your naive $n\log^5n$ or so algorithm (or drop the exponent by 1 using pretesting with M-R), but still superlinear.
-
0It's worth noting that at least half of your numbers need to be at least prime(n/2), and so the space you need to output the numbers in binary is $\Omega(n\log n)$. So getting the answer in linear time -- or indeed in o(n log n) time -- requires accepting results in a more compact format. – 2011-04-25
Check out Chapter 1 of Paul Pollack's book "Not Always Buried Deep". He lists several elementary proofs for the infinitude of primes, some of which can be adapted to form simple iterative algorithms.
(Sorry, I can't get Latex to work here. Isn't it like MathOverflow? Anyway..)
Let S = {p1...pk} be the set of previously generated coprime integers.
And take M = product of integers in S
Now do any of the following to get new integer coprime to the set S.
- (Euclid): M + 1
- (Stieltjes): Factor M as A.B in some way, and take A + B
- (Euler) Totient(M)
- (Braun and Metrod): N = M/p1 + ... + M/p_k
- (Goldbach): N = 2 + M
There is also Saidak's proof from the same book:
- Take N1=n; N2 = N1(N1+1); N3 = N2(N2+1)... Nk=Nk(Nk+1) and so on. This a relative prime sequence.
I am probably missing a couple of other proofs. Anyway, check the book!
EDIT1 : **I am going to retain the answer despite the negative votes, in the hope that it might spur someone else to invent a better algorithm ! *
-
0The proof attributed to Saidak is much older and is expressed more much more concisely in the form $\rm\: n^2\!+n\:$ has a larger set of prime factors than $\rm\:n,\:$ see my [answer here.](http://math.stackexchange.com/a/30133/242) – 2012-11-06
See this "Generating All Co-Prime Pairs".
Method claims to be complete and yield no repeats. Each result generates THREE new children; just stop the generation if either member of the (m, n) pair exceed your definition of "small".
Since this is a declarative generation, that meets your criterion for "linear time", right?
To my (non-mathematician) eyes, this relationship looks a lot like generating Pythagorean-triples.
-
2This g$e$nerates pairs of relatively prime integers, but you can't combine the pairs to make n pairwise relatively prime integers. For example, starting from (3, 1) the metho$d$ makes (5, 3), (7, 3), and (5, 1) in the first step, but these eight numbers are not distinct. Worse, the next step includes (9, 5); while 9 is relatively prime to 5 it is not relatively prime to 3 which appeared earlier. So that method doesn't work here. – 2012-03-16
I assume S need not be prime (just relatively prime)
For S= {2, 15}
Goldbach method : N = 2 + M
= 2 + 30 = 32 (not relatively prime with 2)