# 4. The Frobenius number – Starting to Program¶

## 4.1. Exploration Question:¶

```
Suppose you have coins of value a cents and b cents. What amounts of money can you get by combining these?
Q: Can you think of how to formulate our question mathematically?
A: Given positive integers a and b, for which positive integers n does there exist non-negative integers x and y such that n=ax+by?
```

We will solve this problem by first trying some easy cases such as , , or , , or , to begin. We will explore the first two cases , , and , together so everyone get an idea of what we are doing. We will then group ourselves in small groups to explore more cases.

As we shall discover in our exploration, when there is such an
, there is also an such that for all
greater than or equal to will also work, but does
not. We will call the **conductor** of the set
and as the **Frobenius number**. (The
problem is known as the Frobenius problem or the coin problem as well.)

The **conductor** of two positive integers is the smallest
integer such that all greater than or equal to
can be written as .

The **Frobenius** number of two positive integers is the
largest integer such that there do not exist positive integers
and with .

Your goal is to experiment with this. Experiment! For a given pair of positive integers a and b can you think of some questions we can ask? For example we can ask things like the following:

Is there a conductor?

What is the conductor?

How many numbers n can be written ax+by?

Can you think of more questions to ask? We will group ourselves into groups and try to explore our questions on simple cases as we did before.

Now, soon we’ll be using the computer to help explore more complex examples like . However, experimental mathematics needs only curiosity and persistence. And you don’t need a computer to do that.

Finally we will go to the computer laboratory and introduce *SageMath* -
you can use the Sage notebook below and upload it to try it yourself!

You should do this for tomorrow :

Is there a conductor for the sets , , and ? If so, what is it? Explore!

Is there a Frobenius number for the sets , , and ? If so, what is it? Explore!

Can you list all the set of numbers that can not be written as , and ? When is this set finite?

Write down a step-by-step explanation of the conductor of . You should both compute it and explain how you know that all N greater than the conductor really can be written as for some .

Try leaning how to load a sage jupyter notebook and how to start your own sage notebook.

We’ve already been trying out some experimental mathematics; now it’s
time to see how one might start doing this with the computer. Again,
**please feel free to try things**. Don’t just try to follow the
lecture.

By the way, the acronym “SAGE” stands for “Software for Algebra and

Geometry Experimentation”.

We saw some proof earlier. Let’s start our exploration of programming by recalling a theorem some of you may not have known needs to be a theorem.

**Theorem (Division Algorithm)**:

In words, if you divide an integer by a positive integer
, you will always get an integer remainder that is
nonnegative, but less than . Further, the remainder
is *unique*.

For example, if then

We can prove this using the definition of divisibility and the “Well-Ordering Principle”, but I do not assume you are too familiar with induction and this principle.

By the way, notice that this relates directly to something we proved earlier; in this event, . This leads directly to the Euclidean algorithm for computing the GCD. We can check this works using Sage.

The code `a % b`

will return the remainder upon division of
by . In other words, the result is the unique integer
such that

for some integer (the quotient), as guaranteed by the Division Algorithm. Then

will equal . For example,

```
r = 14 % 3
r
```

```
q = (14 - r ) /3
q
```

It is also possible to get both the quotient and remainder at the same
time with the `.quo_rem()`

method (quotient and remainder).

```
a = 14
b = 3
a.quo_rem ( b )
```

A remainder of zero indicates divisibility. So `(a % b) == 0`

will
return `True`

if divides , and will otherwise
return False.

```
(20 % 5) == 0
```

```
(17 % 4) == 0
```

The `.divides()`

method is another option:

```
c = 5
c.divides (20)
```

```
d = 4
d . divides (17)
```

The greatest common divisor of a and b is obtained with the command
`gcd(a, b)`

, where in our first uses, a and b are integers.

```
gcd (2776 , 2452)
```

We can use the gcd command to determine if a pair of integers are relatively prime

```
a = 31049
b = 2105
gcd (a , b ) == 1
```

```
a = 3563
b = 2947
gcd (a , b ) == 1
```

The command `xgcd(a,b)`

(“eXtended GCD”) returns a triple where the
first element is the greatest common divisor of a and b (as with the
gcd(a,b) command above), but the next two elements are values of
and such that .

```
xgcd (633 ,331)
```

Portions of the triple can be extracted using [ ] (“indexing”) to access the entries of the triple, starting with the first as number . For example, the following should always return the result True, even if you change the values of and . Try changing the values of and below, to see that the result is always True.

```
a = 633
b = 331
extended = xgcd (a , b )
g = extended [0]
r = extended [1]
s = extended [2]
g == r * a + s * b
```

The method `.is_prime()`

will determine if an integer is prime or not.

```
a = 117371
a . is_prime()
```

```
b = 14547073
b . is_prime()
```

The command `random_prime(a, proof=True)`

will generate a random prime
number between and . Experiment by executing the
following two compute cells several times. (Replacing `proof=True`

by
`proof=False`

will speed up the search, but there will be a very,
very, very small probability the result will not be prime.)

```
a = random_prime (10^21 , proof = True )
a
```

```
a.is_prime ()
```

The commands `next_prime(a)`

and `previous_prime(a)`

are other ways
to get a single prime number of a desired size. Try it Yourself.

In addition to checking if integers are prime or not, or generating prime numbers, Sage can also decompose any integer into its prime factors, as described by the Fundamental Theorem of Arithmetic

```
a = 2600
a.factor()
```

So $2600 = 2^3 × 5^2 × 13 $ and this is the unique way to write 2600 as a product of prime numbers (other than rearranging the order of the primes themselves in the product).

## 4.2. Lists And Loops¶

Now let’s start talking the basics of how one might go about exploring
questions with *SageMath*.

### 4.2.1. Lists¶

The command `prime_range(a, b)`

returns an ordered list of all the
primes from to , inclusive. For example,

```
prime_range (500 , 550)
```

While Sage will print a factorization nicely, it is carried internally as a list of pairs of integers, with each pair being a base (a prime number) and an exponent (a positive integer). Study the following carefully, as it is another good exercise in working with Sage output in the form of lists

```
a = 2600
a.factor ()
```

```
a = 2600
factored = a . factor ()
first_term = factored [0]
first_term
```

```
second_term = factored [1]
second_term
```

```
third_term = factored [2]
third_term
```

```
first_prime = first_term [0]
first_prime
```

```
first_exponent = first_term [1]
first_exponent
```

The next compute cell reveals the internal version of the factorization
by asking for the actual list. And we show how you could determine
exactly how many terms the factorization has by using the length
command, `len()`

.

```
list(factored)
```

```
len(factored)
```

Can you extract the next two primes, and their exponents, from a?

In *SageMath*, it turns out that making a list of lists is a good way to
organize our data, by using the table command.

```
L = [[(3,4),6,3],[(4,5),12,6],[(3,6),'none',oo]]
table(L,header_row=["a,b",'conductor','number not possible'])
```

```
L = [["$(3,4)$","$6$","$3$"],["$(4,5)$","$12$","$6$"],["$(3,6)$",'none',"$\infty$"]]
table(L,header_row=["$a,b$",'conductor','number not possible'])
```

This is a good use for lists - making things easy to communicate to others!

### 4.2.2. Loops¶

A related concept you should have also seen in your previous Python
class is a *loop*. Loops make doing tedious things many times easier.
Here is an example getting the determinant of powers of a matrix. I
*could* do it “by hand”.

```
A = matrix([[1,2],[3,4]])
print det(A^0)
print det(A^1)
print det(A^2)
print det(A^3)
print det(A^4)
```

This is not terrible, but it’s not exactly nice either. Instead, let’s use a loop.

```
for i in [0,1,2,3,4]:
print det(A^i)
```

What did we do?

For (each) in the list (ordered set) [0,1,2,3,4], (return)
. The square brackets created a list, and the powers of the
original matrix come in the same order as the list. Remember, the colon
in the first line and the indentation in the second line are
**extremely** important; they are the basic syntactical structure of
Python.

```
for i in [0,1,2,3,4]
A^i
```

```
for i in [0,1,2,3,4]:
A^i
```

### 4.2.3. Streamlining¶

For the curious, it’s worth knowing there are quicker ways to make the possible values for quicker to write. Here are two possible options.

```
for i in [0..4]:
print det(A^i)
```

```
for i in range(5):
print det(A^i)
```

Notice that the `range(5)`

starts counting at zero and ends *before*
reaching five; this is standard behavior. You can get other behavior,
too.

```
range(3, 23, 2); [3,5..21]
```

### 4.2.4. List Comprehensions¶

There is a very powerful way to create such lists in a way that looks
like a loop. This way also looks like mathematical notation. It is
called a *list comprehension*. We start with a relatively easy example:

Who hasn’t written something like this at some point? Here’s how to translate this into Sage:

```
[ n^2 for n in [3..12] ]
```

The notation is easiest if you think of it mathematically; “The set of , for (any) in the range between 3 and 12.”

This sort of construction works for lots of things of mathematical interest, of course - such as our first example.

```
[ det(A^i) for i in [0..4] ]
```

How could we use lists and loops to explore the conductor?

Can I list

*all*numbers of the form ?How would I list some numbers of this form? (Hint: fix one of the variables).

How would I list more numbers of this form? (Hint: make a loop inside of a loop).

Can you turn this into a list and not just a loop?

I know you have done dictionaries in your python course. Can you try to use dictionaries for this?

## 4.3. Defining Functions (Extending Sage)¶

Hopefully you will experience success with your exploration! Still, it is kind of annoying that there isn’t just a simple command for it. In fact, it is often the case that Sage can do something, but doesn’t have a simple command for it. For instance, you might want to take a matrix and output the square of that matrix minus the original matrix.

```
A = matrix([[1,2],[3,4]])
A^2 - A
```

How might one do this for other matrices? Of course, you could just always do again and again. But this would be tedious and hard to follow, as with so many things that motivate a little programming. Here is how Python and Sage solve this problem.

```
def square_and_subtract(mymatrix):
return mymatrix^2 - mymatrix
```

```
square_and_subtract(A)
```

```
square_and_subtract(matrix([[1.5,0],[0,2]]))
```

As a technical matter, this is only a *Python function*, not a Sage
symbolic function (callable expression). That means it does not have
access to all the same things as we discussed earlier today. That is
okay, as it is often better for a function not to live in the symbolic
algebra world.

What if we are worried about forgetting what this function does? To be
fair, we chose a great name for it. Still, just in case, we can provide
a documentation string, putting it in triple quotes `"""`

.

```
def square_and_subtract(mymatrix):
"""
Return `A^2-A`
"""
return mymatrix^2-mymatrix
```

```
square_and_subtract?
```

That’s pretty cool! And potentially quite helpful, especially if the
function is complicated. The typesets properly because we put
it in backticks `A`

. (For the *real* experts, one can use “raw
strings” to include backslashes (say, for LaTeX) in these documentation
strings, like r”““:raw-latex:`\frac{a}{b}`””“. Look at the
documentation for Bessel functions for some great examples). A very
careful reader *may* have noticed that there is nothing that requires
the input ‘mymatrix’ to be a matrix. Sage will just try to square
whatever you give it and subtract the original thing.

```
square_and_subtract(sqrt(5))
```

Functions are very flexible in what input they can allow or require, as well as what output they give. Below are three examples that show some of this flexibility. There are many other good resources out there.

```
def func1( y, z ):
return y+z
```

```
def func2( y, z=3):
return y+z
```

```
def func3( y ):
return y, y+3
```

Could we use functions to explore our question? 1. Could you write a function that lists all numbers of the form , given some range of ? 2. What about of the form ? 3. What about of the form ? Note that here you will have TWO ranges to consider, that of and that of . 4. Are your lists sorted or not? Can you think of a way to fix that? 5. What about for the form ? 6. What about for ?

## 4.4. Exercises¶

These exercises are about investigating basic properties of the integers, something we will frequently do when investigating groups.

Use the

`next_prime()`

command to construct two different 8-digit prime numbers and save them in variables named a and b.Use the

`.is_prime()`

method to verify that your primes a and b are really prime.Verify that 1 is the greatest common divisor of your two primes from the previous exercises.

Find two integers that make a “linear combination” of your two primes equal to 1. Include a verification of your result.

Determine a factorization into powers of primes for c = 4598037234

Write a computer program that will implement the Euclidean algorithm. The program should accept two positive integers a and b as input and should output gcd(a, b) as well as integers and such that

< 2. Review of Python programming|Table of contents | 4. Starting To Program >