!!Con West 2020 - Aaron Wood: The Ancient Greeks and Their Restless Cattle: 2300 years of Bigints!

I thought I would talk about the joy, surprise, and excitement of soap operas. Okay. So previously, on The Ancient and the Restless, Nicky tries to share a tender moment with Archimedes, but he breaks the social rules, and “well actually”s her about the finite versus the infinite. And then computes the upper bound on the number of grains of sand that would fit in the universe. And what’s interesting about this is that they had… The Greek numeral system had a myriad, which was 10^4, and they could go up to a myriad myriad, and that’s kind of as high as it would go. 8-digit architecture. I mean, 10^63 is well beyond that. So he had to invent big numerals.

And he published his results in a paper he called the Sand Reckoner. And that was really good. Then his rival across town, Catherine, was like… Hey, I’ve got a big numeral system of my own! And she has some plans for her big numeral system. And he doesn’t want to cede his big numeral fame. So he challenges her to count the number of cattle. There’s four colors of cattle, and it’s divided into bulls and cows, and he gives a bunch of proportions for the bulls.

Like white bulls are a half and a third of the 02:09 - black together with the yellow, et cetera. And then gives some proportions for the cows. You know, same sort of thing. White were a third and a fourth of the whole of the black. And so on and so on. And so Catherine gets to work, infinitely many solutions, because we’ve got 1 free parameter, she does some stuff, and does some more stuff, and she’s like… Hey, the smallest number of cattle under the sun is 50 million, and you could take any multiple of this number and it would also work. And Archimedes is impressed. But not that impressed. And tells her that… So he ups the ante and he’s like – hey, with the white and black bulls together, they form a square! And when the yellow and dappled bulls are together, they form a triangle! So… And Catherine is like… Yeah, no big deal. How hard can it be? He’s like… If you can do this, then I’ll really be impressed. So Catherine knows about square numbers. She works some stuff out.

She does some factoring, 03:20 - she gets a result about what K should be. She knows about triangular numbers. She does a few more things with the square number stuff. And she ends up figuring out… Hey! All I need to do is find an integer solution to this equation. Where Y is divisible by 4657. And that’s where she stops. Not really possible. So Archimedes is very pleased with himself. And the problem kind of goes away. So fast-forward about 2,000 years, to French mathematician Lagrange. These equations are now known as Pell equations. X squared minus dY squared, where d is some positive integer, and Lagrange proved they had infinitely many solutions.

04:21 - Actually, much earlier than that, the Indians figured out how to do this, in 628, Brahmagupta figured out if you have one solution, you have infinitely many, and Bhaskara II had a method for producing that first solution. But the Europeans didn’t know about the Indians’ work, so they did it totally separately. From Wallace, Lord Branchner, and Lagrange came around and used continuous fractions. So you might be wondering… Why are they called Pell’s equations? And it was just a mistake. (laughter) But when things get named, they just stay.

So what’s a continued fraction? Continued 05:07 - fraction, you start with a number bigger than one, you subtract the integer part, then you invert it, so it’s bigger than one again, and you rinse and repeat. So for square root 33, it might look like this. And a good fact about square roots is that there’s a periodicity. You see that this bottom right one has the same result as the top right one. So this will just repeat indefinitely. 5 and then the 12110 will just keep going. These integer parts are sometimes called the quotients, and you can use the quotients to build rational approximations to the square root.

So you take 51, 512, 5121 and build these approximations. They get closer and closer to the square root as you go. And really fascinating – at the last one, the convergent gives a solution to Pell’s equation. So, ²³⁄₄ sounds to 23, 4 being a solution to x^2-33y^2=1 Then you take powers of that thing. And that gives you all the solutions. So once you find the first solution, you can just keep taking powers of this quadratic integer and now you get all the solutions.

Fast- forward another 100 06:27 - years, and Amthor finds out about Archimedes’ cattle problem, does all the same work, says hey, it’s just a Pell equation. We know how to do that stuff now. I’ll just use continued fractions. Has a period of 92. So the last convergent in that list has this. As the solution. But we need a y that’s divisible by 4657, so we need to take the 2329th power of this thing, which as you can guess is not computable by a human. But anyways… She has this is the smallest solution. There are 206,000 digits, and the first four of them are 7766. So we fast-forward to 1965 and University of Waterloo, they’ve got this cool IBM 7040 with 32k of memory and decide to compute this thing. I know that’s not as impressive as 434-bit modular arithmetic on a Commodore 64. (laughter) But they do this. It takes 7 hours and 49 minutes to compute.

They published the first 07:53 - and last 50-digit numbers. There was a group also in 1889, that spent four years computing digits. Computed 30 digits of the front and 18 digits of the back. That was a good project. (laughter) Anyway, you might notice that the first four digits are 7760. So Amthor is mortified that… Luckily she didn’t try to compute more than 4 digits. That would have been rough. Then in 1981, they had this new Cray 1 computer and they’re like… Hey, we’ve got a new computer. Let’s make sure things are set up right by just solving Archimedes’ cattle problem. Sure. So they compute the digits in about… And do all the verification. It takes about 10 digits. And then this Harry Nilson guy is like… It’s never been published before. Might as well just publish what the solution looks like. On 47 pages. Where the digits are like ¹⁄₃ of actual size. So I thought we would maybe compute it right now. And I was really interested in doing it quickly. So I wrote my code in Ruby. (laughter) So… Uh-oh.

Don’t look, don’t look! Close your eyes, close your eyes. Okay. That was close. I’m glad no one looked. Thanks. Yeah. So we got some continued fraction stuff. Not all that hard. You know. Pretty straightforward. And we had to take powers of quadratic integers, which is also not all that difficult to do. So hard code in the solution to part 1. Because I was too lazy to do that part. So yeah. The first solution we just need to compute the continued fraction convergent. And then we’ve got to take the 2329th power of that thing and multiply by those other values, and that’s it. So we can print this thing off. Whoops. That’s not what I meant to do. Whoops. So… Yeah. 0.01 seconds in Ruby. On this wimpy laptop. Probably we should… I got like… A minute left or something. So… >> 7760271486818269583866643… (laughter) >> Thanks! (applause) .