multiplicative encoding


The multiplicative encoding of a finite sequencePlanetmathPlanetmath a of positive integers k long is the productPlanetmathPlanetmath of the first k primes with the members of the sequence used as exponents, thus

i=1kpiai,

with pi being the ith prime numberMathworldPlanetmath. For example, the fourth row of Pascal’s triangle is 1, 3, 3, 1. The multiplicative encoding is 21335371=47250.

Encryption is not the purpose of multiplicative encoding, as the original sequence is easily retrieved with trial divisionMathworldPlanetmath. However, there are applications in combinatorics. Neil Sloane, for example, encodes the most famous number triangles as multiplicative encodings of the rows in order. While the resulting sequence for Pascal’s triangle does not consist of squarefreeMathworldPlanetmath numbers (save the first two), it does contain only singly even numbersMathworldPlanetmath.

Another use is in logic, such as Kurt Gödel encoding a logical propositionPlanetmathPlanetmath as a single integer. As an example, Nagel and Newman convert (x)(x=sy) to the integer sequence 8, 4, 13, 9, 8, 13, 5, 7, 17, 9, and by multiplicative encoding to the single integer 172225505803959398742621651659678877886965404082311908389214945877004912002249920215937500000000.

References

  • 1 Ernest Nagel & James Newman, Gödel’s Proof. New York: New York University Press (2001): 75 - 76
  • 2 Neil Sloane, The Encyclopedia of Integer Sequences. New York: Academic Press (1995): M1722
Title multiplicative encoding
Canonical name MultiplicativeEncoding
Date of creation 2013-03-22 17:43:43
Last modified on 2013-03-22 17:43:43
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 5
Author PrimeFan (13766)
Entry type Definition
Classification msc 05C38