2012 February 17
Non sequitur

Fun With Math: A Natural Number is a Multiset of Prime Factors

A rule known as the fundamental theorem of arithmetic states, in so many words, that any natural number is uniquely representable as a multiset of prime factors, and vice versa. Having two operands in this form makes some operations easier and other ones more difficult.

This discussion assumes certain definitions of terminology:

  • natural number : A positive integer; an integer 1 or greater.
  • prime number : A natural number with exactly two distinct natural factors, 1 and itself. In particular, 2 satisfies this requirement despite being even, while 1 does not satisfy this requirement because it has only one such factor instead of the required two.
  • multiset : A generalization of a set wherein the multiplicity of each item is significant.

The natural number indicated by a given multiset is the product of 1 and each element of the multiset. For example, 1 is represented by the empty multiset {∅}, 3 by {3}, 5 by {5}, 15 by {3,5}, 25 by {5,5}, and so on.

Multiset operations on the multisets correspond to other operations on the natural numbers they represent:

  • Intersection (i.e. retaining the lesser multiplicity per element) is equivalent to finding the greatest common divisor (gcd):
    • gcd(54, 24)
    • {2, 3, 3, 3} ⋂ {2, 2, 2, 3}
    • {2, 3}
    • 6
  • Union (i.e. retaining the greater multiplicity per element) is equivalent to finding the least common multiple (lcm):
    • lcm(8, 12)
    • {2, 2, 2} ∪ {2, 2, 3}
    • {2, 2, 2, 3}
    • 24
  • Addition of the multiset (i.e. retaining the sum of multiplicities per element) is equivalent to multiplication:
    • 414 * 555
    • {2, 3, 3, 23} + {3, 5, 37}
    • {2, 3, 3, 3, 5, 23, 37}
    • 229770
  • Subtraction of the multiset (i.e. retaining the differences of multiplicities per element between one set and another) is equivalent to division:
    • 88088 / 2002
    • {2, 2, 2, 7, 11, 11, 13} − {2, 7, 11, 13}
    • {2, 2, 11}
    • 44
    • Note that this division is not closed on natural numbers unless the result would also be a natural number (i.e. the left operand must be divisible by the right) because the multiset subtraction itself is not closed on multisets (with nonnegative multiplicities). The multiset notation can still help to reduce the fraction to lowest terms:
      • 2310 / 273
      • {2, 3, 5, 7, 11} − {3, 7, 13}
      • {2, 5, 11} − {13} (since the multiset can’t have negative multiplicities, this is the simplest form)
      • 110 / 13
  • Multiplying all of the multiplicities in the set by n yields the number to the nth power:
    • 1684
    • {2, 2, 2, 3, 7} multiplicities multiplied by 4
    • {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 7, 7, 7, 7}
    • 796594176
  • If all of the multiplicities in the set are themselves divisible by n, dividing them yields the nth root of the number:
    • ∛474552
    • {2, 2, 2, 3, 3, 3, 13, 13, 13} multiplicities divided by 3
    • {2, 3, 13}
    • 78
  • Meanwhile, the natural-to-multiset transform won’t help you at all with addition and subtraction.

Comments are closed.