The NumberTheory package updates and replaces the numtheory package. There are several new applications and examples that use the new NumberTheory commands and, in addition, many commands have been added to the context menu.
Sieve of Eratosthenes
GCD and Euclid's Algorithm
The Juggler Sequence
The 196 Algorithm
Many NumberTheory commands are available in the right-click context menu. For example, fractions can be shown as either a RepeatingDecimal or a ContinuedFraction:
Enter a fraction. For example, enter 3/7.
Right-click (Control-click for Macintosh) the fraction, and then select Show as Repeating Decimal.
37= repeated decimal 0.428571&conjugate0;
Right-click (Control-click for Macintosh) the fraction, and then select Show as Continued Fraction.
37= continued fraction 0+12+13+0
Examples: Prime Numbers
Examples: Arithmetic Functions
Examples: Calkin-Wilf Tree
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:
The top level isprime command determines if a given number is prime:
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.
The SumOfDivisors command returns the sum of the divisors of an integer:
The top level ifactor command gives the integer factorization of an integer:
The PrimeFactors command returns a list of factors for a given integer that are primes without multiplicity:
The NumberOfPrimeFactors command returns the number of Prime Factors of an integer, counted with multiplicity:
The top level nextprime (or prevprime) commands return the next (or previous) prime number after (or before) the given integer:
The PrimeCounting command returns the number of primes less than a given integer:
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:
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:
Mersenne Primes are prime numbers that are one less than a power of 2. These are numbers of the form:
Mn=2n−1, where n is a positive integer.
The IthMersenne(i) command returns the exponent for the ith Mersenne prime number:
The nextprime command returns the next prime number after the current value.
The IsMersenne(n) command checks if a positive integer, n, is a Mersenne exponent such that 2n−1 is a Mersenne prime:
Euler's Totient Function
Euler's totient function is an arithmetic function that counts the positive integers less than or equal to a given value n that are coprime to n. For a positive integer n, another number k is said to be coprime, or relatively prime, if the greatest common divisor gcdn,k=1. For example, 14 and 15 are coprime because the gcd of 14 and 15 is 1, but 14 and 21 are not coprime since their gcd is 7.
Euler's totient function is also known as Euler's phi function, denoted as φn or ϕn. As such, phi(n) and varphi(n) are aliases for the Totient command.
To visualize the first thousand values for φn:
plots:-pointplotseq⁡n,Totient⁡n,n=2..1000,labels=n,φn,symbol=circle, color=Niagara BlueGreen,size=600,golden
The PrimeCounting(n) (or pi(n)) command returns the number of primes less than an integer n. The following plot compares pi(n) with phi(n) for the first 40 values for n:
The Möbius function is defined as a multiplicative arithmetic function, μr, where:
μr= 1 when r is a square-free positive integer with an even number of prime factors
μr= −1 when r is a square-free positive integer with an odd number of prime factors
μr= 0 when r has a squared prime factor
For example, μ2 = −1 because 2 is a square-free positive integer which has 1 prime factor. μ4 = 0 since 4 is not a square-free positive integer.
The first 75 values for the Möbius function are plotted below:
plots:-pointplot⁡seq⁡n,Moebiusn,n=1..75,labels=n,μn, symbolsize=15, color=OrangeRed,size=600,400,tickmarks=default,−1,0,1
The vertices of the Calkin-Wilf tree are labeled with rational numbers ab. The root vertex is defined to be 11 and for any vertex ab, its children are aa+b and a+bb. Every positive rational number occurs exactly once in the Calkin-Wilf tree.
The first 16 terms of the Calkin-Wilf sequence are:
The Calkin-Wilf tree can be created using the GraphTheory package:
DrawTree≔procn,graphstyle≔tree local cwseq, cwgraph; cwseq ≔ x → convert x, 'string' ~ seq NumberTheory:-CalkinWilfSequencei, i = 1 .. n : cwgraph ≔ GraphTheory:-Graph seq cwseqi, cwseq floor 1/2 ⋅ i , i = 2 .. n : return GraphTheory:-DrawGraphcwgraph,style=graphstyle; end proc:
n = 15
n = 31
Download Help Document