0

What I'm interested to find out about is if I can get a formula to find the sequence of coprimes for a primorial.

ie for primorial 30 the coprimes: 1,7,11,13,17,19,23,29

EulerPhi(30) is the count of coprimes but I'd like to get the formula to find the actual coprimes. Any idea?

I want to find the coprimes of very large primorials.

poker3
  • 91
  • If they're very large primorials then there are a very large number of coprimes. Can you be very specific about what you mean by "efficiently"? – Erick Wong Aug 26 '16 at 16:51
  • like a general formula, so you can only give the index and it gives you the coprimes... or maybe some sort of – poker3 Aug 26 '16 at 18:19
  • There isn't going to be a (concise) analytic formula, but you probably want to look into something like wheel sieves (or if you haven't yet considered a basic Eratosthenes sieve, you definitely should!). Unfortunately the wikipedia article on wheel factorization is very lightweight, and I haven't found a good online reference. – Erick Wong Aug 26 '16 at 18:37
  • By "concise" I mean that there is probably an inclusion-exclusion formula that has $2^k$ terms where $k$ is the number of the primes that go into the primorial. This is certainly smaller than the primorial itself, but it's still very large. – Erick Wong Aug 26 '16 at 18:39

0 Answers0