You are currently browsing the category archive for the ‘computing’ category.
Elliptical Curve Cryptography
Elliptical curves are a very important new area of mathematics which have been greatly explored over the past few decades. They have shown tremendous potential as a tool for solving complicated number problems and also for use in cryptography.
Andrew Wiles, who solved one of the most famous maths problems of the last 400 years, Fermat’s Last Theorem, using elliptical curves. In the last few decades there has also been a lot of research into using elliptical curves instead of RSA encryption to keep data transfer safe online. So, what are elliptical curves? On a simple level they can be regarded as curves of the form:
y² = x³ +ax + b
If we’re being a bit more accurate, we also need 4a³ + 27b² ≠ 0. This stops the graph having “singular points” which cause problems with the calculations. We also have a “point at infinity” which can be thought of as an extra point added on to the usual x,y plane representing infinity. This also helps with calculations – though we don’t need to go into this in any more detail here!
Addition of two points A and B
What makes elliptical curves so useful is that we can create a group structure using them. Groups are very important mathematical structures because of their usefulness in being applied to problem solving. A group needs to have certain properties. For example, we need to be able to combine 2 members of the group to create a 3rd member which is also in the group. This is how it is done with elliptical curves:
Take 2 points A and B on y² = x³ -4x + 1. In the example we have A = (2,1) and B = (-2,-1). We now want to find an answer for A + B which also is on the elliptical curve. If we add them as we might vectors we get (0,2) – but unfortunately this is not on the curve. So, we define the addition A + B through the following geometric steps.
We join up the points A and B. This line intersects the curve in one more place, C.
We then reflect the point C in the x axis. We then define this new point C’ = A + B. In this case this means that (2,1) + (-2,-1) = (1/4, -1/8).
Addition of 2 points when A = B
We have to also be able to cope with the situation when the point A and B are the same. Here we create the line through A which is the tangent to the curve at that point:
We then use the same transformation as before to say that A+B = C’. For example with the curve y² = x³ -12x, if we start with the point A(-2,4) then this transformation tells us that A + A = (4,-4).
Elliptical curves over finite fields
For the purposes of cryptography we often work with elliptical curves over finite fields. This means we (say) only consider integer coordinate solutions and work in modulo arithmetic (mod prime).
Say we start with the curve y² = x³ +x+1, and just look at the positive integer solutions mod 7. (Plotted using the site here).
When x = 1,
y² = 1³ +1 + 1
y² = 3
So this has no integer solution.
Next, when x = 2 we have:
y² = 2³ +2 +1 = 11.
However when we are working mod 7 we look at the remainder when 11 is divided by 7 (which is 4). So:
y² = 4 (mod 7)
y = 2 or y = -2 = 5 (mod 7)
When x = 3 we have:
y² = 3³ +3 +1 = 31
y² = 3 (mod 7)
which has no integer solutions.
In fact, all the following coordinate points satisfy the equation (mod 7):
(2,2), (0,1), (0,6), (2,5).
Addition under modulo arithmetic
Let’s look at the coordinate points we calculated before for the elliptical curve y² = x³ +x+1 (integers solutions and mod 7) – they form a group under addition. (Table generated here)
In order to calculate addition of points when dealing with elliptical curves with integer points mod prime we use the same idea as expressed above for general graphs.
The table tells us that (0,1) + (0,1) = (2,5). If we were doing this from the graph we would draw the tangent to the curve at (0,1), find where it intersects the graph again, then reflect this point in the x axis. We can do all this algebraically.
First we find the gradient of the tangent when x = 0:
Next we have to do division modulo 7 (you can use a calculator here, and you can also read more about division modulo p here).
Next we find the equation of the tangent through (0,1):
Next we find where this tangent intersects the curve again (I used Wolfram Alpha to solve this mod 7)
We then substitute the value x = 2 into the original curve to find the y coordinates:
(2,2) is the point where the tangent would touch the curve and (2,5) is the equivalent of the reflection transformation. Therefore our answer is (2,5). i.e (0,1) + (0,1) = (2,5) as required.
When adding points which are not the same we use the same idea – but have to find the gradient of the line joining the 2 points rather than the gradient of the tangent. We can also note that when we try and add points such as (2,5) and (2,2) the line joining these does not intersect the graph again and hence we affix the point an infinity as (2,5) + (2,2).
Using elliptical codes for cryptography
Even though all this might seem very abstract, these methods of calculating points on elliptical curves form the basis of elliptical cryptography. The basic idea is that it takes computers a very long time to make these sorts of calculations – and so they can be used very effectively to encrypt data.
Say for example two people wish to create an encryption key.
They decide on an elliptical curve and modulo. Let’s say they decide on y² = x³ +x+1 for integers, mod 7.
This creates the addition group
Next they choose a point of the curve. Let’s say they choose P(1,1).
Person 1 chooses a secret number n and then sends nP (openly). So say Person 1 chooses n = 2. 2(1,1) = (1,1) + (1,1) = (0,2). Person 1 sends (0,2).
Person 2 chooses a secret number m and then sends mP (openly). So say Person 2 chooses m = 3. 3(1,1) = (1,1) + (1,1) + (1,1) = (0,2) + (1,1) = (0,5). Person 2 sends (0,5).
Both Person 1 and Person 2 can easily calculate mnP (the secret key).
Person 1 receives (0,5) and so does 2(0,5) = (0,5) + (0,5) = (1,1). This is the secret key.
Person 2 receives (0,2) and so does 3(0,2) = (0,2) + (0,2) +(0,2) = (1,1). This is the same secret key.
But for a person who can see mP and nP there is no quick method for working out mnP – with a brute force approach extremely time consuming. Therefore this method can be successfully used to encrypt data.
Prime Spirals – Patterns in Primes
One of the fundamental goals of pure mathematicians is gaining a deeper understanding of the distribution of prime numbers – hence why the Riemann Hypothesis is one of the great unsolved problems in number theory and has a $1 million prize for anyone who can solve it. Prime numbers are the the building blocks of our number system and are essential to our current encryption methods such as RSA encryption. Hence finding patterns in the primes is one of the great mathematical pursuits.
Polar coordinates
The beautiful prime spiral was generated above on Desmos using polar coordinates. We can see a clear spiral pattern – so let’s see how to create this. Polar coordinates (r, θ) need a length (r) from the origin and an angle of anti-clockwise rotation from the origin (θ). So for example in polar coordinates (2,2) means a length of 2 from the origin and a rotation of 2 radians. By considering trigonometry and the unit circle we can say that the polar coordinates (r, θ) are equivalent to the Cartesian coordinate (r.cosθ, r.sinθ).
Plotting prime pairs
So we plot the first few prime pairs:
Polar: (2,2). Cartesian: (2cos2, 2sin2).
Polar: (3,3). Cartesian: (3cos3, 3sin3).
Polar: (5,5). Cartesian: (5cos5, 5sin5).
In Desmos (making sure we are in radians) we input:
We can then change the Desmos graph view to polar (first click on the spanner on the right of the screen). This gives the first 3 points of our spirals. Note I have labeled the points as polar coordinates.
I then downloaded the first 1000 prime numbers from here. I then copied this list of comma separated values and pasted it into an empty part of square brackets M = [ ] in Desmos to create a list.
I can then plot every point in the list as a prime pair by doing the following:
We can then generate our prime spiral for the first 1000 prime pairs:
Just to see how powerful Desmos really is, I then downloaded all the prime numbers less than or equal to 100,000 from here. This time we see the following graph:
We can see that we lose the clear definition of the spiral – though there are still circular spirals with higher densities of primes than others. Also we can see that there are higher densities of the primes on some of the radial lines out from the origin – and other radial lines where no primes appear.
Prime Number Theorem
We can also use our Desmos result to investigate another (more fundamental) result about the distribution of prime numbers. The prime number theorem states:
Here pi(N) is the number of prime numbers less than or equal to N. The little squiggle means that as N gets large pi(N) becomes better and better approximated by the function on the RHS.
For our purple “spiral” above we downloaded all the primes less than or equal to 100,000 – and Desmos tells us that there were 9,592 of them. So let’s see how close the prime number theorem gets us:
We can see that we are off by an error of around 9.46% – not too bad, though still a bit out. As we make N larger we will find that we get a better and better approximation.
Let’s look at what would happen if we took N as 1,000,000,000. From Wikipedia we can see that there are 50,847,534 primes less than or equal to 1,000,000,000. Therefore:
This time we are off by an error of only 5.10%. Have a look at the table of values in Wikipedia to find how large N has to be to be within 1% accuracy.
So this is a nice introduction to looking for patterns in the primes – and a good chance to explore some of the nice graphical capabilities of Desmos. See if you can find any more patterns of your own!
Hailstone Numbers
Hailstone numbers are created by the following rules:
if n is even: divide by 2
if n is odd: times by 3 and add 1
We can then generate a sequence from any starting number. For example, starting with 10:
10, 5, 16, 8, 4, 2, 1, 4, 2, 1…
we can see that this sequence loops into an infinitely repeating 4,2,1 sequence. Trying another number, say 58:
58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1…
and we see the same loop of 4,2,1.
Hailstone numbers are called as such because they fall, reach one (the ground) before bouncing up again. The proper mathematical name for this investigation is the Collatz conjecture. This was made in 1937 by a German mathematian, Lothar Collatz.
One way to investigate this conjecture is to look at the length of time it takes a number to reach the number 1. Some numbers take longer than others. If we could find a number that didn’t reach 1 even in an infinite length of time then the Collatz conjecture would be false.
The following graphic from wikipedia shows how different numbers (x axis) take a different number of iterations (y axis) to reach 1. We can see that some numbers take much longer than others to reach one. Some numbers take over 250 iterations – but every number checked so far does eventually reach 1.
For example, the number 73 has the following pattern:
73, 220, 110, 55, 166, 83, 250, 125, 376, 188, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1…
No proof yet
Investigating what it is about certain numbers that leads to long chains is one possible approach to solving the conjecture. This conjecture has been checked by computers up to a staggering 5.8 x 1018 numbers. That would suggest that the conjecture could be true – but doesn’t prove it is. Despite looking deceptively simple, Paul Erdos – one of the great 20th century mathematicians stated in the 1980s that “mathematics is not yet ready for such problems” – and it has remained unsolved over the past few decades. Maybe you could be the one to crack this problem!
Exploring this problem with Python.
We can plot this with Python – such that we also generate a nice graphical representation of these numbers. The graph above shows what happens to the number 500 when we follow this rule – we “bounce” up to close to 10,000 before falling back into the closed loop after around 100 iterations.
Numbers with large iterations:
871 takes 178 steps to reach 1:
77,031 takes 350 steps to reach 1:
9,780,657,630 takes 1132 steps to reach 1:
If you want to explore this code yourself, the following code has been written to run on repl.it. You can see the code yourself here, and I have also copied it below:
Have a play – and see what nice graphs you can draw!
Chaos and strange Attractors: Henon’s map
Henon’s map was created in the 1970s to explore chaotic systems. The general form is created by the iterative formula:
The classic case is when a = 1.4 and b = 0.3 i.e:
To see how points are generated, let’s choose a point near the origin. If we take (0,0) the next x coordinate is given by:
We would then continue this process over several thousands iterations. If we do this then we get the very strange graph at the top of the page – the points are attracted to a flow like structure, which they then circulate round. The graph above was generated when we took our starting coordinate as (0.1,0.1), let’s take a different starting point. This time let’s have (1.1, 1.1):
We can see that exactly the same structure appears. All coordinates close to the origin will get attracted to this strange attractor – except for a couple of fixed points near the origin which remain where they are. Let’s see why. First we can rewrite the iterative formula just in terms of x:
Next we use the fact that when we have a fixed point the x coordinate (and y coordinate) will not change. Therefore we can define the following:
This allows us to then make the following equation:
Which we can then solve using the quadratic formula:
Which also gives y:
So therefore at these 2 fixed points the coordinates do not get drawn to the strange attractor.
Above we can see the not especially interesting graph of the repeated iterations when starting at this point!
But we can also see the chaotic behavior of this system by choosing a point very close to this fixed point. Let’s choose (0.631354477, 0.631354477) which is correct to 9 decimal places as an approximation for the fixed point.
We can see our familiar graph is back. This is an excellent example of chaotic behavior – a very small change in the initial conditions has created a completely different system.
This idea was suggested by the excellent Doing Maths With Python – which is well worth a read if you are interested in computer programing to solve mathematical problems.
Finding the average distance between 2 points on a hypercube
This is the natural extension from this previous post which looked at the average distance of 2 randomly chosen points in a square – this time let’s explore the average distance in n dimensions. I’m going to investigate what dimensional hypercube is required to have an average distance of more than one, and then also what happens to the average distance as n approaches infinity.
Monte Carlo method
The Monte Carlo method is a very powerful technique which utilizes computational power. Basically we use the fact that the average of a very large number of trials will serve as an approximation to an exact result. In this case I will run a Python program 10 million times – each time it will select 2 coordinate points and then work out the distance between them. It will then find the average of these 10 million trials. The code above generates 2 coordinates in 3 dimensional space inside a unit cube. We can modify this for n-dimensional space by remembering that Pythagoras still works in higher dimensions.
Results
Running this code helps to generate the above results. This answers our first question – we need a 7 dimensional unit hypercube until the average distance between two randomly chosen points is greater than 1. We can also see that the difference between the average distances is reducing – but it’s not clear if this will approach a limit or if it will continue growing to infinity. So let’s do some more trials.
Further trials
This takes us up to a 22-dimensional hypercube. At this point it’s probably useful to plot a graph to see the trend.
Reciprocal model
This reciprocal model is of the form:
We can see that this is a pretty good fit (R squared 0.9994). If this model is accurate then this would suggest that the average distance approaches a limit as n approaches infinity.
Polynomial model
This polynomial model is of the form:
We can see that this is also a very good fit (R squared 0.9997). If this model is accurate then as b is greater than 0, this would suggest that the average distance approaches infinity as n approaches infinity.
Reflection
Quite annoyingly we have 2 model which both fit the data very accurately – but predict completely different results! Logically we could probably say that we would expect the average distance to approach infinity as n approaches infinity – and also we could possibly justify this by the fact that the polynomial model is a slightly better fit. Given the similarity between the 2 models it probably time to find out the actual results for this.
Average n-dimensional distance bounds
Not surprisingly the mathematics required to work this out is exceptionally difficult – and ends up with non-solvable integrals which require analytic solutions. The Monte Carlo method with very large numbers of trials is a reasonably good approach to approximating this answer. There is however a very useful lower and upper bound for the average distance in n dimensional space given by:
This shows immediately that the average distance will approach infinity as n grows large – as the lower bound will grow to infinity. Quite pleasingly we can see that the polynomial model we derived is similar to the lower bound. We can plot both upper and lower bound along with our polynomial model to see how these all compare. We have lower bound (green), polynomial model (black) and upper bound (green):
We can see that our polynomial model very closely follows the upper bound in our domain. As we extend the domain this polynomial approximation remains above the lower and tracks the upper bounds before gradually growing less accurate. When n is 50 our model predicts a distance of 2.94, whereas the upper bound is 2.88. This is quite a nice result – we have used the Monte Carlo method to derive a polynomial approximation to the average distance in n-dimensional hypercubes and it both closely follows the upper bound over a reasonable domain and also is of a very similar form to the lower bound. We can use this lower bound to see that a 36 dimensional hypercube (and higher) would be guaranteed to have an average distance of more than 2.
Conclusion
This was a nice example of the power of the Monte Carlo method in these kind of problems – we were able to use it quite successfully to get a polynomial approximation which turned out to be reasonably accurate. We could have significantly improved this accuracy by running 100 million (or 1 billion etc) trials each time – though this would have probably required a more powerful computer!
Essential resources for IB students:
Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams. I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.
There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!
The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers. These all have worked solutions and allow you to focus on specific topics or start general revision. This also has some excellent challenging questions for those students aiming for 6s and 7s.
Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.
2) Exploration Guides and Paper 3 Resources
I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.
Generating e through probability and hypercubes
This is a really beautiful solution to an interesting probability problem posed by fellow IB teacher Daniel Hwang, for which I’ve outlined a method for solving suggested by Ferenc Beleznay. The problem is as follows:
On average, how many random real numbers from 0 to 1 (inclusive) are required for the sum to exceed 1?
1 number
Clearly if we choose only 1 number then we can’t exceed 1.
2 numbers
Here we imagine the 2 numbers we pick as x and y and therefore we can represent them as a coordinate pair. The smallest pair (0,0) and the largest pair (1,1). This means that the possible coordinates fit inside the unit square shown above. We want to know for what coordinate pairs we have the inequality x + y > 1. This can be rearrange to give y > 1-x. The line y = 1-x is plotted and we can see that any coordinate points in the triangle BCD satisfy this inequality. Therefore the probability of a random coordinate pair being in this triangle is 1/2.
3 numbers
This time we want to find the probability that we exceed 1 with our third number. We can consider the numbers as x, y, z and therefore as 3D coordinates (x,y,z). From the fact that we are choosing a third number we must already have x +y <1. We draw the line x+y = 1, which in 3D gives us a plane. The volume in which our coordinate point must lie is the prism ABDEFG.
We now also add the constraint x+y+z >1. This creates the plane as shown. If our coordinate lies inside the pyramid ABDE then our coordinates will add to less than 1, outside this they will add to more than 1.
The volume of the pyramid ABDE = 1/3 (base area)(perpendicular height).
The volume of the prism ABDEFG = (base area)(perpendicular height).
Given that they share the same perpendicular height and base area then precisely 1/3 of the available volume would give a coordinate point that adds to less than 1, and 2/3 of the available volume would give a coordinate point that adds to more than 1.
Therefore we have the following tree diagram:
Exceeds 1 with 2 numbers = 1/2
Does not exceed 1 with 2 numbers, exceeds 1 with 3 numbers = 1/2 x 2/3 = 1/3.
Does not exceed 1 with 2 numbers, does not exceed 1 with 3 numbers = 1/2 x 1/3 = 1/6.
4 numbers
If you been following so far this is where things get interesting! We can now imagine a 4 dimensional unit cube (image above from Wikipedia) and a 4D coordinate point (x,y,z,a).
Luckily all we care about is the ratio of the 4-D pyramid and the 4-D prim formed by our constraints x+y+z <1 and x+y+z+a >1.
We have the following formula to help:
The n-D volume of a n-D pyramid = 1/n (base)(perpendicular height).
Therefore:
The 4-D volume of a 4-D pyramid = 1/4 (base 3D volume)(perpendicular height).
The 4-D volume of the prism ABDEFG = (base 3D volume)(perpendicular height).
Given that the 2 shapes share the same base and perpendicular height, the hyper-pyramid occupies exactly 1/4 of the 4-D space of the hyper-prism. So the probability of being in this space is 1/4 and 3/4 of being outside this space.
We can now extend our tree diagram:
Does not exceed 1 with 2 numbers, does not exceed 1 with 3 numbers, exceeds with 4 numbers = 1/2 x 1/3 x 3/4 = 1/8
Does not exceed 1 with 2 numbers, does not exceed 1 with 3 numbers, does not exceed with 4 numbers = 1/2 x 1/3 x 1/4 = 1/24.
In general a hyper-pyramid in n dimensional space occupies exactly 1/n of the space of the hyper-prism – so we can now continue this tree diagram.
Expected value
We can make a table of probabilities to find how many numbers we expect to use in order to exceed one.
Which gives us the following expected value calculation:
Which we can rewrite as:
But we have:
Therefore this gives:
So on average we would need to pick e numbers for the sum to exceed one! This is quite a remarkable result – e, one of the fundamental mathematical constants has appeared as if by magic on a probability question utilizing hyper-dimensional shapes.
Demonstrating this with Python
Running the Python code shown above will simulate doing this experiment. The computer generates a “random” number, then another and carries on until the sum is greater than 1. It then records how many numbers were required. It then does this again 1 million times and finds the average from all the trials.
1 million simulations gives 2.7177797177797176. When we compare this with the real answer for e, 2.7182818284590452353602874713527, we can see it has taken 1 million simulations to only be correct to 4sf.
Even 5 million simulations only gives 2.7182589436517888, so whilst we can clearly see that we will eventually get e, it’s converging very slowly. This may be because we are reliant on a random number generator which is not truly random (and only chooses numbers to a maximum number of decimal places rather than choosing from all values between 0 and 1).
I think this is a beautiful example of the unexpected nature of mathematics – we started out with a probability problem and ended up with e, via a detour into higher dimensional space! We can also see the power of computers in doing these kinds of brute force calculations.
Essential resources for IB students:
Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams. I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.
There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!
The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers. These all have worked solutions and allow you to focus on specific topics or start general revision. This also has some excellent challenging questions for those students aiming for 6s and 7s.
Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.
2) Exploration Guides and Paper 3 Resources
I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.
Have you got a Super Brain?
Adapting and exploring maths challenge problems is an excellent way of finding ideas for IB maths explorations and extended essays. This problem is taken from the book: The first 25 years of the Superbrain challenges. I’m going to see how many different ways I can solve it.
The problem is to find all the integer solutions to the equation above. Finding only integer solutions is a fundamental part of number theory – a branch of mathematics that only deals with integers.
Method number 1: Brute force
This is a problem that computers can make short work of. Above I wrote a very simple Python program which checked all values of x and y between -99 and 99. This returned the only solution pairs as:
Clearly we have not proved these are the only solutions – but even by modifying the code to check more numbers, no more pairs were found.
Method number 2: Solving a linear equation
We can notice that the equation is linear in terms of y, and so rearrange to make y the subject.
We can then use either polynomial long division or the method of partial fractions to rewrite this. I’ll use partial fractions. The general form for this fraction can be written as follows:
Next I multiply by the denominator and the compare coefficients of terms.
This therefore gives:
I can now see that there will only be an integer solution for y when the denominator of the fraction is a factor of 6. This then gives (ignoring non integer solutions):
I can then substitute these back to find my y values, which give me the same 4 coordinate pairs as before:
Method number 3: Solving a quadratic equation
I start by making a quadratic in x:
I can then use the quadratic formula to find solutions:
Which I can simplify to give:
Next I can note that x will only be an integer solution if the expression inside the square root is a square number. Therefore I have:
Next I can solve a new quadratic as follows:
As before I notice that the expression inside my square root must be a square number. Now I can see that I need to find m and n such that I have 2 square numbers with a difference of 24. I can look at the first 13 square numbers to see that from the 12th and 13th square numbers onwards there will also be a difference of more than 24. Checking this list I can find that m = 1 and m = 5 will satisfy this equation.
This then gives:
which when I solve for integer solutions and then sub back into find x gives the same four solutions:
Method number 4: Graphical understanding
Without rearranging I could imagine this as a 3D problem by plotting the 2 equations:
This gives the following graph:
We can see that the plane intersects the curve in infinite places. I’ve marked A, B on the graph to illustrate 2 of the coordinate pairs which we have found. This is a nice visualization but doesn’t help find our coordinates, so lets switch to 2D.
In 2D we can use our rearranged equation:
This gives the following graph:
Here I have marked on the solution pairs that we found. The oblique asymptote (red) is y = 2x-1 because as x gets large the fraction gets very small and so the graph gets closer and closer to y = 2x -1.
All points on this curve are solutions to the equation – but we can see that the only integer solution pairs will be when x is small. When x is a large integer then the curve will be close to the asymptote and hence will return a number slightly bigger than an integer.
So, using this approach we would check all possible integer solutions when x is small, and again should be able to arrive at our coordinate pairs.
So, 4 different approaches that would be able to solve this problem. Can you find any others?
Essential resources for IB students:
Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams. I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.
There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!
The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers. These all have worked solutions and allow you to focus on specific topics or start general revision. This also has some excellent challenging questions for those students aiming for 6s and 7s.
Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.
2) Exploration Guides and Paper 3 Resources
I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.
Sierpinski Triangle: A picture of infinity
This pattern of a Sierpinski triangle pictured above was generated by a simple iterative program. I made it by modifying the code previously used to plot the Barnsley Fern. You can run the code I used on repl.it. What we are seeing is the result of 30,000 iterations of a simple algorithm. The algorithm is as follows:
Transformation 1:
xi+1 = 0.5xi
yi+1= 0.5yi
Transformation 2:
xi+1 = 0.5xi + 0.5
yi+1= 0.5yi+0.5
Transformation 3:
xi+1 = 0.5xi +1
yi+1= 0.5yi
So, I start with (0,0) and then use a random number generator to decide which transformation to use. I can run a generator from 1-3 and assign 1 for transformation 1, 2 for transformation 2, and 3 for transformation 3. Say I generate the number 2 – therefore I will apply transformation 2.
xi+1 = 0.5(0) + 0.5
yi+1= 0.5(0)+0.5
and my new coordinate is (0.5,0.5). I mark this on my graph.
I then repeat this process – say this time I generate the number 3. This tells me to do transformation 3. So:
xi+1 = 0.5(0.5) +1
yi+1= 0.5(0.5)
and my new coordinate is (1.25, 0.25). I mark this on my graph and carry on again. The graph above was generated with 30,000 iterations.
Altering the algorithm
We can alter the algorithm so that we replace all the 0.5 coefficients of x and y with another number, a.
a = 0.3 has disconnected triangles:
When a = 0.7 we still have a triangle:
By a = 0.9 the triangle is starting to degenerate
By a = 0.99 we start to see the emergence of a line “tail”
By a = 0.999 we see the line dominate.
And when a = 1 we then get a straight line:
When a is greater than 1 the coordinates quickly become extremely large and so the scale required to plot points means the disconnected points are not visible.
If I alternatively alter transformations 2 and 3 so that I add b for transformation 2 and 2b for transformation 3 (rather than 0.5 and 1 respectively) then we can see we simply change the scale of the triangle.
When b = 10 we can see the triangle width is now 40 (we changed b from 0.5 to 10 and so made the triangle 20 times bigger in length):
Fractal mathematics
This triangle is an example of a self-similar pattern – i.e one which will look the same at different scales. You could zoom into a detailed picture and see the same patterns repeating. Amazingly fractal patterns don’t fit into our usual understanding of 1 dimensional, 2 dimensional, 3 dimensional space. Fractals can instead be thought of as having fractional dimensions.
The Hausdorff dimension is a measure of the “roughness” or “crinkley-ness” of a fractal. It’s given by the formula:
D = log(N)/log(S)
For the Sierpinski triangle, doubling the size (i.e S = 2), creates 3 copies of itself (i.e N =3)
This gives:
D = log(3)/log(2)
Which gives a fractal dimension of about 1.59. This means it has a higher dimension than a line, but a lower dimension than a 2 dimensional shape.
Essential resources for IB students:
Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams. I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.
There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!
The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers. These all have worked solutions and allow you to focus on specific topics or start general revision. This also has some excellent challenging questions for those students aiming for 6s and 7s.
Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.
2) Exploration Guides and Paper 3 Resources
I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.
Sphere packing problem: Pyramid design
Sphere packing problems are a maths problems which have been considered over many centuries – they concern the optimal way of packing spheres so that the wasted space is minimised. You can achieve an average packing density of around 74% when you stack many spheres together, but today I want to explore the packing density of 4 spheres (pictured above) enclosed in a pyramid.
Considering 2 dimensions
First I’m going to consider the 2D cross section of the base 3 spheres. Each sphere will have a radius of 1. I will choose A so that it is at the origin. Using some basic Pythagoras this will give the following coordinates:
Finding the centre
Next I will stack my single sphere on top of these 3, with the centre of this sphere directly in the middle. Therefore I need to find the coordinate of D. I can use the fact that ABC is an equilateral triangle and so:
3D coordinates
Next I can convert my 2D coordinates into 3D coordinates. I define the centre of the 3 base circles to have 0 height, therefore I can add z coordinates of 0. E will be the coordinate point with the same x and y coordinates as D, but with a height, a, which I don’t yet know:
In order to find a I do a quick sketch, seen below:
Here I can see that I can find the length AD using trig, and then the height DE (which is my a value) using Pythagoras:
Drawing spheres
The general equation for spheres with centre coordinate (a,b,c) and radius 1 is:
Therefore the equation of my spheres are:
Plotting these on Geogebra gives:
Drawing a pyramid
Next I want to try to draw a pyramid such that it encloses the spheres. This is quite difficult to do algebraically – so I’ll use some technology and a bit of trial and error.
First I look at creating a base for my pyramid. I’ll try and construct an equilateral triangle which is a tangent to the spheres:
This gives me an equilateral triangle with lengths 5.54. I can then find the coordinate points of F,G,H and plot them in 3D. I’ll choose point E so that it remains in the middle of the shape, and also has a height of 5.54 from the base. This gives the following:
As we can see, this pyramid does not enclose the spheres fully. So, let’s try again, this time making the base a little bit larger than the 3 spheres:
This gives me an equilateral triangle with lengths 6.6. Taking the height of the pyramid to also be 6.6 gives the following shape:
This time we can see that it fully encloses the spheres. So, let’s find the density of this packing. We have:
Therefore this gives:
and we also have:
Therefore the density of our packaging is:
Given our diagram this looks about right – we are only filling less than half of the available volume with our spheres.
Comparison with real data
[Source: Minimizing the object dimensions in circle and sphere packing problems]
We can see that this task has been attempted before using computational power – the table above shows the average density for a variety of 2D and 3D shapes. The pyramid here was found to have a density of 46% – so our result of 44% looks pretty close to what we should be able to achieve. We could tweak our measurements to see if we could improve this density.
So, a nice mixture of geometry, graphical software, and trial and error gives us a nice result. You could explore the densities for other 2D and 3D shapes and see how close you get to the results in the table.
Essential resources for IB students:
Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams. I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.
There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!
The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers. These all have worked solutions and allow you to focus on specific topics or start general revision. This also has some excellent challenging questions for those students aiming for 6s and 7s.
Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.
2) Exploration Guides and Paper 3 Resources
I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.
Square Triangular Numbers
Square triangular numbers are numbers which are both square numbers and also triangular numbers – i.e they can be arranged in a square or a triangle. The picture above (source: wikipedia) shows that 36 is both a square number and also a triangular number. The question is how many other square triangular numbers we can find?
The equation we are trying to solve is:
a2 = 0.5(b2+b)
for some a, b as positive integers. The LHS is the formula to generate square numbers and the RHS is the formula to generate the triangular numbers.
We can start with some simple Python code (which you can run here):
for c in range(1,10001):
for d in range(1,10001):
if c**2 == (d**2+d)/2:
print(c**2, c,d)
This checks the first 10000 square numbers and the first 10000 triangular numbers and returns the following:
1 1 1
36 6 8
1225 35 49
41616 204 288
1413721 1189 1681
48024900 6930 9800
i.e 1225 is the next square triangular number after 36, and can be formed as 352 or as 0.5(492+49). We can see that there are very few square triangular numbers to be found in the first 50 million numbers. The largest we found was 48,024,900 which is made by 69302 or as 0.5(98002+9800).
We can notice that the ratio between each consecutive pair of square triangular numbers looks like it converges as it gives:
36/1 = 36
1225/36 = 34.027778
41616/1225 = 33.972245
1413721/41616 = 33.970612
48024900/1413721 = 33.970564
So, let’s use this to predict that the next square triangular number will be around
48024900 x 33.9706 = 1,631,434,668.
If we square root this answer we get approximately 40391
If we solve 0.5(b2+b) = 1,631,434,668 using Wolfram we get approximately 57120.
Therefore let’s amend our code to look in this region:
for c in range(40380,40400):
for d in range(57100,57130):
if c**2 == (d**2+d)/2:
print(c**2, c,d)
This very quickly finds the next solution as:
1631432881 40391 57121
This is indeed 403912 – so our approximation was very accurate. We can see that this also gives a ratio of 1631432881/48024900 = 33.97056279 which we can then use to predict that the next term will be 33.970563 x 1631432881 = 55,420,693,460. Square rooting this gives a prediction that we will use the 235,416 square number. 235,4162 gives 55,420,693,056 (using Wolfram Alpha) and this is indeed the next square triangular number.
So, using a mixture of computer code and some pattern exploration we have found a method for finding the next square triangular numbers. Clearly we will quickly get some very large numbers – but as long as we have the computational power, this method should continue to work.
Using number theory
The ever industrious Euler actually found a formula for square triangular numbers in 1778 – a very long time before computers and calculators, so let’s have a look at his method:
We start with the initial problem, and our initial goal is to rearrange it into the following form:
Next we make a substitution:
Here, when we get to the equation 1 = x2 – 2y2 we have arrived at a Pell Equation (hence the rearrangement to get to this point). This particular Pell Equation has the solution quoted above where we can define Pk as
Therefore we have
Therefore for any given k we can find the kth square triangular number. The a value will give us the square number required and the b value will give us the triangular number required. For example with k = 3:
This tells us the 3rd square triangular number is the 35th square number or the 49th triangular number. Both these give us an answer of 1225 – which checking back from our table is the correct answer.
So, we have arrived at 2 possible methods for finding the square triangular numbers – one using modern computational power, and one using the skills of 18th century number theory.
Essential resources for IB students:
Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams. I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.
There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!
The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers. These all have worked solutions and allow you to focus on specific topics or start general revision. This also has some excellent challenging questions for those students aiming for 6s and 7s.
Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.
2) Exploration Guides and Paper 3 Resources
I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.
