"Good" subsets of natural numbers

Question

We define a subset A of positive integers as "Good" if it's possible to write it's members as $a_1$, $a_2$, $a_3$, $\cdots$ so that GCD of any two consecutive numbers $a_i$ and $a_{i+1}$ is greater than $1$. Verify and prove "Goodness" of the following two sets:

1. Set of positive integers greater than $1$
2. Set of squares greater than $1$

How to solve this problem?

Answer 1

For question 1, we define $a_1,a_2,\ldots$ recursively. Assume we have already defined $a_k$ for $1\le k<n$.

• If $n$ is odd, let $a_n$ be the smallest number not yet used.
• If $n$ is even, let $a_n$ be the smallest not yet used proper multiple of $a_{n-1}$ and $m$, where $m$ is the smallest number not yet used. (Incidentally, it will happen that $a_{n+1}=m$)

This will guarantee that $a_{2n}$ is divisible by both $a_{2n-1}$ and $a_{2n+1}$.

Answer 2

To ease my notation, I will use the convention that $n = \{ 0, 1, \ldots, n -1 \}$ for all $n \in \mathbb N$. (This is standard in set theory, but less common in other branches.)

Let me first address the set of natural numbers $>1$: This set is indeed good. Let $\{ p_{n} \mid n \in \mathbb N \}$ be an enumeration of all prime numbers and let $S$ be the set of all finite sequences $s \colon n \to \{0,1\}$ such that $s(n-1) = 1$. Fix an enumeration $S = \{ s_n \mid n \in \mathbb N \}$ such that for all $n \in \mathbb N$ there is some $i \in \mathbb N$ such that $s_n(i) = 1 = s_{n+1}(i)$. Such an enumeration exists and can be obtained as follows: $$ 1, 11, 10, 111, 100, 101, 110, 1111, 1000, 1001, \ldots $$ Note that this is just counting in binary with a slight twist: Whenever we have to introduce a new digit, we first assign a $1$ to all these digits, hence obtaining $2^{n}-1$ for some $n \in \mathbb N$, and then continue to list the numbers below $2^{n}-1$ in ascending order that haven't been listed yet.

Now let $c_n = \prod_{i=0}^{\operatorname{dom}s_n -1 } p_i^{s_n(i)}$. It's easy to check that $\{c_n \mid n \in \mathbb N \}$ witnesses the goodness of $\mathbb N^{+} \setminus \{1\}$. (Clearly $\{c_n \mid n \in \mathbb N\}$ enumerates $\mathbb N^{+} \setminus \{1\}$ and $(c_n, c_{n+1}) > 1$ follows from the choice of our enumeration $\{s_n \mid n \in \mathbb N \}$.)

As P Vanchinathan pointed out in his comment, this immediately implies that $\{ n^2 \mid n \in \mathbb N^+ \setminus \{1\} \}$ is good as well.