Find an infinite set of positive integers such that the sum of any two distinct elements has an even number of distinct prime factors

Solution 1:

For what it's worth, such a sequence constructed by a greedy algorithm begins:

2, 4, 8, 10, 16, 18, 36, 199, 208, 1131, 1347, 3984, 5751, 7310, 27315, 129313, 134101, 169400, 589570

That is, we start with $A_1 = 2$, and then each $A_n$ is the smallest number greater than $A_{n-1}$ with $A_i + A_n$ having an even number of distinct prime factors for each $n \le 1$. (So, for example, $A_3 = 8$ because $5+4, 6+2, 7+2$ each have an odd number of distinct prime factors, but $8+2$ and $8+4$ both have even numbers.)

Another such sequence, starting with 1, begins

1, 5, 9, 13, 35, 39, 286, 290, 381, 385, 866, 4376

and one starting with 3 begins

3, 7, 11, 15, 33, 41, 47, 65, 101, 203, 4102, 6392, 8507, 18608.

From these it seems that these sequences grow roughly exponentially; that is, $A_n \approx k^n$ for some constant $k$. This makes sense. Since approximately half of all integers have an even number of distinct prime factors, once you have $n$ numbers in such a sequence it should take about $2^n$ tries to find the next one.

Of course this isn't a proof, but it's at least an argument why such sequences should exist. And judging from the irregularity of the greedily constructed sequences, a greedy method probably isn't the best way to go here even if you want to explicitly construct the sequence.

Solution 2:

Start with $\{5n+1\}$ and construct an infinite complete graph, colouring the edge between $x$ and $y$ with the parity of the number of distinct prime factors of $x+y$.

By the infinite Ramsey theorem, there is an infinite clique of one colour.

If that corresponds to the number of distinct prime factors being even, we are done. Otherwise consider each number multiplied by $5$. Since the sum of any (original) two is not divisible by $5$, after multiplying by $5$, we have that the number of distinct prime factors for each sum must be even.

In fact, I am guessing there are an infinite number of such sets, such that any two such sets have finite intersection.