Basic Programming in GAP

Return to Index

We assume that the reader has a computer on which GAP is installed.

The tutorial which follows develops some basic programming with the GAP language. It does not use any functions concerning groups, rings, or fields.

GAP code is shown like this.

[Press ?? to see GAP output]

You can also choose to see a page showing ALL GAP output.

Arithmetic

The following commands need no explanation.

(2 + 3)*(7 - 5); ??

2*3/66; ??

2^100-1; ??

5/2 + 3/5; ??

66/1512 + 1/252; ??

Sqrt(100); ??

Sqrt(100) in Integers; ??

Sqrt(99) in Integers; ??

Let us comment here regarding spaces in the input. We could (and often do) leave spaces round the contents of brackets. For example

Sqrt( 100 ); ??

More spaces (although we wouldn’t in general suggest that anyone does this) are still OK.

Sqrt( 100 ); ??

We can even leave a space before the (.

Sqrt ( 100 ); ??

However, we obviously can’t leave spaces in the middle of commands or numbers. For example the following will produce an error.

Sqr t(100); ??

Sqrt(10 0); ??

We return to giving commands for the manipulation of numbers.

(66/1512 + 1/252) in Rationals; ??

(66/1512 + 1/252) in Integers; ??

We can find Greatest Common Divisors of integers

Gcd(1512,1215); ??

Gcd(1020,1512,1215); ??

and their Least Common Multiples.

Lcm(1512,1215); ??

Lcm(1020,1512,1215); ??

Given two integers a, b with greatest common divisor d we can find x, y such that xa + yb = d with Gcdex(a,b):

a:= 1512;; b:= 1215;; g:= Gcdex(a,b); ??

Note that “rec” indicates a record with various components.

d:= g.gcd;; x:= g.coeff1;; y:= g.coeff2;; d= a*x+b*y; ??

Notice the use of ;; to avoid GAP printing back the input line.

To work mod n we can use the obvious method.

(5 + 7) mod 9; ??

3^7 mod 10; ??

However, to compute large powers mod n it is better to use PowerModInt.

PowerModInt(2, 1000, 10); ??

gives the same result as

2^1000 mod 10; ??

What do you think PowerModInt does and why do you think it might be faster?

So if we want to compute 1000²⁵¹²⁹¹ mod 251291 we should use

PowerModInt(1000, 251291, 251291); ??

Is this the answer you expect? Try

PowerModInt(1001, 251291, 251291); ??

PowerModInt(1002, 251291, 251291); ??

PowerModInt(1003, 251291, 251291); ??

What well known theorem does this illustrate?

What about

PowerModInt(1000, 251293, 251293); ??

Another useful function for working with integers is RootsMod which finds modular roots.

RootsMod(4, 15); ??

finds all the square roots of 4 mod 15. It has the same effect as

RootsMod(4, 2, 15); ??

For the cube roots of 4 mod 15 use

RootsMod(4, 3, 15); ??

In fact the RootsMod function returns a set. We now look further at sets and lists.

Lists

GAP writes its lists with [ ].

We can define a list using a range.

r_1:= [ 1..10 ]; ??

This list r₁ consists of all the integers from 1 to 10. For example:

5 in r_1; ??

11 in r_1; ??

The list r₁ contains Length(r_1) or Size(r_1) elements

Length(r_1); ??

GAP will also use ranges to produce an arithmetic progression. For example:

r_2:=[1,3..17]; ??

We can get GAP to display the elements of the list.

Elements(r_2); ??

More examples:

r_3:=[2,4..16]; ??

Elements(r_3); ??

r_4:=[5,8..35]; ??

Elements(r_4); ??

We can also write out all the elements to define a list:

s:= [ 1, 8, 6, 2 ]; ??

GAP will do a form of arithmetic with lists.
We can generate the same arithmetic progression as before:

2*[1..9]-1; ??

We can add or subtract lists — even of different lengths

[1,2,3]+[4,5]; ??

We can add new elements to lists. GAP does not return any output to the screen.

t:=[ 1, 2, 2, 3, 4, 5, 6 ]; ??

Add(t, 10);

But we can see what has happened:

t; ??

The command Add will simply add an entry to the end of an existing list. If we want to create a new list which is equal to the original list but has an added element we can first make a copy of the list and then add the element. For example

lis:= [1,2,1,2,5,9]; ??

newlis:= ShallowCopy(lis); ??

GAP has various commands for copying and ShallowCopy is the one we need here. We can now modify our copy without changing the original list.

Add(newlis, -5);

lis; newlis; ??

We can filter out elements from a list with particular properties. For example to find all the elements in the list t which are prime we input

t1:= Filtered(t, IsPrimeInt); ??

To filter out the elements which have a given property, one must use Filtered(t, f) where f is a function which takes the value true on the elements to be filtered. We will discuss functions later.

Sets

GAP will sometimes consider a list as a set, but often needs to convert it before applying set operations.

s:= [ 1, 8, 6, 2 ]; ??

We test if it is a set:

IsSet(s); ??

GAP will only count a list of integers as a set if it is ordered increasingly and contains no repetitions. The next example has a repeated entry.

t:= [ 1, 2, 2, 3, 4, 5, 6 ]; ??

IsSet(t); ??

Of course s and t are lists and we can create sets from them:

ss:= Set(s); ??

tt:= Set(t); ??

Notice that this operation removes repetitions and puts the elements into increasing order.

The usual set operations work and GAP treats the lists as if they were sets before applying the operations:

Intersection(s, t); ??

IsEqualSet(Intersection(s,t),Intersection(ss,tt)); ??

Union(s, t); ??

Difference(s, t); ??

Difference(t, s); ??

To add an element to the set ss we use AddSet. Again we get no output.

AddSet(ss, 4);

ss; ??

Loops

We begin with elementary loops.

for i in [1..10] do Print(i); od; ??

Notice that the output is 12345678910. Suppose we want to print a space between consecutive numbers.

for i in [1..10] do Print(i," "); od; ??

Suppose we want to print each number on a separate line. We use "\n" to make a new line.

for i in [1..10] do Print(i, "\n"); od; ??

A slightly more useful loop might be:

for i in [1..10] do Print(i," squared is ",i^2,"\n"); od; ??

Notice that we have put spaces in ” squared is ” so that it displays properly.

Conditionals

We now introduce conditionals into our loop. We test to see if an integer i is prime and if so we print it.

for i in [1..20] do if IsPrimeInt(i) then Print(i, " is prime ", "\n"); fi; od; ??

Of course most even numbers cannot be prime so we could reduce the number of times the loop is run by only looking at odd numbers. However, 2 will not be listed!

for i in [1, 3 .. 19] do if IsPrimeInt(i) then Print(i," is prime ","\n"); fi; od; ??

The next loop prints the primes in the first 50 terms of the Fibonacci sequence.

for i in [1..50] do if IsPrimeInt(Fibonacci(i)) then Print(Fibonacci(i)," is prime ","\n"); fi; od; ??

We can test whether numbers less than 1000 are primes in another way, rather than use IsPrimeInt. For example

13 in Primes; ??

Fibonacci(13) in Primes; ??

Note however that Primes only contains the 168 primes less than 1000. For example

IsPrimeInt(1597); ??

1597 in Primes; ??

Functions

We move on to functions. The following code defines a function that simply squares the argument it is given.

squared:= function(n); return n^2; end; ??

If you want to see the function written out fully, you can ask GAP to Print it.

Print(squared); ??

Try

squared(12345); ??

to see the result. There are simpler ways to write easy functions like this. For example

cubed:= n -> n^3; ??

Print(cubed); ??

cubed(123456); ??

We can produce lists of cubes as follows:

List( [1..10], cubed ); ??

This is a very useful construction. Here are a few more examples.
First the squares of the even numbers between 2 and 14.

List( [2,4..14], n->n^2 ); ??

A more complicated example

f:=function(n); if n mod 2 =0 then return n^2; else return n^3; fi; end; ??
List( [1..20], f); ??

If we define a function which returns true or false, we may use this to filter a list.

is1mod4:=function(n); if n mod 4 = 1 then return true; else return false; fi; end; ??

Filtered([1..20], is1mod4); ??

A famous sequence

Next we write a function which returns n/2 if n is even and 3n+1 if n is odd.

There is a famous open question which asks whether one always reaches 1 if one starts with any number and successively applies that rule. For example, if we start with 3 we get

3, 10, 5, 16, 8, 4, 2, 1

f:= function(n); if n mod 2 = 0 then return n/2; else return 3*n+1; fi; end; ??

Let us now write a function t to return the number of steps that are required to reach 1. Note that we define local variables to use in the function. We do this so that if variables with the same name are used elsewhere their value will not be affected by the function. Note that there is no semi-colon before the local variables are listed.

t:= function(i) local k, m; k:= 0; m:= i; while m > 1 do k:= k+1; m:= f(m); od; return k; end; ??

When we wrote the code for the function we put extra spaces at the beginning of each line so that it was easier to see where conditional clauses and loops began and ended.

Let us produce a sequence with i^th entry the number of steps required to reach 1 starting from i.

s:= List( [1..1000], t ); ??

If you don’t want to see the list s then end the line with ;;
The following loop will product the same list s as we just constructed above but of course takes longer to write.

s:= [];; for i in [1..1000] do Add(s, t(i)); od; Print(s, "\n"); ??

Notice the fact that lots of adjacent entries in s are equal. So often beginning with consecutive numbers we find that the same number of steps is required to reach 1. As we reach larger numbers we see three consecutive numbers with this property etc.

We construct a list len whose n^th entry will be the number of times n consecutive numbers take the same number of steps. Note that when we reach the end of the list, we do not know whether the next entry would have been the same as the last one and so we do not count this run.

len:= ListWithIdenticalEntries(20, 0); ??

count:= 1;; for i in [ 2 .. Length(s) ] do if s[i] = s[i-1] then count:= count + 1; else len[count]:= len[count] + 1; count:= 1; fi; od; len; ??

Remove the trailing 0’s in len

i:= Length(len); while len[i] = 0 do Unbind(len[i]); i:= i-1; od; len; ??

For each i print the number of i consecutive integers taking the same number of steps to reach 1.

for i in [1..Length(len)] do Print("There are ",len[i]," runs of length ", i, "\n"); od; ??

We again note that we added spaces in the strings in the Print statement.

Another thing that one can investigate about this problem is the highest number reached by the sequence before it collapses to 1.

Stirling numbers of the second kind

We now investigate Stirling numbers of the second kind. Stirling2(n, r) is the number of ways a set of n elements can be partitioned into r disjoint non-empty subsets.

First we list the these numbers for a fixed n, take n = 12.

l:= List( [1..12], k -> Stirling2(12, k) ); ??

Find the maximum value

m:= Maximum(l); ??

and its position in the list

Position(l, m); ??

Let us now construct a list stir from these lists of Stirling numbers so that the n^th entry of stir is the list of Stirling numbers for a set of n elements. This would give a seriously large output, so we suppress it.

stir:= List( [1..50], n -> List([1..n], k -> Stirling2(n, k)) );;

Now find where the maximum occurs for each n.

for i in [1..Length(stir)] do Print("row ", i, " has maximum in position ", Position(stir[i], Maximum(stir[i])), "\n"); od; ??

It is not easy to predict where the maximum will occur for a given n. However, there is an asymptotic result known, namely that as n rarrow infinity the maximum position tends to n/ln(n).

Divisors of consecutive integers

We now examine a problem which involves elementary number theory.
Are there infinitely many pairs of consecutive integers with the same number of divisors?
Is there an infinite number of pairs of consecutive integers that each have 4 divisors?
We have no hope of solving the problem but let us investigate it.

First note that DivisorsInt(n) returns a list of divisors of n.

DivisorsInt(1512); ??

It is easy to find the number of divisors of n.

Length(DivisorsInt(1512)); ??

For ease of typing let us define f(n) to be the number of divisors of n.

f:= n -> Length(DivisorsInt(n)); ??

Let us look for pairs of consecutive integers with the same number of divisors.

for i in [1..200] do if f(i) = f(i+1) then Print("pair ", i," ", i+1, " has ",f(i), " divisors ", "\n"); fi; od; ??

We can easily move to finding three consecutive integers with the same number of divisors.

for i in [1..200] do if f(i) = f(i+1) and f(i+1)=f(i+2) then Print("triple ", i," ", i+1, " ", i+2," has ", f(i)," divisors ", "\n"); fi; od; ??

Then we can look for even longer runs. This code uses a different kind of loop.

i:=1;; over:=false;; while not over do if f(i) = f(i+1) and f(i+1)=f(i+2) and f(i+2)=f(i+3) and f(i+3)=f(i+4) and f(i+4)=f(i+5) and f(i+5)=f(i+6) then Print("Sequence of length 7 starting ",i," has ",f(i)," divisors \n"); over:=true; fi; i:=i+1; od; ??

As an exercise you may care to turn the above into a function with a parameter n which returns sequences of length nof integers with the same number of divisors.

Can one find such runs of arbitrary length? GAP can help, but won’t tell you the answer!

JOC/EFR January 2003

Return to GAP Instructional Material Index page
See page showing ALL GAP output

CIRCA