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
will equal
for some integer 
(the quotient), as
guaranteed by the Division Algorithm. Then . 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 >