Editing Square-free integer (section)

==Encoding as binary numbers==
If we represent a square-free number as the infinite product

:<math>\prod_{n=0}^\infty (p_{n+1})^{a_n}, a_n \in \lbrace 0, 1 \rbrace,\text{ and }p_n\text{ is the }n\text{th prime}, </math>

then we may take those <math>a_n</math> and use them as bits in a binary number with the encoding

:<math>\sum_{n=0}^\infty {a_n}\cdot 2^n .</math>

The square-free number 42 has factorization {{nowrap|2 × 3 × 7}}, or as an infinite product {{nowrap|2<sup>1</sup> · 3<sup>1</sup>  · 5<sup>0</sup> · 7<sup>1</sup> · 11<sup>0</sup> · 13<sup>0</sup> ···}}  Thus the number 42 may be encoded as the binary sequence <code>...001011</code> or 11 decimal. (The binary digits are reversed from the ordering in the infinite product.)

Since the prime factorization of every number is unique, so also 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 <code>101010</code>. This decodes to {{nowrap|2<sup>0</sup> · 3<sup>1</sup> · 5<sup>0</sup> · 7<sup>1</sup> · 11<sup>0</sup> · 13<sup>1</sup> {{=}} 3 × 7 × 13 {{=}} 273.}}

Thus binary encoding of squarefree numbers describes a [[bijection]] between the nonnegative integers and the set of positive squarefree integers.

(See sequences [[OEIS:A019565|A019565]], [[OEIS:A048672|A048672]] and [[OEIS:A064273|A064273]] in the [[On-Line Encyclopedia of Integer Sequences|OEIS]].)