A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The top level ithprime(i) command returns the ith prime. For example, the first ten primes are given by the following sequence:

$\mathrm{seq}\left(\mathrm{ithprime}\left(i\right)\,i\=1..10\right)$

The top level isprime command determines if a given number is prime:

$\mathrm{isprime}\left(28\right)$

$\mathrm{isprime}\left(29\right)$

The Divisors command can also verify that a number is prime. If the divisors of a given integer are only 1 and itself, then the number is prime.

$\mathrm{Divisors}\left(28\right)$

$\mathrm{Divisors}\left(29\right)$

The SumOfDivisors command returns the sum of the divisors of an integer:

$\mathrm{SumOfDivisors}\left(28\right)$

The top level ifactor command gives the integer factorization of an integer:

$\mathrm{ifactor}\left(28\right)$

The PrimeFactors command returns a list of factors for a given integer that are primes without multiplicity:

$\mathrm{PrimeFactors}\left(28\right)$

The NumberOfPrimeFactors command returns the number of Prime Factors of an integer, counted with multiplicity:

$\mathrm{NumberOfPrimeFactors}\left(28\right)$

The top level nextprime (or prevprime) commands return the next (or previous) prime number after (or before) the given integer:

$\mathrm{nextprime}\left(29\right)$

The PrimeCounting command returns the number of primes less than a given integer:

$\mathrm{PrimeCounting}\left(31\right)$

Two integers are relatively prime (coprime) if their greatest common divisor (gcd) is 1. The AreCoprime command tests if a sequence of integers or Gaussian integers are coprime:

$\mathrm{AreCoprime}\left(5\,8\right)$

$\mathrm{AreCoprime}\left(2\,8\right)$

The following plot shows the coprimes for the integers 1 to 15:

An integer is called square-free if it is not divisible by the square of another number other than 1. All prime numbers are square-free:

$\mathrm{IsSquareFree}\left(31\right)$

$\mathrm{IsSquareFree}\left(7\cdot 101\right)$

$\mathrm{IsSquareFree}\left(3\cdot 7^2\right)$

Mersenne Primes

Mersenne Primes are prime numbers that are one less than a power of 2. These are numbers of the form: ${\mathit{M}}_{\mathit{n}}\mathbf{\=}{\mathbf{2}}^{\mathit{n}}\mathbf{-}\mathbf{1}$, where n is a positive integer. The IthMersenne(i) command returns the exponent for the ith Mersenne prime number: $\mathrm{IthMersenne}\left(4\right)$ $7$ (1.1.1) $2^7-1$ $127$ (1.1.2) $\mathrm{isprime}\left(2^7-1\right)$ $\mathrm{true}$ (1.1.3) The nextprime command returns the next prime number after the current value. $\mathrm{nextprime}\left(127 \right)$ $131$ (1.1.4) The IsMersenne(n) command checks if a positive integer, n, is a Mersenne exponent such that $2^n-1$ is a Mersenne prime: $2^2-1$ $3$ (1.1.5) $\mathrm{IsMersenne}\left(2\right)$ $\mathrm{true}$ (1.1.6) $2^{11}-1$ $2047$ (1.1.7) $\mathrm{IsMersenne}\left(11\right)$ $\mathrm{false}$ (1.1.8) $\mathrm{ifactor}\left(2^{11}-1\right)$ $\left(23\right)\left(89\right)$ (1.1.9)

The vertices of the Calkin-Wilf tree are labeled with rational numbers $\frac{a}{b}$. The root vertex is defined to be $\frac{1}{1}$ and for any vertex $\frac{a}{b}$, its children are $\frac{a}{a\+b}$ and $\frac{a\+b}{b}$. Every positive rational number occurs exactly once in the Calkin-Wilf tree.

The first 16 terms of the Calkin-Wilf sequence are:

$\mathrm{seq}\left(\mathrm{CalkinWilfSequence}\left(n\right)\,n\=1..16\right)$

The Calkin-Wilf tree can be created using the GraphTheory package:

$$\begin{gathered} \mathrm{DrawTree}≔\mathbf{proc}\left(n\,\left\{\mathrm{graphstyle}≔\mathrm{tree}\right\}\right) \\ \mathbf{local} \mathrm{cwseq}\, \mathrm{cwgraph}\; \\ \mathrm{cwseq} ≔ \left(x \to \mathrm{convert}\left( x\, \'\mathrm{string}\' \right)\right)~\left( \left[ \mathrm{seq}\left( \mathrm{NumberTheory}:-\mathrm{CalkinWilfSequence}\left(i\right)\, i \= 1 .. n \right) \right] \right)\: \\ \mathrm{cwgraph} ≔ \mathrm{GraphTheory}:-\mathrm{Graph}\left( \left\{ \mathrm{seq}\left( \left\{ \mathrm{cwseq}\left[i\right]\, \mathrm{cwseq}\left[ \mathrm{floor}\left( \left(1\/2\right) \cdot i \right) \right] \right\}\, i \= 2 .. n \right) \right\} \right)\: \\ \mathbf{return} \mathrm{GraphTheory}:-\mathrm{DrawGraph}\left(\mathrm{cwgraph}\,\mathrm{style}\=\mathrm{graphstyle}\right)\; \\ \mathbf{end} \mathbf{proc}\: \end{gathered}$$