(Brady: What's today's video about? What you got here Matt?)
- So this is the handwritten results from a mathematician who lived in the mid to late 1800s,
a gentleman called William Shanks, who I think in the modern day we would call a
recreational mathematician. He had a real job, ran a boarding school;
in his spare time he just did calculation after calculation. William sent all of his
incredible results in to the Royal Society - here we go - so this is W. Shanks' Reciprocals of Prime
Numbers. And then what follows is- and these are the sections and when he did him so you can see.
He's got them in batches of ten to five thousand at a time, and this is across years,
this was not a fast process. And then here's what he found, and he's described it here.
In the left-hand columns of this table are primes, these are the prime numbers down here,
in the right-hand columns is the number of figures in the period of the reciprocal of each prime. So
what he's done is he's taken each prime number, he's computed 1 over that prime number, and then
worked out how many digits before it repeats. So the first one out of the gates is 60,013
and Shanks is claiming after 5,001 digits its reciprocal will repeat. So 1 divided by
60,013; it will seem random for 5,001 digits then you're like, this is familiar, it'll be the same
as earlier. Should we check one of them? Because on the way in today I wrote a little bit of Python
software - my ShanksBot - which will do to this automatically. So give me a prime and I'll put
it in here and see what it says. - (I'm going to pick 61,561.)
That has 405 digits.
What have we got? 405! Shanks and ShanksBot agree. So I tell- we'll do one by hand and I'll show you
what the ShanksBot is doing and that'll show us what the worst case scenario can be. Okay,
so we'll start with the prime 7 which means the reciprocal of that prime is 1 over 7.
And this means 1 divided by 7 or, in primary school terms, how many times does 7 go into 1?
So let's do it as a long division. So here you've got your dividend, that's the number going into it,
and here you've got the number you're you're dividing it into, so it's 7 into 1. Now the
issue is 7 does not go into 1 because - this is not very groundbreaking - 7 is bigger than 1. We
have a problem. However we can try and work out what fraction of it is going to go in.
And so actually while 7 doesn't go into 1, 0.7 does go into 1. So if I say 0.7 goes into 1 once,
that's the same as saying 7 goes into 1 zero-point-once. So what we're saying is 7 goes into 1
zero-point-once but it's got a leftover, 0.3. So what we do now is we're going to put our leftover down here.
What we've done is we've said if you've got 1.0 and you put in 0.7 what you're left with
is 0.3. And now we're going to repeat that. Implied are all these extra zeros right? Because there's
infinitely many of these, which is very convenient; we just need to know now - we've already covered
this bit - how many times 7 goes into that. And now we're like, okay, we can't do- 7 doesn't go
into 0.3, 0.7 doesn't go to 0.3 but 0.07 does. And so you go
how many times does 0.07 go in? Well 4 times 0.07 is
0.28, and that's 4 times it so we put it up here, and then we subtract that off and we've got
0.020. Now at this point we actually don't need to write in all these zeros every single time.
All we really care about is the 2 and the 0 after it there right? And so we go how many
times does 7 go into 20? Well it goes in twice, it's 14. Put the 2 up there, subtract that off we get 6.
Now we can add on one of these extra spare 0s, of which there are infinitely many, 7 goes into 50
that's eight times? Put the 8 up there, subtract that off, it's 4, now it's 40. 7 goes into
uh 35 five times, put the 5 up there - and all I'm doing is the same logic as before but
now it's just a bit more algorithmic, it's a bit more straightforward. 49, 7, 1. Ah! That's familiar,
that's what we had before. And so now actually we've got exactly the same situation down here,
where now with 7 going into 10- then before I was faffing around with the 0.7s - basically
what I'll say is 7 goes into 10 once, that 7 has got a remainder of 3, the 1 would
go up there. As you can see we've now got exactly the same here, 30 would have 28 underneath, we'll
put another 4 there. And soon as we hit here that is exactly the same as what we started with here, 1
and a 0, and so this takes us back there. In theory it- you know, it's carrying on down here but because
we've got exactly the same situation all these steps will follow in the same order every single
time, which is why 7 repeats after 142857, and that's six digits. - (That's when)
(it hits this infinite loop? Will all primes hit an infinite loop like this though?) - Yes and let's do-
let's do a slightly bigger one and we'll be able to see why it has to happen eventually.
So brady here's what we're going to do: we're going to try and find the reciprocal of a bigger prime,
let's keep it to two digits, what would you like? 23 that is a prime we're gonna do a long
(Umm 23?) - 23! That is a prime. We're gonna do a long
division and we're gonna divide it into 1. Now as you may have noticed with 7s, each time I have
a result I'm trying to work out what multiple of the dividend goes into it. So in this case
straight out of the gates, 1.0 - we're going to| have to start putting some zeros on. It doesn't go into
1, doesn't go into 10, does go into 100. You're like, well how many times? I think
probably 4. And you're like and four times that is going to be 92, and then we did that four times
so this is actually our answer 0.04. We're just trying to find a number in the 23 times table
that is the biggest but not bigger than whatever our remainder is at the time.
So what I'm actually going to do over here, I'm going to write out my 23 times table if that's okay.
So 1 times 23 is 23, 2 times 23 is we just double that, 46. 3 times 23 is add those together,
69. 4 times 3 is just double what two times was so that's 92 - which is what we've
already used there. 7 times is add three and four together; so 9 and 2 is 11,
6 and 9 is 15, add 1 is 16. - (Wouldn't it just be easier to add 23 to that?)
Or you could just add 23 to the previous one. Okay I'm going to be I'm going to be honest
Brady you're absolutely right; and what I'm actually doing is um because I've done this
on a much much bigger scale when calculating pi by hand I've gotten used- I was doing this for like
20 digit numbers right? And so I've just gotten in this formula- you're right I got so obsessed
with my silly way of doing it that I didn't stop and think, is there a better way?
Let's carry 1 - okay there it is cool. And if we add 23 again we'd be up to 230, that's that's ten
times. Okay so this is going to speed up filling it in a lot. Then if we subtract that off that's 8.
Okay so now it doesn't go into 8, it does go into 80. 69 is the biggest one we're going to have,
and that's the 3. Subtract that off we're left with 11, doesn't go into 11, 110? Yeah 92.
And that's 4 times up there. We subtract this off that's going to
be 18, doesn't go into 18, 180? Yes, that's going to be 161 is the next biggest one,
7 times. As you can see once you get to the swing of this - 19, 190; 184,
8 times. Subtract that off, 6. So now, what we're looking for is the first time- 60, yeah 46,
twice. The first time we have a point where this remainder is one we've seen before.
So we're at 14 now and we've never seen 14 before, so I've got to do 14. And it's going to be 138.
That gives us a remainder of this time just 2. So have we seen 2 before? We haven't, so the
numbers we care about are the top ones, which are the remainders each time. So so far we've seen
100, we've had 80, we've had 110, we've had 180, we've had 190, we've had 60, we've had 140, well
now we've had 200. Then we said that 200 is 184 is 8 times, put an 8 up there, remainder here
is 16. Have we seen 160 before? No we haven't so now we keep going. Now the question becomes
how long can we keep going? And each time we go we add one more
here until we have to hit a repeat. Well in this case, ignoring the padding zeros, if we just take
the non-zero bit that's actually 1, 8, 11, 18, 19, 6, 14, 2. Those- that can't be bigger than 23 because
if it was bigger than 23 we would have just picked a bigger number underneath and taken off one more
lot of it. So the remainder, ignoring the zeros, is always smaller than 23. So it can't be zero,
it can't be 23, but it can be any of the numbers in between all the way up to 22 can appear in here.
They may not all appear in there, we may hit a loop point before we get there, or they may all appear
in there somewhere. And if we just redid this as n then the number of options before it is n minus
1. And so that's your worst case scenario, is it's going to take n minus 1 steps. Once we've done that
we've used every single one, the next one has to be one we've used before, we'll hit a loop point. So
funnily enough, we pull out the Shanks chart, we see here 60,017 that was as bad as it gets. That was
60,016 digits so it hit every single one of them before it finally repeated
whereas the one before it only hit 5,000, it hit like - what's that? Like you know, less than
10% of the possible values before it hit a loop point. - (Surely Shanks wasn't doing this for all-)
You know what, I don't think he was because - partly because this takes a really long time,
and you can see me doing it. The first thing you've got to do is you've got to generate your table,
and then you've got to go through and do this, and as you can see the way I'm doing it takes
up a lot of paper. - (And for a small number!)
And for a small number. And what you can do when you get here -
so I've done a lot of long division of my time - what what we did was we you want printed paper
with squares on it so everything stays lined up, and then when you get here you copy it up and you
can then you do another stripe, and then you copy it up and you do another stripe, but you're still
going a long way that way and you can't imagine he went 60,016 digits in that direction. That's
one clue he didn't do it this way. The other clue is the type of mistakes he made. Here, he thought
it repeated every 30,525 and he corrected it to 61,050 which is exactly twice what he thought he had.
If you look at all these corrections he's always either doubling or halving it which makes me think
he's got a technique that probably involves powers of two or something, or some steps of halving,
and sometimes he's done one too many or one too few and that's what he's corrected. So that kind
of systematic error leads me to believe he wasn't doing it this way, he had another way of doing it.
He died in 1882 so this is like three years before he died, he's still sending in, he's up to primes up
to 110,000. So where did he get to on this one? Oh there's a note at the end - 'Note: we may hear remark
that by means of our table we can readily find the number of figures in the period of the reciprocals
of a composite number not having any higher factors than 110,000' - so
he's basically said these are useful because you can use the reciprocals of the primes
to get all the reciprocals of the composites. Doesn't say why that's useful. 'We have simply
defined the least common multiple of several numbers of figures in the...'. Yeah okay and he
explains how to do that, and then he signs off. His only practical application for what he's done
is you can use it to find another thing with the practical application.
I like this guy! He's got- I really- I like the cut of his jib.
(Imagine how good his YouTube channel would have been?) - Ah he definitely would have had a YouTube
channel. - (Oh yeah. What would he have thought of the ShankBot?)
I think- well I don't know because
if his sole goal was to find these numbers he would love ShankBot. I feel like it was the doing
that he enjoyed, and I feel like the fact that I coded it up and ShankBot just kicks it out
without flinching, not the same. - (One last question because I know you've been doing a lot of research)
(into him - was he married?) - Yeah yeah, and his wife survived him by a good uh pretty much
two decades. Yeah so he was like- every morning he's like morning honey, I'm off to work. And by work
he would just walk upstairs, start doing calculations, like oh another another hard day in the office.
There are some obvious follow-on questions that you could have at this point. You could
ask yourself how do you take the reciprocals - at least the length of the repeating part of the
reciprocals of the primes - and use it to work out the repeating part the reciprocals of composites,
which is what Shanks put in there as a little note. You can also ask yourself what's special
about the numbers like 7 that use every single one of these before they get back to
where they started. And it it turns out it's something called- you've got a thing called a
primitive root. So prime numbers don't have factors but they can't have primitive roots which involves
doing powers of things and remainders. And primes that have 10 as a primitive root will have every
single one of these pop up; because 10's their primitive root they go through every single one
before they get back to the first one. Which is why 60,013 does not have 10 as a primitive root
so it only used 5,001 and then 60,017 does have 10 as a primitive root and that's why it took the
took that long, it used every single one before it got back to where it started. And there's a thing
called a Reptend prime which also tells you the ones that have this incredible property. So if
people want to look into it there's a lot more fun. For me however all about the long division.
(So just so I'm clear, 60,017 are Reptend primes?) - Yes.
(Because they go to the max.) - Yeah yeah yeah I will allow that as a definition.
If you like this video you're really gonna like Matt Parker's new video for Pi Day 2022,
it's on his channel standupmaths. And also Matt, myself, and Keith Moore from the Royal
Society talk more Shanks on the Objectivity channel. There are links here on the screen
and down in the video description. - Hero. Yeah, hero. Northumbrian hero.
And still world record holder for most digits of pi calculated by hand.