Prime signatures

This article needs more work.

Please help by expanding it!

A positive integer with prime factorization

$p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}$

is said to have a prime signature (an [unordered] prime signature) of 

{α1, α2, …, αk }

where 

{…}

is a multiset (or bag). For example, the prime signature of 

1

is the empty multiset 

{ }

, primes have a prime signature 

{1}

, and prime powers 

p k

have prime signature 

{k}

.

Goldston, Graham, Pintz, & Yıldırım call these exponent patterns, and King refers to them as prime bags (PBs).

The prime signature ([unordered] prime signature) of 

n

should not be confused with the ordered prime signature of 

n

: for example 

12 = 2 2  ×  3

and 

18 = 2  ×  3 2

both have prime signature 

{2, 1}

while 

12

has ordered prime signature 

(2, 1)

and 

18

has ordered prime signature 

(1, 2)

, where 

(…)

is a tuple.

Prime signature as partition of Omega(n)

Numbers and their prime signatures
n	Factorization	Prime signature
1		{ }
2	$2$	{1}
3	$3$	{1}
4	$2^{2}$	{2}
5	$5$	{1}
6	$2\cdot 3$	{1,1}
7	$7$	{1}
8	$2^{3}$	{3}
9	$3^{2}$	{2}
10	$2\cdot 5$	{1,1}
11	$11$	{1}
12	$2^{2}\cdot 3$	{2,1}
13	$13$	{1}
14	$2\cdot 7$	{1,1}
15	$3\cdot 5$	{1,1}
16	$2^{4}$	{4}
17	$17$	{1}
18	$2\cdot 3^{2}$	{2,1}
19	$19$	{1}
20	$2^{2}\cdot 5$	{2,1}
21	$3\cdot 7$	{1,1}
22	$2\cdot 11$	{1,1}
23	$23$	{1}
24	$2^{3}\cdot 3$	{3,1}
25	$5^{2}$	{2}
26	$2\cdot 13$	{1,1}
27	$3^{3}$	{3}
28	$2^{2}\cdot 7$	{2,1}
29	$29$	{1}
30	$2\cdot 3\cdot 5$	{1,1,1}

The prime signature of 

n

is a partition of 

Ω (n)

$\Omega (n)=\sum _{i=1}^{\omega (n)}\alpha _{i},$

where 

Ω (n)

is the number of prime factors (with repetition) of 

n

.

Number of divisors and prime signature

Since the number of divisors depends only on the exponents in the prime factorization of a number, all numbers of a given prime signature have the same number of divisors.

Prime signatures and their numbers

See Orderings of prime signatures.

Special numbers and their prime signatures

See also Sequences determined by prime signature

A number with prime signature

$S=\{\alpha _{1},\alpha _{2},...,\alpha _{\omega (n)-1},\alpha _{\omega (n)}\}$

is

• A unit if 

  S = { }

  ;
• A prime if 

  S = {1}

  ;
• A prime power if 

  S = {k}, k   ≥   2

  ;
• A square if 

  gcd (S)

  is even;
• A k-th power if 

  gcd (S)

  is a multiple of 

  k, k   ≥   2

  ;
• A square of a squarefree number if 

  min (S) = max (S) = 2

  ;
• A 

  k

  -th power of a squarefree number if 

  min (S) = max (S) = k, k   ≥   2

  ;
• A squarefree number if 

  max (S) = 1

  ;
• A squareful number (2-powerful number) if 

  max (S)   ≥   2

  ;
• A squarefull number (2-powerfull number) if 

  min (S)   ≥   2

  ;
• A cubeful number (3-powerful number) if 

  max (S)   ≥   3

  ;
• A cubefull number (3-powerfull number) if 

  min (S)   ≥   3

  ;
• A biquadrateful number (4-powerful number) if 

  max (S)   ≥   4

  ;
• A biquadratefull number (4-powerfull number) if 

  min (S)   ≥   4

  ;
• A k-powerful number if 

  max (S)   ≥   k, k   ≥   2

  ;
• A k-powerfull number if 

  min (S)   ≥   k, k   ≥   2

  ;
• A k-almost prime if$\textstyle {\sum _{\alpha _{i}\in S}}$ 

  αi = k

  ;
• A squarefree k-almost prime if$\textstyle {\sum _{\alpha _{i}\in S}}$ 

  αi = k

  and 

  max (S) = 1

  ;
• An Achilles number if 

  min (S)   ≥   2

  and 

  gcd (S) = 1

  .

Sequences

A118914 Concatenation of the prime signatures (in increasing order of exponents of prime power components) of the positive integers.

 

{1, 1, 2, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 4, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 4, 2, 1, 2, 1, ...}

A025487 Least integer of each prime signature; also products of primorial numbers A002110.

 

{1, 2, 4, 6, 8, 12, 16, 24, 30, 32, 36, 48, 60, 64, 72, 96, 120, 128, 144, 180, 192, 210, 216, 240, 256, 288, 360, 384, 420, 432, 480, 512, 576, 720, 768, 840, 864, 900, 960, 1024, 1080, 1152, 1260, 1296, ...}

A036035 Least integer of each prime signature, in graded (colexicographic order or reflected colexicographic order) of exponents.

 

{1, 2, 4, 6, 8, 12, 30, 16, 24, 36, 60, 210, 32, 48, 72, 120, 180, 420, 2310, 64, 96, 144, 216, 240, 360, 900, 840, 1260, 4620, 30030, 128, 192, 288, 432, 480, 720, 1080, 1800, 1680, 2520, 6300, 9240, ...}

A046523 Smallest number with same prime signature as 

n

.

 

{1, 2, 2, 4, 2, 6, 2, 8, 4, 6, 2, 12, 2, 6, 6, 16, 2, 12, 2, 12, 6, 6, 2, 24, 4, 6, 8, 12, 2, 30, 2, 32, 6, 6, 6, 36, 2, 6, 6, 24, 2, 30, 2, 12, 12, 6, 2, 48, 4, 12, 6, 12, 2, 24, 6, 24, 6, 6, 2, 60, 2, 6, 12, 64, 6, 30, 2, ...}

A095904 Triangular array of natural numbers (greater than 

1

) arranged by prime signature.

 

{2, 3, 4, 5, 9, 6, 7, 25, 10, 8, 11, 49, 14, 27, 12, 13, 121, 15, 125, 18, 16, 17, 169, 21, 343, 20, 81, 24, 19, 289, 22, 1331, 28, 625, 40, 30, 23, 361, 26, 2197, 44, 2401, 54, 42, 32, 29, 529, 33, 4913, 45, ...}

See also

• Prime factorization
• Orderings of prime signatures
• Ordered prime signatures (where the order of exponents matters, corresponding to compositions of 

  Ω (n)

  )
• Orderings of ordered prime signatures

External links

• Will Nicholes, List of the first 400 prime signatures.
• Will Nicholes, Iterative mapping of prime signatures.