We say that a positive integer is good if it has an even number of prime factors. Does there exist an arbitrarily large sequence of consecutive good numbers?

In fact, this problem came from another one: Show that there exists an infinite set $S$ of positive integers such that the sum of any two distinct elements of S has an even number of distinct prime factors.

If the first statement about long sequences of good numbers is true, then I can finish the second problem as follows: Choose $s_{1}\in \mathbb{N}$ randomly. Then, we will define the increasing sequence $s_{n}$ inductively. Take a sequence of $s_{n-1}+1$ consecutive good numbers. If $a$ is the smallest one in this sequence, take $s_{n}=a$. Then set $S=\{s_{n}\}^{\infty}_{n=1}$.

  • 1
    $\begingroup$ Is 12 good? (That is, are you taking into account multiplicity of prime factors?) $\endgroup$ – Michael Lugo Jan 15 at 18:10
  • 1
    $\begingroup$ Heuristically, which numbers are "good" is essentially coin-flipping, and we should expect arbitrarily long runs of heads in a sequence of coin flips. But these sort of things are notoriously hard to prove. $\endgroup$ – Michael Lugo Jan 15 at 18:19
  • 1
    $\begingroup$ Peter's tests are roughly in line with my coin-flipping heuristic (that is, that we should have a run of length $n$ by around $2^n$). $\endgroup$ – Michael Lugo Jan 15 at 18:47
  • 1
    $\begingroup$ I just want to solve the original problem. If this strstegy is hard to proof, I will find another one. $\endgroup$ – alexp9 Jan 15 at 18:48
  • 1
    $\begingroup$ The original question has a nice non-constructive proof using Ramsey's theorem, see math.stackexchange.com/questions/7527/… $\endgroup$ – Dap Jan 18 at 11:29

Your Answer

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

Browse other questions tagged or ask your own question.