# Finding infinite sequences with pairwise relatively prime outputs.

I am looking for a formula which for every element in $\mathbb{Z}$ as an input, gives pairwise relatively prime outputs. That is for example thanks to Greg Martin's suggestion the positive outputs of $2^{2^{n}}+1$ seem to all be pairwise relatively prime. I understand that the infinite set of primes is a solution however there is no known formula for primes. I have also tried the product ($\prod_{i=1}^ni)+1$ Which I am 90% sure is correct. In the best of scenarios I can find a working solution of the form $y=f(x)$ and maybe a proof solidifying my guess. So far I have been unsuccessful but would like to hear your suggestions or answers. Thank you.

• To clarify, you are asking for an infinite sequence of positive integers, given by some sufficiently nice formula, such that no two numbers in the sequence have a common factor? And what is $A_i$ in your proposed formula? ... Have you considered the Fermat numbers $2^{2^n}+1$, which are indeed pairwise relatively prime? – Greg Martin Mar 12 '14 at 6:04
• Yes that's right and also possibly an infinite sequence including the negative integers. I think it would make more sense if $A_i$ was just $i$. I'll correct it. I'm surprised I didn't consider Fermat's numbers. Is there a way to prove that all the numbers are pairwise relatively prime? – MathematicalAnomaly Mar 12 '14 at 6:51
• Counterexample to your 90%: $\gcd(3!+1,6!+1)=7$ – ccorn Mar 12 '14 at 8:12
• For pairwise coprimeness it is sufficient that the product is squarefree. – ccorn Mar 12 '14 at 8:25
• I suppose trivial repetitions of units as in $(1,1,1,\dots)$ shall be excluded – ccorn Mar 12 '14 at 8:26

## 2 Answers

The Fermat numbers $2^{2^n}+1$ are pairwise relatively prime - this is not just an observation but is in fact provable.

It's easy to turn this into a function $f\colon \Bbb Z\to\Bbb N$ where the outputs are pairwise relatively prime: $$f(n) = \begin{cases} 2^{2^{2n}}+1, &\text{if }n\ge0; \\ 2^{2^{2|n|-1}}+1, &\text{if }n\le-1. \end{cases}$$ Or, if you prefer something defined without cases, just let $f(n) = 2^{2^{|3n-1|}}+1$. Or if you even want an analytic function: $f(n) = 2^{2^{(3n-1)^2}}+1$.

I was just working on something similar myself which might help; this isn't a single formula so much as a description of a set of sequences with that property, and although there are much smaller-valued solution sets, an easy one to describe is $$\Phi_{p_k}(x)$$ for $$k\in\mathbb{N}$$, where $$p_k$$ is the $$k$$th prime, and $$\Phi_i$$ represents the $$i$$th cyclotomic polynomial.

E.g., a set like $$\begin{array} \\ x+1,\\ x^2+x+1,\\ x^4+x^3+x^2+x+1,\\x^6+x^5+x^4+x^3+x^2+x+1,\\\ldots \end{array}$$ will be pairwise prime for any $$x$$.

I also suspect you can do it with an infinite number of quadratics, but they're not as easily generated. Linear recurrences would also be a good place to try.

Oh right, and if nobody's mentioned it, Sylvester's sequence and its variants has this exact property.