# How can one efficiently generate n small relatively prime integers?

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?

-
What do you mean by relatively prime? If you mean gcd of all to be 1, pick n-1 odd numbers and then add 2 to the set. Did you mean pairwise relatively prime? In which case you seem to be leaving very little space. –  Aryabhata Nov 11 '10 at 0:35
Have you tried running an efficient implementation of the sieve of Eratosthenes until some cutoff, then using an efficient probabilistic primality test after that? –  Qiaochu Yuan Nov 11 '10 at 0:50
@Moron, yes, pairwise relatively prime. I'm not sure whether the relaxation from "prime" to "pairwise relatively prime" is helpful. –  jonderry Nov 11 '10 at 0:52
@Qiaochu Yuan, that's essentially my idea for a basic algorithm. The trouble is that primes are spaced roughly Omega(lg n) apart when you reach candidates of size n^Omega(1). Additionally, as a test, Miller-Rabin adds another polylog factor. I was wondering whether something better exists, since we are generating all the primes/relative-primes all at once. –  jonderry Nov 11 '10 at 0:59
If you don't insist on relatively small, you can use (9^2^n+1)/2 as shown in math.stackexchange.com/questions/3243/… –  Ross Millikan Nov 11 '10 at 1:06

## 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.

-
It'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. –  Charles Apr 25 '11 at 17:58

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.

1. (Euclid): M + 1
2. (Stieltjes): Factor M as A.B in some way, and take A + B
3. (Euler) Totient(M)
4. (Braun and Metrod): N = M/p1 + ... + M/p_k
5. (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 ! *

-
-1: Incorrect: Euclid P+1: Is not necessarily a new prime. Probably the case with others. Besides, how do all these methods ensure that all numbers are O(logn) bits? (or give an O(n) time algorithm?) –  Aryabhata Nov 11 '10 at 3:26
@Moron, I was in a hurry when I typed it last night and messed it up. Read it now. About O(log n) bits, yes, some of these may not provide that. –  SandeepJ Nov 11 '10 at 13:42
These methods all quickly give numbers that are way too large. This is not an easy problem; the requirement that the numbers are small means that you have no room to make these easy big constructions. –  Qiaochu Yuan Nov 11 '10 at 13:46
@Qiaochu, OK but how does Latex work here? Any links? –  SandeepJ Nov 11 '10 at 13:55
@SandeepJ: it works the same as on MO, except that escaping underscores works differently here, which is probably the problem you were having (either that or you needed to refresh; sometimes it just doesn't load). Instead of using  I think backslashes work. –  Qiaochu Yuan Nov 11 '10 at 15:33

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.

-
This generates 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 method 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. –  Charles Mar 16 '12 at 13:03

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)

-