Prime signatures

Prime signatures are a way of describing the prime factorization of a number. The prime signature lists the exponents of the prime factors, typically sorted from smallest exponent to greatest (or vice versa).

For example, the number 28’s prime factorization is 2² × 7, which can be abstracted to p²q (where p and q are distinct primes) or p₁²p₂ (where p₁ and p₂ are distinct primes.)

The prime signature of 28 is therefore {1,2}.

All prime numbers have a prime signature of {1}, squares of primes have prime signatures of {2}, a number composed of two primes has a prime signature of {1,1}, etc.

Below is a table of the first 12 positive integers and their prime signatures:

	Prime factorization		Prime signature
1	1	p0	{}
2	2	p1	{1}
3	3	p1	{1}
4	22	p2	{2}
5	5	p1	{1}
6	2 × 3	p1q1	{1,1}
7	7	p1	{1}
8	23	p3	{3}
9	32	p2	{2}
10	2 × 5	p1q1	{1,1}
11	11	p1	{1}
12	22 × 3	p2q1	{1,2}

As you can see, the elements of the prime signature map directly to the exponents of the prime factorization. (p and q are shown here as p¹ and q¹ to better illustrate this connection.)

Zero does not have a prime signature, since it does not have a unique prime factorization, but all positive integers have a prime signature. As seen above, the first few prime signatures are {}, {1}, {2}, {1,1}, {3} and {1,2}. You can see a list of the first 400 prime signatures here.

The prime signature of 1

Since p⁰ is 1 regardless of which prime p is, 1 is the only number with an empty prime signature, shown as {}. Equivalently, the prime signature of 1 could be shown as {0}, to illustrate the connection to the exponent of p⁰.

However, any number of zero-powered primes multiplied together also produce 1, so we could just as easily assign 1 a prime signature of {0,0} (for p⁰q⁰) or {0,0,0} (for p⁰q⁰r⁰.) Therefore we omit the zeroes, since they do not add any information.

(Alternatively, some sources show the prime signature of 1 as {1}, causing it to “share” the prime signature of 2, 3, 5 and the rest of the primes. However, most prime signature sequences show 1 and 2 as having different prime signatures, even if the (empty) prime signature for 1 is not shown explicitly.)

While the empty prime signature, {}, applies only to 1, every other prime signature has infinitely many numbers associated with it. For example, {1} is the prime signature of each and every prime number, and there are infinitely many primes.

Do negative numbers have prime signatures?
What about fractions, like 1/2?

The standard definition of prime signatures applies only to positive integers, so neither negative numbers nor non-integers have a prime signature, according to the standard definition.

However, it is possible to extend the concept of prime signatures to encompass other types of numbers. For example, the reciprocal of a prime number (e.g. 1/2, 1/3, 1/5) could be given a prime signature of {-1}, since the reciprocal of a prime can be expressed as p^-1.

Similarly, a fraction such as 3/4 could be given a prime signature of {-2,1}, since 3/4 is equivalent to 3¹ × 2^-2, or p^-2q.

Branching

Each prime signature branches into two or more different prime signatures through the inclusion of an additional factor. {1} for example will branch into either {2} or {1,1}, depending on what factor is added (i.e. the existing factor or a new factor.) The number of branches that can be taken depends on the number and arrangement of the factors.

As another example, {1,2,3,4} can branch five different ways. Raising one of the existing four unique factors to a higher power will produce one of these four new prime signatures, depending on which factor is raised: {2,2,3,4}, {1,3,3,4}, {1,2,4,4} or {1,2,3,5}. Including a new, fifth unique factor will produce a prime signature of {1,2,3,4,5}.

The image below illustrates this by showing the possible paths a prime signature can take. Each distinct prime is represented by a letter: p, q, r, etc.

The black line in the image shows a path taken that increases the p factor by one power. For example, the box labeled p² branches to the box labeled p³ via the black line, indicating the power of p has been increased by one.

Similarly, the red line indicates q’s power has been increased, the green line indicates r’s power has been increased, the purple line indicates s’s power has been increased, and the blue line indicates t’s power has been increased.

The numbers along the left side correspond to the lowest integer with the prime factorization shown in the box to the right. For example, 256 is shown next to p⁸ because 256 is the smallest integer that is a prime to the power of 8.

Note that only certain branching lines are shown; p⁹ (at the bottom) shows a red branch below it, indicating a q factor can be added, but no green line is shown, because there cannot be an r without a q.

Prime signature links

On this site you can find a list of the first 400 prime signatures, and a large table showing the first 4 (or more) integers for each of the first 160 prime signatures.

Also on this site: integer sequences built using prime signatures as the basis: binary-encoded prime signatures and iterative mapping of prime signatures.

Wikipedia has a prime signature page as well.