This site is supported by donations to The OEIS Foundation.

Prime signatures

From OeisWiki
(Redirected from Prime signature)
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


A positive integer with prime factorization

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
pk
have prime signature
{k}
.

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

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 {1}
3 {1}
4 {2}
5 {1}
6 {1,1}
7 {1}
8 {3}
9 {2}
10 {1,1}
11 {1}
12 {2,1}
13 {1}
14 {1,1}
15 {1,1}
16 {4}
17 {1}
18 {2,1}
19 {1}
20 {2,1}
21 {1,1}
22 {1,1}
23 {1}
24 {3,1}
25 {2}
26 {1,1}
27 {3}
28 {2,1}
29 {1}
30 {1,1,1}
The prime signature of
n
is a partition of
Ω (n)
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

is

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

Notes

  1. D. A. Goldston, S. W. Graham, J. Pintz, C. Y. Yıldırım, Small gaps between almost primes, the parity problem and some conjectures of Erdős on consecutive integers, International Mathematics Research Notices 7 (2011), pp. 1439-1450.
  2. Ross D. King, Numbers as data structures: the prime successor function as primitive, 2011.

External links