2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Greg Martin Mar 12 '14 at 6:04
  • $\begingroup$ 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? $\endgroup$ – MathematicalAnomaly Mar 12 '14 at 6:51
  • $\begingroup$ Counterexample to your 90%: $\gcd(3!+1,6!+1)=7$ $\endgroup$ – ccorn Mar 12 '14 at 8:12
  • $\begingroup$ For pairwise coprimeness it is sufficient that the product is squarefree. $\endgroup$ – ccorn Mar 12 '14 at 8:25
  • $\begingroup$ I suppose trivial repetitions of units as in $(1,1,1,\dots)$ shall be excluded $\endgroup$ – ccorn Mar 12 '14 at 8:26
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.