Square-free Integer - Encoding As Binary Numbers

Encoding As Binary Numbers

If we represent a square-free number as the infinite product:

then we may take those and use them as bits in a binary number, i.e. with the encoding:

e.g. The square-free number 42 has factorisation 2 × 3 × 7, or as an infinite product: 21 · 31 · 50 · 71 · 110 · 130 · ...; Thus the number 42 may be encoded as the binary sequence ...001011 or 11 decimal. (Note that the binary digits are reversed from the ordering in the infinite product.)

Since the prime factorisation of every number is unique, so then is every binary encoding of the square-free integers.

The converse is also true. Since every positive integer has a unique binary representation it is possible to reverse this encoding so that they may be 'decoded' into a unique square-free integer.

Again, for example if we begin with the number 42, this time as simply a positive integer, we have its binary representation 101010. This 'decodes' to become 20 · 31 · 50 · 71 · 110 · 131 = 3 × 7 × 13 = 273.

Among other things, this implies that the set of all square-free integers has the same cardinality as the set of all integers. In turn that leads to the fact that the in-order encodings of the square-free integers are a permutation of the set of all integers.

See sequences A048672 and A064273 in the OEIS