So, I was watching an interview with Terence Tao which mentioned his famous Problem Six from the 1988 International Math Olympiad, which he only managed to get one point out of seven for. In the competition, the final problem he had to solve was:
Let a and b be positive integers such that ab + 1 divides a2 + b2. Show that a2 + b2 / ab + 1 is the square of an integer.
At first I thought this just meant you had to find a single solution at which it is true that:
(a2 + b2) mod (ab + 1) ≅ 0
AND
sqrt((a2 + b2) / (ab + 1)) = [some integer]
Which is actually a really easy problem. If you do the obvious thing when testing number-by-number, you get it immediately. If a = 1 and b = 1, then (12 + 12)/(1*1 + 1) = 2/2 = 1, and the root of 1 is of course 1.
But, like, this looked way too easy, so I wanted to know if there were other instances of this forming a perfect square. Then I found that a = 2 and b = 8 does it. Noticing a potential pattern, I checked a = 3 and b = 27. Sure enough, another solution.
At this point, I didn’t want to keep checking these by hand, so I tried the first 25 iterations of b = a3 using a Python script.
a = 1
while(a <= 25):
b = a**3
if((a**2 + b**2)%(a*b + 1) == 0):
x = (a**2 + b**2)/(a*b + 1)
print("A =", a)
print("B =", b)
print("The result,", x, "is a square of", x**0.5)
a +=1
Upon running it, I found that for all instances of b = a3, the result of the equation is a perfect square. Specifically, the result is a perfect square of a. That was the cool part. (I already suspected this after trying a = 2 and a = 3, but double checking with a computer was trivial enough.)
So then I tried to figure out why that was the case. Firstly, if a3 = b, and a and b are both squared in the numerator, then the numerator is effectively a2 + a6. Next, if the denominator is a*(a3) + 1, then it’s a4 + 1. Finally, the result of the equation is a2. Therefore:
Thus, it is proven that for any positive integers b and a such that b = a3, ab + 1 divides a2 + b2 and a2 + b2 / ab + 1 is the square of an integer.
...Except, that wasn’t what I needed to prove. I needed to prove that for any Z+ a and b such that ab + 1 divides a2 + b2, a2 + b2 / ab + 1 is a perfect square.
Aaaaand I don’t yet know how to do that. But I’m working on it! So far, I know that not all instances of “ab + 1 divides a2 + b2″ are instances of b = a3, because a = 8 and b = 30 also does it, with a result of 4, which is the square of 2. Meanwhile, a isn’t even a factor of b here: 8 = 2*2*2, while 30 = 2*3*5.
I’m not sure what I’ll need to do to prove the general case, but I’ll work on it some more when I get back from dinner this evening. In the meantime, if anyone has hints/suggestions for how I can tackle this or things I should test, please let me know! Just please don’t write a proof in the notes unless you write it in words and rot13 it.
OK, so, yesterday I said I was investigating Problem 6 of the 1988 International Math Olympiad. The problem as stated is:
Let a and b be positive integers such that ab + 1 divides a2 + b2. Show that a2 + b2 / ab + 1 is the square of an integer.
I interpreted this to mean:
For any positive integers a and b such that ab + 1 divides a2 + b2, show that a2 + b2 / ab + 1 must be a perfect square.
In the process of investigating it, I would up proving that for any positive integers b and a such that b = a3, ab + 1 divides a2 + b2and a2 + b2 / ab + 1 is the square of an integer. This is related, but not quite what I’m looking for. My specific reasoning was:
Firstly, if a3 = b, and a and b are both squared in the numerator, then the numerator is effectively a2 + a6. Next, if the denominator is a*(a3) + 1, then it’s a4 + 1. Finally, the result of the equation is a2. Therefore:
However, b = a3 isn’t the only time ab + 1 divides a2 + b2, nor the only time the result is a perfect square. For example, I noticed yesterday that a = 8 and b = 30 does it.
Anyway, that’s what happened yesterday, so now you’re all caught up. Now, the thing that nerdsniped me for the past two hours: What is the pattern of these “irregular” solutions, such as a=8 & b=30?
I fired up my compiler and wrote a script to search for pairs of numbers like this, and I discovered a pattern. The equation is solved when a=8 & b=30, or when a=30 & b=112, or when a=112 & b=418...
That is, there’s a cycle. The b of one solution is the a of the next, with some larger number being b next time. This goes on for as far up as I checked*, which means there’s a long (I expect infinite) sequence of integers where you can plug in any adjacent pair and find a solution.
However, this wasn’t the only sequence like this. In fact, after I stopped thinking of these as “the irregular solutions”, I realised there must be a bunch of sequences like this. Let me explain:
The sequence I just discussed ({8, 30, 112, 418...}) doesn’t start at 8. It starts at 2. Because, as you might recall, a=2 & b=8 is a solution. So we have a sequence {2, 8, 30, 112, 418...}.
(The pairs you can form have interesting properties - the first has a ratio of 4 (ie: 8/2 =4), while every subsequent pair has a slightly smaller ratio [3.75, 3.73333 (recurring), 3.7321 (truncated), 3.7320 (truncated)]. Because the difference between adjacent ratios becomes smaller as well, I assume this converges on some limit. However, at present, I’m not sure how I’d find it.)
However, if you’re like me, when you saw that 2 & 8 was the start of a sequence, you thought “Hold on, does that mean 3 & 27 is also the start of a sequence?” If so, you would be right! There’s a whole ‘nother “irregular” sequence {3, 27, 240, 2133, 18957...}. This also consists of pair-wise solutions, and the ratios also start at a perfect square (32) and then decline toward some (supposed) lower bound.
Unsurprisingly, there’s a sequence like this for every “regular” pair I checked (ie: pairs where b = a3), and I assume there’s one for all integer values of a. (Unproven, but conjectured strongly enough that I’d be pretty surprised if I were wrong.)
The result of the equation when given inputs from any of the sequences ends up being a square, of course. Specifically, a square of the first number in the sequence. So, for the first sequence I talked about, the equation always outputs 4. For this reason, I consider the first element of the sequence to be the defining element, so I’ve been calling each sequence Sfirst element. So, the first sequence discussed would be S2. (I expect there is a sequence S1, but that it simply contains {1, 1, 1, 1, 1, 1, 1...}).
The prime factorisations of the numbers in each sequence haven’t told me much useful stuff yet. So far, I can’t see a pattern that would let me predict** the next number in the sequence using its factorisation. Only two result really jump out at me:
The first thing is that every number in a given sequence has the first number of that sequence as a factor. This was intuitive to me so it wasn’t very interesting. What was interesting is that the third, sixth, ninth and so on elements of every single sequence tested are all divisible by 10. I have no idea why this keeps happening, but it does, and that’s cool enough that it might merit more research.
However, if anyone reading this discovers anything more interesting in the factorisations, please let me know.
Anyway, this has almost certainly all been a massive sidetrack from actually solving the problem. But, hey, I started working on the problem because it was interesting, and this sidetrack was interesting, so I don’t consider this lost in any way.
*I checked for the existence of all the sequences S2...S10, and several members of each set, and the factorisations of some members, and the ratios of some pairs. All those fiddly numbers and my obscure hypotheses are under the cut for anyone who thought this post wasn’t already long enough, or wants to use my results to investigate further.
**Edit: Shit, I only realised after writing this that I should just look these sequences up in the G-d damn OEIS. Sure enough, every sequence I’ve checked is already there, and has an equation for it. Here’s S2. I’m really kicking myself now. It’s a bit late to go diving into them, but I’ll let you guys know what I uncover.
Hi, extremely strange people who want to read even more math. Here is some more stuff from my exploration:
Firstly, here are my guesses about what might be going on here. Each conjecture has varying amounts of confidence, based on how intuitively correct the pattern seems to me and how confident I am that I understand the relevant math.
Conjectures with >95% confidence:
There are no natural numbers a such that b = a3does not yield a solution.
:. The set So is countably infinite.
:. There is a countably infinite number of sets S1...Sn.
All members of the set Sn will have n as a factor.
Conjectures with >70% confidence:
Each set S1...Sn is countably infinite
The set of all the sets S1..n (hence forth Sab) is countably infinite (for the same reason the rationals are countable)
Every third element (the third, the sixth, the ninth, etc) of any sequence S2...Sn will be divisible by 10
The limit for the ratios for a given sequence will be greater than n2-1, for any sequence Sn.
Conjectures with >50% confidence:
There are no solutions to the equation which are not in the super set Sab (bearing in mind that So is a subset of Sab., since the listing the first two elements of each set S1...Sn gives you the first 2n terms of So.)
For each set Sn, every prime is a factor of some element of that set. (Strictly conditional on all sets S1...Sn being infinite.)
If you can prove, disprove, or otherwise contribute to me thinking about any of these conjectures, you will win the prize of me expressing my gratitude by sending emoji to your inbox. That’s basically as valuable as a Field’s Medal, right? 💡💯💡
Next up, my method of investigation thus far:
The first thing I did was iteratively test loooooots of possible {a, b} pairs. Like, so many. Literally a million. Here’s the code that did that:
a = 5000
while((a > 0)):
b = 200
while((b > 0)):
if((a**2 + b**2)%(a*b + 1) == 0):
x = (a**2 + b**2)/(a*b + 1)
print("A =", a)
print("B =", b)
print("Numerator =", (a**2 + b**2))
print("Denominator =", (a*b + 1))
print("The result,",x, "is a square of", x**0.5)
print(" ")
b -=1
a -=1
This worked down from very high numbers to very low ones, testing lots of possibilities. The list generated included the original sequence of “regular” pairs (So, which contains {{1, 1}, {2, 8}, {3, 27}, {4, 64}...}. Unlike the Sn sequences, only the pairs shown as subsets are valid solutions.), where b = a3, up to {17, 4913}.
Additionally, it generated the first few terms of S2 and S3, as well as the first term of each of S4, and S5. This is the point at which it was 100% clear to me that there was a sequence of sequences S2..n. (I then assumed a sequence S1 which is as described before the cut.)
In testing the numbers in each sequence, I found that the ratios of the pairs declined as I described before the cut. The ratios for the first couple elements of S2 are:
As you can see, it appears to converge. I’m not sure how I’d figure out what the limit is, but I’m pretty confident it’s >3.7. Furthermore, you can see that each ratio is lower than the one before it, which means I could discount the possibility of a pair such that their ratio would be larger than the ratio of the pair before it. This allowed me to greatly restrict the search space when checking for each “family” of numbers (ie: numbers in the same sequence).
My method for searching within each “family” was to take its initial member ‘a’ (eg: In S2 that would be ‘2′) and then test whether a*a2 was a solution. Given that it was, I would enter it into my array, assign b to be that number, and then take the ratio of b/a to be the largest possible ratio of a pair of solutions.
Then I would use the number I’d just discovered as my new ‘a’, multiply it by the ratio I’d found last time, and then check if that number was a solution. If not, I’d decrement it by one over and over again until I found a solution, and then I’d save that and repeat the cycle, with the ratio becoming smaller each time.
This algorithm, converted to Python, was:
stopper = 1
ceiling = 25
family = [5]
for a in family:
b = int(a*ceiling)
while(b > a):
if((a**2 + b**2)%(a*b + 1) == 0):
x = (a**2 + b**2)/(a*b + 1)
ceiling = b/a
family.append(b)
stopper +=1
print("The ratio is", ceiling)
break
b -=1
if(stopper > 9):
break
print(family)
#This will print the first 10 elements of S5. If you want a different sequence Sn, then replace the ‘5′ in family’s array with n and the 25 for ceiling with n**2
Once the difference between the ratios of pairs became small enough, b ended up being pretty much the same as a*ceiling rounded down to the nearest integer.
OK, if you’re still reading this, now is when I paste all the numbers I found in case you want the values. First, I’ll list the first elements of the the sets I found, with the ratio of the last two elements in each list. I’ll give the first ten for S2 to S4, and the first 5 for the others up to S10. Underneath that, I’ll give you some prime factorisations, in case you’re into those.
Colson Corp. had $700,000 net income in 2015. On January 1, 2015 there were 200,000 shares of common stock outstanding. On April 1, 20,000 shares were issued and on September 1, Colson bought 30,000 shares of treasury stock. There are 30,000 options to buy common stock at $40 a share outstanding. The market price of the common stock averaged $50…
