Proof for bijection of a function between positive integers and nonprime positive integers.

Very interesting question!

Let us first prove that S(m) can not be prime. This follows from the fact that such a sequence can not end in a prime, as the product would only be divisible once by this prime.

To prove it is a bijection from all integers greater than $1$ to all composite numbers, we give the inverse. The inverse $S^{-1}(n)$ is the greatest possible $m$ such that such a sequence exists. Note that this is well-defined for composite numbers as you can take the sequence to be all primes dividing into $n$ an odd number of times.

To prove this gives an inverse, we need to show $S^{-1}(S(m))=m$ holds for all $m$. This is because, if a sequence ending with $S(m)$ exists with a higher starting number than $m$, then taking the symmetric difference with the sequence starting with $m$ and ending with $S(m)$ gives a sequence starting with $m$ and with lower ending number than $S(m)$.

Let $n$ be a composite number. Then there are sequences $a_1<a_2<\cdots <a_r = n$ such that $a_1a_2\cdots a_s$ is a square. For instance, if $n = ab$ with $a<b<n$ (which is possible since $n$ is composite), we have $a\cdot b \cdot n = n^2$.

Since there are sequences, and they all have starting points less than or equal to $n$, there is a highest starting point, say $m$. Let $m = b_1<b_2<\cdots b_s = n$ be one such sequence.

Clearly $S(m)\leq n$, as the sequence $b_i$ shows. I claim we have equality. Assume for contradiction that $S(m) < n$. Let $m = c_1\cdot c_2\cdots c_s = S(m)$ be a sequence such that $c_1c_2\cdots c_s$ is a square. Then $$ b_1b_2\cdots b_s\cdot c_1c_2\cdots c_t $$ is a square. It remains a square if we take away all the terms that appear twice. $m = b_1 = c_1$ appears twice, so the smallest factor in the stripped-down product is larger than $m$. And the largest factor is still $n$, since $b_s = n$ but $c_t<n$.

What we end up with is a sequence of distinct integers which if we multiply them together we get a square, the largest of them is $n$ and the smallest is larger than $m$, contradicting the definition of $m$.

This shows that $S(m) = n$.