I have attempting to solve this using the infinite ramsey theorem, with colouring based on whether the sum of two vertices has an even or odd number of distinct prime factors. This is leading to an infinite recursion. Is this ok? At the end of all time I will be done.

  • $\begingroup$ I don't think the Ramsey theorem will give you what you want. It promises a homogeneous set, but that could be a set that has all sums with an odd number of prime factors. It doesn't promise sets homogeneous for both colors. It is also nonconstructive and it sounds like you want an explicit example. Not that I have any better idea. $\endgroup$ – Ross Millikan Oct 22 '10 at 18:19
  • 1
    $\begingroup$ The Ramsey theorem works; you just need to be slightly trickier about your choice of graph. $\endgroup$ – Qiaochu Yuan Oct 22 '10 at 18:46

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.

  • $\begingroup$ This was my solution with 5 replaced by 3. But I still don't think I want it to be publicly available. Can you please delete this and then, if you like, un-delete it after Wednesday afternoon? $\endgroup$ – Qiaochu Yuan Nov 1 '10 at 17:30

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.


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.