# "Good" subsets of natural numbers

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?

• Actually only one of the problem need to be solved. Suppose you found sequence $a_n$ answering Qn (i). Then the sequence $a_n^2$ provides answer to (ii),because $gcd(x,y)> 1$ iff $gcd(x^2,y^2)>1$ Commented Aug 5, 2016 at 8:08
• Fill in every other term with factorials: $$\square \quad 3! \quad \square \quad 4! \quad \square \quad 5! \quad \square \quad 6! \quad \cdots$$ Fill in the remaining squares with all other integers in incresaing order.
– anon
Commented Aug 5, 2016 at 8:22
• @arctictern So you mean first set is "Good"? Please explain more Commented Aug 5, 2016 at 8:24
• @arctictern: You should post that as an answer, nice. Commented Aug 5, 2016 at 8:24
• @arctictern That would produce $$2,3!,3,4!,4,5!,5,\color{red}{6!,7},7!$$Beginning with $4!$ should heal this Commented Aug 5, 2016 at 8:26

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

• But... trees... :( Commented Aug 5, 2016 at 8:34
• @Stefan I don't see what you mean? Commented Aug 5, 2016 at 8:42
• Would the sequence be something like $2, 6, 3, 12, 4, 20, 5, 35, \ldots$? Commented Aug 5, 2016 at 8:46
• Well, your solution is obviously more elegant than mine. My mind seemingly refused to work with intergers and instead enumerated Cantor's tree in a way that codes the desired result. So... while my solution may seem unnecessarily complicated, it does have trees! Commented Aug 5, 2016 at 8:46
• @HagenvonEitzen I don't understand your solution at all!! Commented Aug 5, 2016 at 9:26

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.

• On my way home I noticed that this is only 'morally correct' as I don't list any numbers that contain a given prime factor multiple times. However, this can easily be fixed by encoding the multiplicities into the second half of the given string $s$. Commented Aug 5, 2016 at 14:38