Number Theory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : System : Information : Updates : Maple 2016 : updates/Maple2016/NumberTheory

Number Theory

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.

 

withNumberTheory

AreCoprime,CalkinWilfSequence,CarmichaelLambda,ContinuedFraction,ContinuedFractionPolynomial,CyclotomicPolynomial,Divisors,FactorNormEuclidean,HomogeneousDiophantine,ImaginaryUnit,InhomogeneousDiophantine,IntegralBasis,InverseTotient,IsCyclotomicPolynomial,IsMersenne,IsSquareFree,IthMersenne,JacobiSymbol,KroneckerSymbol,Landau,LargestNthPower,LegendreSymbol,Möbius,ModExtendedGCD,ModularLog,ModularRoot,ModularSquareRoot,Moebius,MultiplicativeOrder,Möbius,NearestLatticePoint,NextSafePrime,NumberOfIrreduciblePolynomials,NumberOfPrimeFactors,Ω,Φ,PrimeCounting,PrimeFactors,PrimitiveRoot,PseudoPrimitiveRoot,QuadraticResidue,RepeatingDecimal,RootsOfUnity,SumOfDivisors,SumOfSquares,ThueSolve,Totient,λ,μ,φ,π,σ,τ,ϕ

(1)

 

MathApps


Sieve of Eratosthenes


abc Conjecture


Collatz Conjecture


Fibonacci Numbers


Goldbach's Conjecture


Pascal's Triangle


GCD and Euclid's Algorithm


Euler's Identity


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:

 

Repeated Decimal

1. 

Enter a fraction. For example, enter 3/7.

37

2. 

Right-click (Control-click for Macintosh) the fraction, and then select Show as Repeating Decimal.

37= repeated decimal 0.428571&conjugate0;

Continued Fraction

1. 

Enter a fraction. For example, enter 3/7.

37

2. 

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

Examples: Prime Numbers

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:

seqithprimei,i=1..10

2,3,5,7,11,13,17,19,23,29

(1.1)

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

isprime28

false

(1.2)

isprime29

true

(1.3)

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.

Divisors28

1,2,4,7,14,28

(1.4)

Divisors29

1,29

(1.5)

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

SumOfDivisors28

56

(1.6)


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

ifactor28

227

(1.7)

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

PrimeFactors28

2,7

(1.8)

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

NumberOfPrimeFactors28

3

(1.9)

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

nextprime29

31

(1.10)

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

PrimeCounting31

11

(1.11)

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:

AreCoprime5,8

true

(1.12)

AreCoprime2,8

false

(1.13)

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:

IsSquareFree31

true

(1.14)

IsSquareFree7101

true

(1.15)

IsSquareFree372

false

(1.16)

Mersenne Primes

Mersenne Primes are prime numbers that are one less than a power of 2. These are numbers of the form:

Mn=2n1, where n is a positive integer.

The IthMersenne(i) command returns the exponent for the ith Mersenne prime number:

IthMersenne4

7

(1.1.1)

271

127

(1.1.2)

isprime271

true

(1.1.3)

The nextprime command returns the next prime number after the current value.

nextprime127 

131

(1.1.4)

The IsMersenne(n) command checks if a positive integer, n, is a Mersenne exponent such that 2n1 is a Mersenne prime:

221

3

(1.1.5)

IsMersenne2

true

(1.1.6)

2111

2047

(1.1.7)

IsMersenne11

false

(1.1.8)

ifactor2111

2389

(1.1.9)

Examples: Arithmetic Functions

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.

Totient21,φ21,ϕ21

12,12,12

(2.1.1)

To visualize the first thousand values for φn:

plots:-pointplotseqn,Totientn,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:

Möbius function

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:-pointplotseqn,Moebiusn,n=1..75,labels=n,μn, symbolsize=15, color=OrangeRed,size=600,400,tickmarks=default,1,0,1

Examples: Calkin-Wilf Tree

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:

seqCalkinWilfSequencen,n=1..16

1,12,2,13,32,23,3,14,43,35,52,25,53,34,4,15

(3.1)

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

DrawTreeprocn,graphstyletree     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

DrawTree15;

DrawTree31, graphstyle=spring;