Semiprime

Examples and variations

The semiprimes less than 100 are: Semiprimes that are not square numbers are called discrete, distinct, or squarefree semiprimes:

The semiprimes are the case k=2 of the k-almost primes, numbers with exactly k prime factors. However some sources use "semiprime" to refer to a larger set of numbers, the numbers with at most two prime factors (including unit (1), primes, and semiprimes). These are:

Formula for number of semiprimes

A semiprime counting formula was discovered by E. Noel and G. Panos in 2005.{{cite web | access-date = 16 December 2024}} Let \pi_2(n) denote the number of semiprimes less than or equal to n. Then \pi_2(n) = \sum_{k=1}^{\pi \left(\sqrt n\right) } \left[\pi\left(\frac{n}{p_k}\right) - k + 1 \right] where \pi(x) is the prime-counting function and p_k denotes the kth prime.{{cite journal

Properties

Semiprime numbers have no composite numbers as factors other than themselves. For example, the number 26 is semiprime and its only factors are 1, 2, 13, and 26, of which only 26 is composite.

For a squarefree semiprime n=pq (with p\ne q) the value of Euler's totient function \varphi(n) (the number of positive integers less than or equal to n that are relatively prime to n) takes the simple form \varphi(n)=(p-1)(q-1)=n-(p+q)+1. This calculation is an important part of the application of semiprimes in the RSA cryptosystem. For a square semiprime n=p^2, the formula is again simple: \varphi(n)=p(p-1)=n-p.

Applications

In 1974 the Arecibo message was sent with a radio signal aimed at a star cluster. It consisted of 1679 binary digits intended to be interpreted as a 23 \times 73 bitmap image. The number 1679=23\cdot 73 was chosen because it is a semiprime and therefore can be arranged into a rectangular image in only two distinct ways (23 rows and 73 columns, or 73 rows and 23 columns).

References

References

1. {{cite OEIS. A001358
2. Nowicki, Andrzej. (2013-07-01). "Second numbers in arithmetic progressions".
3. Conway, J. H.. (2008-06-18). "Counting Groups: Gnus, Moas, and Other Exotica."".
4. Stewart, Ian. (2010). "Professor Stewart's Cabinet of Mathematical Curiosities". Profile Books.
5. French, John Homer. (1889). "Advanced Arithmetic for Secondary Schools". Harper & Brothers.
6. (2013). "The Mathematics of Encryption: An Elementary Introduction". American Mathematical Society.
7. "The RSA Factoring Challenge is no longer active". RSA Laboratories.
8. du Sautoy, Marcus. (2011). "The Number Mysteries: A Mathematical Odyssey through Everyday Life". St. Martin's Press.