The Reciprocals of Primes - Numberphile

[@pXnTilde]

Its so crazy that anyone with some math and programming experience can do in an afternoon what took him years of his life. But those tools allow us to go so much further.

[@shmmh]

Doesn't give you the same insights as if you do it programmatically.

[@pXnTilde]

@@shmmh Are there insights to glean in the first place? To program something you have to understand the math, so I think you're mostly just saving procedure time

[@kaybaerwald]

@@pXnTilde But doing stuff manually gives you a potential opportunity to gain insights you might overlook if done automatically. At least I do some trial runs manually sometimes in order to understand whatever I just programmed :D

[@veggiet2009]

I'm not sure we could go further than he did, maybe if he was alive he could take our technology further, or maybe he wouldn't see the challenge in it because the computer makes it "easy" technology always has a trade off.

[@refreshfr]

As Matt said, William Shanks very likely found a way to not "brute-force" it after doing it by hand and working on it. Whereas if you program it using Matt's method which is the intuitive, basic and, dare-I-say, "naïve" approach, then it works perfectly fine, and fine enough that you don't second-guess it to find a better and perhaps more elegant approach. But programming also allows you to experiment new methods more quickly and thus maybe find a better approach faster? It all depends what is your intent: do you just want the result quickly or do you want to try to find "how things work"?

[@train_blabber]

There was a mistake in Matt's 1/23 division 😳 When the number at the bottom is 2, he carries two zeros, so there should be 08 in the top, not just 8.

[@heh2393]

_Parker Division_

[@shikhanshu]

There's always a mistake in whatever Parker does. It's the Parker way.

[@jacobwestfahl1510]

The Parker Zero if you want

[@PhilBoswell]

@@shikhanshu in his initial demonstration with 1/7 at 3:45 there's an error which would really make things blow up, as it's made to look like we're dividing by zero 🤦‍♂️ To be fair, that is *not* Matt's fault!

[@ReyMysterioX]

The Parker Reciprocal of 23

[@Rational_thinker_212]

in 1982, i was working as a lab assistant and got access to a Hewlit Packard calculator the size of 3 loaves of bread that was programable in BASIC. After learning the language i wanted to write a program that would keep the device busy over night. Everyone told me that it was so fast i would never be able to do it. I wrote a program that simply diveded intengers by each other from an array of 1000 x1000 and reported the number of digits before a repeat. After the first night it ran out of paper reporting so I altered it to only tell me when it got a result over 1000 digits. I became facinated with this and kept increasing the array size and only looking at larger and larger numbers. I soon had the poor machine running none stop over three day weekends without finishing. Some of the PhDs in the lab started to take notice and asked me to program things for them as they thought I was some kind of math/programmer genius. In fact I had no training past highschool trig. But with the the help of few references books, I hade the poor overworked gloified calculator running regressions and fast fourier transformations that before had to have a FORTRAN programmer write, punch cards and buy time on a mainframe computer. Great fun, imagine if Shanks would have had a programmable calculator.

[@mikenccc1955]

I remember those calculators :) I was in college in London in 1973 and we we had a couple of those in one of the basement laboratories. I remember they were so pricey they'd padlocked them to the bench top with a chain ;)

[@scowell]

Babbage!

[@technoboop1890]

The size of 3 loaves of bread... anything but the metric system huh

[@Rational_thinker_212]

@@technoboop1890 just for you I measured a loaf of bread from my pantry and got 576 cubic inches, time three: 1728 ci; then converted to CCs for 28316.8. I can see that is much better.

[@stuartmcmillam9214]

Love it brother... your a bigger geek than I... well done...!!!

[@thenakedsingularity]

You really got to respect this William Shanks guy. He also did the longest calculation of Pi before computers.

[@MLB9000]

Was his day job working with a chap named Armitage by any chance?

[@finmat95]

respect?

[@hydrobyte4844]

he sacrificed his arm to complete all number of pi

[@Z3R0Steam]

he's probably part of the reason we know a lot of this information too

[@molybd3num823]

@@finmat95 for sure

[@Bleighckques]

Can't believe a Numberphile video came out related to something that I've actually been doing myself. Not to this scale, but I've been trying to do these in my head with the smaller primes every once in awhile if I can't sleep (I think I'm up to 61 or 67). I use the same method of long division, but I don't keep track of the actual value of the reciprocal because I lose track, I just count how many steps before I reach 1 again. A couple interesting things I've found: - The point about doubling or halving the solutions Shanks had isn't due to how he's acquiring the answers but rather due to a property they all share. Not only do all the answers fall into the range of 1 to n-1, but they are all factors of n-1. For example, 13 has 6 digits that repeat, 13-1 is 12, of which 6 is a factor; 53 has 13 digits that repeat, 53-1 is 52, of which 13 is a factor, etc. So it would be common to have a mistake that leads you to count past the halfway point and simply conclude that the answer must be n-1 because it is the only remaining factor after reaching (n-1)/2, leading to later having to halve the answer to correct it. - The numbers that have n-1 digits in their answers all have just one string that repeats for every fraction in the range 1/n to (n-1)/n. 7 for example, 1/7 = 0.142857, 2/7 = 0.285714, 3/7 = 0.428571, 4/7 = 0.571428, 5/7 = 0.714285, 6/7 = 0.857142. However, the numbers with answers that are some factor (n-1)/x will have x different sequences of numbers. 13 for example, 1/13, 3/13, 4/13, 9/13, 10/13, and 12/13 all repeat 076923 with different starting points, but 2/13, 5/13, 6/13, 7/13, 8/13, and 11/13 all repeat 153846 instead.

[@snowfloofcathug]

That’s really cool! Thank you :D

[@natheniel]

Shanks is this you?

[@natheniel]

can you elaborate on the last point?

[@Tracy_AC]

you have 9/13 twice

[@haulin]

Awesome. Anyone's got Matt's script to calculate those? It would be interesting to see the sequence of the factors of n-1 and see if there's a pattern in there.

[@EchosTackyTiki]

12:30 I think the fact that he just did it because he wanted to, not because it was useful, but just because he thought it was fun, is the most endearing part of his story. I like little historical footnotes like that. I think sometimes they make all the difference.

[@TrickyTricky914]

One thing that I like is that it humanizes him more. We (or at least, I) often forget that humans back then are largely the same as we are now. Everything back then when I imagine it in my head is all stern and serious. But things like this show where that isn’t the case.

[@hksg]

you really think it wasn't useful? it actually was. May be he didnt know that time exact use case. But just tell, why are scientists have calculated trillions of digits of Pi? most of things he did had a great physical significance and have been proven over time. some say, if we got exact repetition of Pi's digit, we can exactly expain lot of theories, in space-time, blackholes gravity etc etc.

[@Faroshkas]

​@@hksgwhat

[@nicezombie8054]

​@@hksghowever if pi would repeat it would be rational and pu is proven to be transcendental aka irrational and no solution of a polynomial with coefficients being integers

[@pickleballer1729]

"His only practical application for what he's done, is you can use it to find another thing with no practical application." The amateur mathematician's creed! I worked out the algorithms for getting all of the irreducible Pythagorean sets, the sums of squares and cubes up to n, and worked on Fermat's Last Theorem for a long time just because I was curious. A friend of mine asked me over and over why I did that when I could have just looked it up (I never imagined that I was the first to do any of that at all.) The only answer I had was. "It was fun."

[@gomotion5725]

Yes! The need for everything to have a practical application kills the curiosity. A lot of the most interesting and mind blowing things are discovered accidentally often by doing useless things only driven by curiosity. Not because someone wanted to find something useful. I think most successful scientists to their stuff because understanding unknown things is fun. Otherwise science would be far to exhausting :D

[@mathsman5219]

@@gomotion5725 If you don't know the practice applications it doesn't means they don't exist.

[@hansjakobrivertz1118]

Fun, but it also sharpened your brain. Most youths today are loosing so much because they google everything.

[@eekee6034]

Math is the ultimate puzzle game. :) I've played the mathematically autogenerated games of Simon Tatham's Puzzle Collection for years, and the feeling of satisfaction when you understand how the logic you applied solves the puzzle is just like the satisfaction of solving a mathematical puzzle.

[@hb1338]

A famous maths professor once remarked "this is a branch of mathematics which remains untainted by any form of practical application".

[@pectenmaximus231]

“It’ll seem random for 5001 digits, and then you’re like, ‘this is familiar’” Yeah, happens all the time

[@samrandall6623]

all you would need do is see if the dividend is equal to the starting dividend (1.0...) :)

[@vigilantcosmicpenguin8721]

We've all been there, just calculating digits, when it seems like you're going in circles.

[@simonmasters3295]

Made me laugh

[@SinHurr]

Every prime Thursday

[@cameron7374]

@@samrandall6623 No. Since you could have the first 100 digits repeat way earlier than the actual repetition point.

[@csolus]

You forgot to mention this nice property: if you take the repeating "number" (e.g. 142857 for n=7), you get a number N with a very nice property: every multiple of it is a circular permutation (e.g. 2*142857 = 285714), which also extends to products by any number, assuming that you chop the result in chunks of size n-1 and add them up. For instance 142857^2 =20408122449, and 122449+20408=142857 ;-) ;-) It's quite obvious given the origin of this number, but the property is really cool.

[@d4slaimless]

There's a separate video about 142857 and this kind of properties.

[@Chrnan6710]

That's how I remember my decimals of sevenths! I just remember the cycle "142857" and I figure out where to start in the cycle by starting at the nth largest number in the cycle for a remainder of n/7. For example, 12/7 = 1 + 5/7 = 1 + [what is the 5th largest number in the cycle? 7!] = 1.714285...

[@wrstark]

nice

[@AIYOU_]

@@Chrnan6710 Funny that the way I remember it was that 1/7 was just the times table of 7 0.14285714 Is 14, 28 and 56 just in sequence

[@SpeedcoreDancecore]

How do you prove that?

[@charlottedarroch]

The way Shanks likely did it was by calculating the multiplicative order of 10 modulo the given prime p. This order always divides p-1 and there are a variety of tricks to make modular arithmetic by hand much easier. And so, for example, to show that the order of 10 mod 60013 is 5001, one would need to show that 10^5001 = 1 mod 60013, but that 10^d =/= 1 mod 60013 for any proper factor d|5001. So one would need only check the factors 1,3 and 1667.

[@AyanKhan-if3mm]

Hey can you please elaborate it a bit more? Why do we need to check for only 1,3,1667?

[@charlottedarroch]

@@AyanKhan-if3mm Well you only need to check those factors if you suspected that the order of 10 mod 60013 was 5001, which we would if we were double-checking Shanks's results. If you were doing this by hand, you'd want to check all the factors of 60012, but you could do so in a somewhat systematic way. For example, if you had found that 10^5001 = 1 mod 60013, you now only need to check factors of 5001 itself. But to be more systematic you could begin by checking if 10^60012 = 1 mod 60013 (you don't actually need to check this, by Fermat's Little theorem). Then check the factors of 60012 which have a single prime divisor divided out. So these would be 60012/2 = 30006, 60012/3 = 20004 and 60012/1667 = 36. You'd find that 10^30006 = 10^20004 = 1 mod 60013, but that 10^36 =/= 1 mod 60013. So this tells you that the order of 10 mod 60013 divides both 30006 and 20004, but doesn't divide 36 and must therefore have 1667 as a factor. Putting these together, one obtains that the order of 10 is divisible by 1667 and divides 10002, so it must be one of 1667, 3334, 5001 or 10002. So you already know that 10^10002 = 1 mod 60013, so you could now check 10^5001 = 1 mod 60013, which would eliminate 10002 as the order. At this point, showing 10^3334 =/= 1 mod 60013 would confirm that the order of 10 mod 60013 is exactly 5001. There are a variety of different orders you might want to check things in, since knowing for example the value of 10^1667 mod 60013 allows computation of 10^5001 mod 60013 just by cubing and taking the remainder. However, in a sense the most systematic way is to take the highest number you know could still be the order, say x, and look at all the divisors of that number by a single prime factor, x/p. If x could still be the order, i.e. you know that 10^x = 1 mod 60013, but that none of these numbers x/p can be the order, because you find out 10^(x/p) =/= 1 mod 60013, then that is already complete confirmation that x is the order.

[@giggabiite4417]

@@charlottedarroch when u started, I knew what u were saying, but by the last paragraph, my brain stopped trying lol

[@joshuatilley1887]

@@charlottedarroch I wonder if there is a way that doesn't require the factorisation of p-1? This step would be rather time consuming.

[@TheElCogno]

@@joshuatilley1887 I don't think there is. But factorizing p-1 is not that bad. It's guaranteed to be divisible by 2, there are elementary tricks to check divisibility at least by 3, 5, and 11, each time you find a factor the next step gets easier, and those numbers are at most 5 digits. What is very time consuming is to factor a number that factors into two large primes, for which you'd have to check every prime number up to the smallest factor.

[@irakyl]

Brady's question of "will all primes hit an infinite loop like this?" has an easier answer. All reciprocals are periodic, because if they didn't have a period, they would be irrational, and they are clearly defined as a ratio of 1 and the prime.

[@2712animefreak]

But, composite numbers can have some digits before the loop, whereas prime numbers never do.

[@LukePalmer]

Also Matt's proof is constructive, whereas this is a non constructive proof. That is, from Matt's proof you can extract a method for finding the period, whereas yours just says "it's impossible for it not to periodic".

[@duncathan_salt]

worth noting that any prime factors of the base you're working in will have a unique property to their periods compared the other primes: leading digits before a period of length 0

[@donaldhobson8873]

And what matt was proving here is basically the rational => periodic proof.

[@nurfitriabdhalim3607]

But 1/2 =0.5 and 1/5 is 0.2 of I am missing something here🤔

[@DMC88mph]

After watching Matt Parker perform impressive math for YEARS, I'll gladly help him with the long division with which he seems to struggle, lol.

[@tangyspy]

He even got the 1/23 wrong 🤣

[@jbwm1000]

I can't believe what I'm watching, to be honest! Haha😂

[@undercoveragent9889]

He blinded you with science,pal. Lefties like Matt do not _do_ 'impressive math'.

[@Paul-sj5db]

So, Schenk ran a boarding school. Maybe he crowdsourced the process by getting the children to do a prime, as punishment or just normal work. With a few children doing the same prime he could have some error correction as long as they didn't copy off each other. The strangest part of this was the relative lack of curiousity of how he did it.

[@Halfasomersault]

I personally would not trust disobedient kids to do my life's work.

[@kenahoo]

Look at 10:30 for the curiosity of how he did it.

[@genfre]

That would be prime and punishment.

[@jacobpeters5458]

the strangest part was devoting 1/7 of the video to explain how long division works........

[@mathematicalmodelz]

@@jacobpeters5458 cope

[@Gribbo9999]

Loved the lesson in long division by hand. This arithmetic process we learned at the age of about 6 or 7 back in my day (70 years ago!). So it seems a bit strange to see a serious mathematician like Matt working his way through it step by step (doesn't everybody know how to do this?). But truth be told, I tried to do a long division by hand while back and was shocked to find I'd forgotten how to do it after 50 or so years of calculators! Thanks for the refresher :)

[@BlueScreenCorp]

This is still the simplest but longest way to do division and this is what I learned in school 25 years ago learning division in grade 3, and this is what children learn today. There are faster methods but this one always works

[@CandidDate]

You can even do long division with polynomials of any power. The remainder contains the original polynomial.

[@isaacelkington2508]

@@BlueScreenCorp I'm sure a lot of children aren't taught long division. I was never taught this method (5 years or so younger than you).

[@Pozi_Drive]

On the continent the division is depicted easier: 17 / 29871 / result to calculate 29871 / 17 The way he does things is very chaotic. No wonder the guy uses Python and not Modula or Oberon, like a true mathematician would do.

[@SquirrelASMR]

I never learned and did CS and lots of math in shcool

[@thomaswagner9875]

Fascination - brings back memories of high school back in 1968. I wrote a Fortran program to compute how long of a repeating sequence that the inverse of an odd number was. My program worked correctly and I had fun using it, and showing the results to my high school math teachers.

[@peterpike]

The way that digits repeat depends on the base you're using too. For example, 1/7 = 0.142857... in base 10, but in base 6, the same value would be 1/11, and it would be 0.0505050505... And most fun would be base 8, where 1/7 =0.111111... Just like in base 10, 1/9 = 0.111111... and for the same reason: 1/[base-1] is always going to equal 0.11111... So if you want to know what the reciprocal to any particular number is without having to calculate it out, now you know for at least the base that's one more than the value you're looking for.

[@mathsciencefancier]

Yap. I think a number cannot be expressed without its background; a base; like binary, decimal... A number represents relationship as far as I learned. Without a based-background, then this world now is using Egypt-Pyramid numbers or Roman's number perhaps?

[@mathsciencefancier]

Anyway, that's cool not to calculate but got result with very easy numbers!

[@Qermaq]

Yes - any number with a prime factor not shared with a base has a repeating decimal in its reciprocal. So any number with only 2s and 5s as prime factors will have a terminating decimal in base 10. But introduce any other prime factors, you get a reptend. In base 6, the key prime factors are 2 and 3. In a prime base, only that prime itself is a factor of the number whose reciprocal terminates.

[@Ewr42]

@@mathsciencefancier we forget that our common base 10 is a subjective choice, general maths is much more interesting than what we focus on, and I'm not even considering the other axioms we removed from ZF bc people didn't like implications like infinity.

[@peterpike]

@@mathsciencefancier -- True. Numbers are really just loops, or repeating patterns, and how you divide them up depends on a lot of arbitrary choices. A while back I made a graph which I called the "Factor Field" because it represented all numbers as such patterns. So the first column had cells filled in every row, the second was every other row, the third column was every third row, etc. And using that, you could easily see what the factors of any number was by finding the row that represented the number you were looking for and seeing which cells were filled in. Every column filled in on a row represented a factor for that numbers. So, row 6 for example, had cells filled for column 1, 2, 3, and 6. The thing about this graph was that it was completely unlabeled originally, and yet just looking at how the numbers related to each other, there were very obvious repeating patterns that came out of it. For example, because of the cluster of columns 1, 2, and 3 every six rows, there was a bit of a "spike" in the graph every six rows. So, in my opinion, if we had not arbitrarily chosen base 10 as our foundational base, base 6 mathematics would have been far more natural to use. It's why often when I am learning a mathematical concept, I try to see what it looks like in base 6. One awesome thing base 6 math taught me was how every prime number MUST end in either a 1 or a 5 in base 6 mathematics. Any number ending in 0, 2, or 4 is divisible by 2, just like in base 10 (since base 6 is an even base), and any number ending in 3 or 0 is divisible by 3 (just like in base 10 every number ending in 5 or 0 is divisible by 5). This means that you're left with numbers that end in 1 or 5 being the only possible numbers that are prime. Only after I "discovered" this did I look up some information on primes and learned that it's already been established that all prime numbers greater than 3 fit the pattern of 6n +/- 1, which is the base 10 equivalent of what I had discovered in base 6. The other thing I was able to prove from base 6 is that if a number ending in 1 or 5 in base 6 is NOT a prime number, the only possible factors it could have likewise must end in 1 or 5, and this necessarily must follow because when you multiply a number ending in 1 by another number ending in 1, the result will end in 1. Likewise, numbers ending in 5 multiplied by numbers ending in 1 must end in a number ending in 5. Finally, in base 6 specifically, numbers ending in 5 multiplied by another number ending in 5 must result in a number ending in 1. No other numbers can multiply together in base 6 to end in either 1 or 5. I'm not sure how useful that is, but it's fun and that's what really matters.

[@priyanshupaswan2184]

Getting numberphile, stand up maths and objectivity notification at the same time.. gonna have a great time

[@user-mq3um5iu2q]

What about Tom Scott!?

[@amylaneio]

Objectivity, too, also featuring Matt.

[@vigilantcosmicpenguin8721]

A triple dose of Matt, that's fun.

[@nemesisurvivorleon]

add Computerphile to that for me

[@SpicyMelonYT]

Amazing how difficult of an explanation he gave for long division when he’s so mathematically capable everywhere else. We learned long div a bit different and he made it more convoluted

[@andrewcorrie8936]

Agree. I have never learned to say to myself, "7 doesn't go into 1, but 0.7 does"; but rather, "7 into 1 won't go; write in a zero and a decimal point; use the following zero "7 into ten goes 1 remainder 3", etc.

[@perplexedon9834]

​@@andrewcorrie8936you're describing the process, Matt is explaining the reasoning. There are simpler ways to teach someone how to do the steps of a method, but Matt is trying to concisely remind/teach the viewer of WHY the process works. It's like an automotive engineer explaining how to use the clutch on a manual car by talking about interrupting the transmission through gears, but if you were teaching someone to drive you'd just say "put the clutch in before changing, and slowly pull it out after".

[@HonkeyKongLive]

He was explaining the fundamentals. The point of these videos isn't to get to the end, it's to show how things work.

[@KusaneHexaku]

@@andrewcorrie8936 i love comments of people failing to grasp what Numberphile is about, it's always funny

[@andrewcorrie8936]

@@KusaneHexaku Glad to have given you a chuckle, then. Personally, I thought the traditional method explains what is going on at least as well since the place value (mechanically) allotted to the computed values as one proceeds immediately tells you what it is, in fact, you are calculating. In fact, at least in Britain, that is a not uncommon kind of school question: given the answer to 10/7 = 1.428..., calculate the value of 100/0.7 or 0.00001/70 etc. But I am obviously wrong and will now go and write out my times tables as some sort of penance.

[@kektagonb3469]

I don’t know what I was expecting coming to watch this video, but I definitely didn’t expect to finally truly understand long division. Something about how you demonstrate it so simply made it finally click.

[@Klaevin]

this must be the tenth time it clocks for me... tomorrow, I'll have forgotten again. I'm not bad at math, it's just long division and I don't know why

[@JacobPlat]

We called it staartdeling (taildivision).

[@danfg7215]

long division is taught and done very differently in Brazil

[@tgwnn]

Haha it's funny because I thought his explanation was terrible. No offense to Matt, I love him -- it was just not Matt at his best I thought. I wasn't even going to comment this until I saw yours; it's just funny how different people like (very) different things even in the same topic.

[@Slackow]

@@tgwnn I mean the method was inefficient but it helps you understand how it actually works, because you can see what you're doing is shifting around a factor of 10 and summing the individual calculations.

[@TmOnlineMapper]

I did some digging and found a pretty efficient method of calculating the period length of prime reciprocals. Essentially the order of 10 (mod p) is the period length. Now the order of a number mod another number is the smallest n for which a^n = 1 (mod m). Meaning that we just have to find the smallest n for that 10^n = 1 (mod p). For primes, n is gurantueed to be a divisor of p - 1, which means we just need to factor p - 1 and calculate all divisors from that list and try them in order from the smallest to the biggest. Now the best part is all these calculations are pretty fast to do (even by hand). Integer powers in mod space are fast to calculate for practically any arbitrary power or base, for factorization you don't need to check any primes starting at 239 (aka the first 51 primes). In summary I believe with that method you can calculate the period of the reciprocal in around 30 minutes by hand. Faster with practice ;) Now this method is also extremely fast for computers. For example I calculated the period of the reciprocal of 18446744073709551557, which is 4611686018427387889 digits. And that calculation was done in less than 240ms. Funnily enough when I the primes used to factor p - 1 are cached the whole process takes around 3ms, which shows that the hardest part about the whole calculation is generating the primes for factorizing p - 1. The power calcuation is practically a joke even for numbers of this magnitude.

[@ericthebearded]

That's pretty cool that the order (mod p) of 10 is the period. I have one question on your calculation method. You say "for factorization you don't need to check primes larger than 239 (aka the first 51 primes)". How is that the case? Even for numbers well below 18446744073709551557 (take 4098 for example), how can you do the factorization without needing to check primes larger than 239?

[@TmOnlineMapper]

@@ericthebearded Well for prime factorization you just need to check all primes up to the square root of the number you're checking. Now the square of 233 (51st prime) is 54,289. Now you may ask, why so low, when we're checking numbers of 100,000 and above? Well, p - 1 is always divisible by 2. Meaning we can easily cut that in half. And I picked 233 just so we have a tiny buffer. Oh. And my wording is wrong. I meant "for factorization you don't need to check any primes starting at 239 (aka the first 51 primes)". I hope that helps :)

[@Kirian42S]

Parker speaks of Shanks using a "trick" of some sort, but he notes that the full repetend primes are those for which 10 is a primitive root, i.e., the multiplicative order of 10 is p-1. I suspect Shanks was performing some sort of modular exponentiation--which, while ultra-ultra fast in computer code, is still faster than long sets of multiplications even when used by hand. So factor p-1, then check if any factor is the order of 10. Take 28559, which has p-1 = 28558 = 2*109*131. You can skip the 2 for any prime larger than 100 (as 10^2 will just be 100 (mod p)). To decide whether 10^109 = 1 (mod p), you'd use modular exponentiation on 10, which is basically going to be long division with shortcuts--but a lot less long division than what Matt would have needed!

[@hundeeba7449]

I arrived at the same conclusion and came here in the comments to search if any one has found it too. Kudos you.

[@TheEternalVortex42]

Although much better than doing the long division, this isn't actually efficient since computing the factors of p-1 has no known fast (polynomial time) algorithm. Indeed the problem of finding the order of a number (mod p) is known as the "discrete logarithm" problem, which likewise has no known polynomial time algorithm (and, like factorization, is actually the basis for some cryptography, thus we hope no fast algorithm will be found).

[@saetmusic]

My brother spent decades completely obsessed with Prime Numbers. Shortly before he passed away, he sent me a thick packet of his research. He believed he had discovered "The Codification of the Primes" and "The Periodic Table of the Primes" as Mentioned in Santoy's book, "The Music of the Primes" There are handwritten pages of notes and then there are dozens of pages just filled with numbers. I can't make anything of it, but is it something you might be interested in seeing?

[@carbdebunkshate8967]

have you sent them an email? Maybe send it to some university if they haven't responded because that sounds very interesting and it shouldn't just be forgotten

[@axx9149]

I agree, that sounds like it deserves being checked out. Any update?

[@undercoveragent9889]

@@carbdebunkshate8967 Yes, but he should send only a few pages because academia is morally bankrupt. Lockdowns and war; they are what modern science is for.

[@uggupuggu]

update?

[@Ebvardh]

This is a bad place to ask what you’ve asked as your comment is bound to get lost in a sea of other comments. I recommend you email the people in the video.

[@RobertMilesAI]

I want to see this table typed up (or OCRed) to see if there are any places that Shanks and Shanksbot disagree. Are there any mistakes in the table that weren't already caught and corrected?

[@r3l4x69]

theres not much of a reason to do that

[@danbance5799]

@@r3l4x69 There is one reason, and it is perhaps the greatest of all reasons: because it's there.

[@infiniteplanes5775]

Mathematics is an unusual language, for its only goal is to further itself

[@nofriends4784]

@@infiniteplanes5775 don't all languages do so?

[@patrickpablo217]

@@r3l4x69 for Science!

[@jaafars.mahdawi6911]

Just as informing as it is entertaining! One tiny 'hiccup' i couldn't resist stating out, though (typical math enthusiast): When the remainder is 2, we don't go straight to 200 but to 20 instead, hence a missing 0 in the resulting sequence of digits..

[@Robi2009]

Yeah noticed that too 👍

[@diegovski]

His method is called the Parker Division.

[@igrim4777]

10:24 , Matt: (reads line in book) 60017 is as bad as it gets. It hits all 60016 possible minuends. Brody: (zooms in on book to show the very next line, 60029 hits all 60028 of its possible minuends)

[@J.D.Mckruger03]

Years of dedication in one book.

[@juliuszkocinski7478]

I'd say many books, especially in field of science have years of dedication poured into them

[@fcturner]

General definition of a PhD thesis

[@hikatoyshi]

He also spent decades computing the digits of pi (500 were correct, the last 100 were wrong)

[@Gruuvin1]

With no practical purpose.

[@Sonny_McMacsson]

When divorce wasn't seen as an option, you'd hide in your home office all day and compute stuff.

[@VoidHalo]

I've always admired mathematicians who worked before the days of calculators. When, no matter how simple the calculation was, you HAD to do it by hand, and you had to do them every time. And you had to be damn sure that every single digit in every single calculation, no matter how menial MUST be 100% absolutely perfect. Or you will perhaps unknowingly continue on with your work, not even realizing you made the tiny error until some time probably well down the line when you finally check your work. The tedium must have been incredible. I always speculated that more famous mathematicians like Gauss might have had an assistant to do all of the little tedious calculations. But I also have to wonder if they might even trust the work of somebody else, since it has to be so perfect. Or maybe that's how an apprentice would get his feet wet. Helping out a more skilled mathematician with all of the tedium. That's usually what apprentices get stuck doing, tedium.

[@SpiritmanProductions]

Impressed by Shanks's work, but then flabbergasted at the incredibly clunky long-division process! 😯

[@beenaplumber8379]

@@StopTheRot It's not clunky at all. I haven't seen anyone make it look so convoluted and bizarre since the 70s, when grandparents were complaining still about the "new math." This was an absolutely dreadful description of how to do it. It's really simple and easy. Don't they teach long division anymore?

[@slzckboy]

@@beenaplumber8379 i enjoyed the videoas a whole.. i wrote my own shanksbot at the weekend after watching it. However the long division process description was made more confusing that it needed to be. I have a new found appreciation for my primary school teacher in the 80s now

[@SpiritmanProductions]

@@beenaplumber8379 I meant tortuous, really. 'Clunky' does get used for this meaning, though. ;)

[@TheBookgeek7]

What would y'all use instead?

[@TheBookgeek7]

@@slzckboy...and how else would you describe it?

[@rev6330]

From just looking at the tables, it seems that for any prime p, the length of the period of the reciprocal can NOT be ANY number between 1 and p-1. Because in any example we see, the period length (let's call it l) always devides p-1. In many cases, the smallest common denominator is just 1, so l = p-1. But in other cases, like p=60013 example, l is 5001, which is (p-1)/12. I'm not really qualified to quickly understand why that is, but it very much appears that way. So, Matt's explanation at 9:34 is a little missleading, as it suggests that the period of 1/23 could in theory have any length l from 1 to 22, while practicly, it can only ever be 1, 2, 11 or 22. Which also means that you don't need to calculate the reciprocal all the way up to p-1 digits, but only up to (p-1)/2+1 digits. Because if it doesn't start looping at that point, you know it will only start looping at p-1. A little more explanation on this would be sweet. :>

[@freddiecarter9320]

If we let m be the smallest decimal period of 1/p then (1/p) * 10^m = n + 1/p where n is some integer, rearranging this, we find that 10^m - 1 = n * p, which tells us that 10^m is congruent to 1 modulo p. A theorem due to Fermat (Fermat's little theorem) states that x^(p - 1) is congruent to 1 modulo p for all primes p and integers x that p does not divide, so we know that 10^(p - 1) is congruent to 1 modulo p. If we let p - 1 = m * x + r for some integer x and 0

[@iras66]

You are looking for the multiplicative order 10 mod p. The reason is the following. If you stop after the first repetition in the devision and you multiply back you will get 0.999...9 for some number of 9s (let's call it k). Moreover, if you see the number N after the decimal point you will have pN=10^k-1. In particular, 10^k-1 is divisible by p. This argument also works in the other direction, so at then end you are looking for the smallest k such that p divides 10^k-1 which is exactly the order of 10. The fact that k divides p-1 follows from Fermat's little theorem. I suppose this is also how you calculate the smallest period if you are smart enough. Factorize p-1. Try if 10^k-1 for any k=(p-1)/q where q is prime. If not, we are done (the shortest period is p-1). If k=(p-1)/q works then start the next prime divisor, and so on. Also, in order to determine whether the order divides a certain number k, it is enough to do modular exponentiation which is probably much faster than doing the actual division. I'm pretty sure this was all known in the 19th century or even much earlier, and I'm quite surprised that Matt didn't seem to be aware of any of these.

[@debblez]

what the question is asking is how many numbers are a power of ten, mod p so if the number, idk, n, is not a power of ten, then 10*n isnt going to be either, nor is 100*n or 1000*n, etc. So you have the group of numbers that are 1*10^x numbers that are maybe lets say 3*10^x, maybe 7*10^x, and for each group of numbers x goes from 0 to the cycle length we’re after. since they are all the same size and together they make up every number up to p-1, they have to divide p-1

[@XxRiseagainstfanxX]

You can stop looking for divisors from the square root up, no need to go all the way to half the number.

[@Alex_Deam]

In case anyone reading this is interested to go deeper, the number theory result others have explained can be generalized using (a simple consequence of) Lagrange's theorem from group theory: the order (here: the smallest power of ten necessary to get to 1 mod p) of ANY element in a finite group (here: the multiplicative group of integers mod p) always divides the number of elements in that group (here: p-1).

[@julienfb4693]

The fact that the video was uploaded at 3:14pm on 03/14 is overkill but so nice π😎π

[@patrickmckinley8739]

In grade school, I had a similar fascination for the reciprocals. The property that made them so special was the ability to multiply by a small number by shifting the digits. For example, you can double 142857 by moving the first two digits to the end. One interesting observation about the primitive roots is when you get half way through the period, you get the (n-1) remainder. Noting that every possible remainder has to be used in some multiple of the reciprocal is Fermat's Little Theorem. I really expected that yo be mentioned in this video.

[@Living_Murphys_Law]

I never noticed that about 1/7. That's really cool.

[@liam3284]

That has some interesting properties for fast math opimization.

[@Hedning1390]

-2 and 5 does not create repeating digits which means you could get remainder 0. -You can't just add a 0 without moving right in the digits of the result. The 2 makes a remainder 20 before making 200 and thus puts a 0 in the result.

[@mbrusyda9437]

technically there're repeating 0s

[@rimantasstanaitis7280]

@@mbrusyda9437 but then technically every natural number will have this property of having a repeating loop of digits..

[@glenneric1]

You're right. AT 8:54 the 2 would become a 20, which still is smaller than 23, so you have to add a 0 to the board. He added an 8.

[@mbrusyda9437]

@@rimantasstanaitis7280 I mean, they are a subset of rationals, so yeah

[@Hedning1390]

@@mbrusyda9437 Even if I grant that technicality (which I am not) it would still be wrong to say you never get remainder 0, which he does say and even draws a picture with a bracket excluding 0.

[@longcastle4863]

Would actually have loved to have had explained what system Shank used to do his work so he didn't have to divide everything by hand.

[@gregoryfenn1462]

Probably exploited Langrange’s Theorem or Fermat’s Little Theorem

[@cheems1337]

This is basically calculating the multiplicative order of 10 (decimal system) mod 7. There are methods to do it a lot faster

[@spiffinn_music_lists]

Yeah i really mean no offense to matt but this wasn't his strongest video. his explanations were misleading and lacking (especially given the insights in the comment section)

[@redpepper74]

@@artificialintelligenceplus1321 using an algorithm to _predict random numbers_ is not going to work

[@syindrome]

"What's in the Shanks?!"

[@marcjasonsantos2465]

There is a mistake in 8:50 , there should be a 0 between 6 and 8 since the remainder is just 2 and you cannot just add two zeros to the remainder, it should be one by one. In the addition of the first zero, the remainder becomes 20 and since there is zero amount of 23 in 20, the result is 0 and a remainder of 20 then you add another 0 to make the remainder 200 and that's where the result becomes 8 and produces a remainder of 16. So there must be 0 between 6 and 8 in the results. Anyways, a great video! Shanks is a chad!

[@dakshbadal7522]

Came here looking for someone pointing out the mistake. Well done.

[@RameshKumar-mv3jd]

Thank you. I was looking for this correction

[@yutnee]

I caught it as well. Cool video!!

[@johnlratcliffe]

Yes. Saw that too.

[@thehosenbugler]

The mistake is actually at 8:45. 60-46 is 14, not 1.4 - the 14 was incorrectly 1 place to the right. This was corrected with the '200' moved 1 place to the left (the correct position), so there isn't a missing zero.

[@ilyrm89]

Parker will always amaze me with his interesting math insights!

[@cougar2013]

Except for saying that 60017 is as bad as it gets with 60029 right there below it on screen

[@elvwood]

I'm kind of glad Shanks isn't around to meet the eponymous bot! Back around 1970 I read a comic featuring someone who is cryogenically frozen for a pioneering trip to another planet; when he's revived he's welcomed by hordes of cheering humans who got there ahead of him thanks to the development of faster than light travel during his journey. It really got to younger me: how must it feel to see something you've sacrificed so much for become easy or irrelevant? Happily I just teach maths, so if - say - someone were to come up with a technique that makes long division obsolete, my next groups of learners can just learn that instead - I've picked a career that's proof against that particular worry!

[@Llanchlo]

That's the basic plot of Far Centaurus, A E Van Vogt, 1944

[@johngrint8231]

I thought this video might be about the sums of the reciprocals of primes, which are pretty fascinating. For example, if we take all 20-digit primes, the sum of their reciprocals is almost exactly 1/20. More generally, the sum of the reciprocals of all n-digit primes is approximately 1/n, and this becomes increasingly accurate as n increases. Even more remarkably, this holds true whether working in base 10, or in base 2, or in any other base.

[@Blobfish3561]

By that logic, it means that the more prime reciprocals you add, the smaller the sum gets which doesn’t make sense

[@Mathemarius]

@@Blobfish3561 Come on, start thinking.

[@Blobfish3561]

@@Mathemarius oh sorry i misread it cause i thought he meant that the sum of the reciprocals of the primes up to the nth prime is approximately 1/n

[@jessepost1108]

In 1/7, wouldn't 1 be the dividend? And 7 the divisor?

[@fatmn]

Incredibly distracting that he kept calling it the wrong thing

[@SigmaChuck]

Slightly annoying but ienjoyed the video anyway

[@thegreatwebstar]

My great uncle had timetables for what time "exactly" the mail arrived everyday for close to 100 years... pretty sure his grandpa started it, looked exactly like that book lol... a lot of work (half a lifetime actually) Cool video, thanks for keeping math alive

[@greenaum]

What, he worked it out in advance somehow, or waited til the postman came each day and wrote it down? The latter, sorry to say, is the work of a lunatic, an obsessive. 100 years of completely useless information, even in theory, absolutely no use for it. Unless I suppose you wanted to catch the postman sloping off to the pub when he should have been working, 70 years ago, when he was alive.

[@j.vonhogen9650]

They must have been trapped in the crawl space of their house for almost 100 years to be able to collect all of that data. Maybe they were looking for a pattern while planning their (failed) escape from that crawl space. I'm just kidding. Maybe your father and grandfather were spies or codebreakers working for an intelligence agency. Was their house close to an embassy perhaps?

[@Vnifit]

@@greenaum or maybe back before we had incredible entertainment options, people instead picked up unique hobbies to pass the time. I'm sure he wasn't obsessively waiting for the postman, probably went about his life and recorded it whenever he knew/could estimate it well enough. Also some of the worlds greatest inventions have been because someone was obsessive about something "useless".

[@damienstubbs6246]

Do a statistical analysis just for kicks!

[@jameslatimer3600]

As a letter carrier for 14 years and a supervisor of letter carriers for most of my other 19 years I'd be willing to bet that the delivery times didn't vary that much. Summer heat and rain, winter cold and snow our times around the routes were like clockwork. There must have been clues we didn't consciously recognize to say whether we were early or late. Missing buses, for example, meant possibly having 20 - 40 minutes added to our day.

[@ankyfire]

This video is absolutely fantastic!!! Not only all math is explained in a really easy to understand way, you can see how much fun that guy is having. It's always so much fun watching someone talking about their passion.

[@idkmax5977]

This KZbin channel is one of the best channels on the KZbin which can be used for wide range of users to create intrest in mathematics and change their negative views over the exact science Mathematics

[@FirstLast-gw5mg]

"So will all primes hit an infinite loop like this though?" Well yeah actually _all rational numbers_ will hit an infinite loop like this, because a rational number divided by another rational number is also a rational number. And a rational number is any number which ends in some repeating sequence (or terminates, which really just means it ends in a repeating 0).

[@ERROR-ei5yv]

and every reciprocal prime number will have a non-terminating decimal expansion (never ends in 0's) in every base except itself (like 7 doesn't terminate in any base but 7, 23 doesn't in any but 23, etc) Edit: correction, this also includes bases that are multiples of the prime number (like 1/7 in base 14 or base 49)

[@KisoX]

@@ERROR-ei5yv Except 2 :)

[@thomasbui6175]

@@KisoX AND 5

[@FirstLast-gw5mg]

@@ERROR-ei5yv After your correction this is correct. The reciprocals of 2 and 5 terminate in base 10 because 2 and 5 are the prime factors of 10.

[@_prash]

I don't think terminating and repeating means exactly the same thing, that's why we do both these cases separately. He was asking about a loop or say "bar" of that number and you are mentioning terminating as repeating which isn't the same thing in case of rational number if we go into the deep, I know that rational number has property of either terminating or repeating but your comment isn't completely true.

[@emmeeemm]

In response to Brady's question about whether all primes will do this, Matt is very nearly correct with his answer of "Yes". Matt has overshot by two primes. 2 and 5 do not have periodic decimal representations for their reciprocals. This is because they both divide evenly into 10, in decimal and thus terminate the long division algorithm. Primes which are factors of your counting base will not have this periodic representation property. All other primes will. Of course, I understand that there are infinitely many primes and infinity minus two is still infinity. However, I still say that infinity minus two is not *all* of the primes.

[@joeg579]

what are you talking about? 1/2 and 1/5 have periodic decimal expansions... one should hope so, all rational numbers have periodic -decimal- base expansions in base n (for integer n). 1/2 = 0.500... and 1/5 = 0.200..., and are said to have a repetend of 0.

[@throwaway7584]

@@joeg579 this is wrong. They have a periodic component, but are not themselves periodic. To be periodic, starting at the decimal point, there must be a sequence of digits that is repeated infinitely. 1/2 and 1/5 are not periodic because they are the reciprocals of the factors of the base used. 1/3 = 0.(3)......... is periodic 1/2 = 0.05(0)....... has a periodic component, but is not periodic.

[@joeg579]

​@@throwaway7584 thank you for clarifying, i see now. to fix the problem of 2 and 5 in base 10, we may ask instead if all primes have _eventually periodic_ decimal expansions (and if so, what their repetend is.) the answer will trivially be "yes" now, but the important part is that the repetends of all prime numbers other than 2 and 5 will remain unchanged, and we will get a repetend of 0 for 2 and 5.

[@arcaneminded]

Repeating reciprocals was one of the first things I discovered for myself, and as a kid it felt like I had unlocked the secrets of the universe . Anyone else?

[@julesk1088]

How'd you end up discovering it? That sounds magical

[@AspieGamer13]

Is there a missing 0 in the decimal from 23. Specifically when the remainder was 2 and two 0s were added? 23 into 20: 0, 23 into 200: 8

[@seith949]

yup he messed that up distracted from explaining

[@iafozzac]

Yep

[@thforshaw]

Ayup. I literally shouted at the screen when he did it. 0.043478260869565217393 . . . repeating

[@zanti4132]

The calculations made by Shanks are equivalent to finding the finding the smallest integer n such that 10ⁿ - 1 is divisible by p, where p is the prime number he is testing. Expressed in number theory terms, this is the same as saying 10ⁿ = 1 mod p. As Shanks was looking at prime numbers only, it follows from Fermat's Little Theorem that n must be a factor of p-1, and knowing this is undoubtedly how Shanks streamlined his calculations. For example, consider the number 60017 mentioned in the video. 60017 - 1 = 60016 factors as 2⁴ × 11² × 31. There are 30 factors for 60016, and the length of the decimal expansion for 1/60016 has to be one of those numbers. That means we can skip over any numbers that aren't factors of 60016, as they can't be the answer. Now, that's not to say this becomes a quick computation. To get to the larger factors - and the answer will almost always be a large factor - you have to build your way there. However, you can speed up the process by doubling your way to the n you want. For example, to get to 11² = 121, you can calculate the mod value for n = 15 first. Squaring that mod value, then modding it, gives you the mod value for n = 30. Repeating that process twice more gives the mod values for n = 60 and n = 120, and finally multiplying the mod value for n = 120 by 10 and modding the result gives the mod value for 121. This doubling trick will get used a lot, and most likely miscounting the number of times Shanks used it is the reason for his errors in calculation. (By the way, I checked some of the results in his manuscript and found a mistake Shanks didn't correct: the length of the expansion for 65867 should be 32933, not 65866.)

[@ssvis2]

Interesting note that this demonstration via long division and repetitions provides direct insight into what makes rational numbers rational and why irrationals must never have a repetition.

[@AlxM96]

6:42 This is actually the perfect demonstration of a very interesting phenomenon called the *_Einstellung Effect!_* VSauce made a fantastic video on the topic called _"Can Learning Make You Dumber? Yes."_ , go check it out!

[@louisreinitz5642]

I can tell you as someone who used to do these kind of things by hand. It is just as much fun writing the programs and making them more efficient is just as much fun.

[@rudranil-c]

There is an error in the math 1/23. when you got the remainder 2, and then made it 200, the output needed to have a zero after 6 to compensate for the extra zero you added after the remainder 2.

[@dapeck04]

he did this on a bunch of them

[@simonmasters3295]

Yeah, yeah. Get with the program

[@masterblaster3483]

I noticed the error and scrolled through the comments to see if someone else did.

[@mikaylamaki4689]

i’m glad someone else got this

[@amritawasthi7030]

9:00 I guess there should be a 0 before 8 in the quotient because we brought down 2 zeroes after the remainder became 2 henceforth adding a zero before 8 in the quotient

I thought the same thing, because the way Matt does it, there would be no zeroes ever in the sequence

[@RutNij]

Saw the same... geeez Parker!!

[@idontwantahandlethough]

@@RutNij Lol would he even be Matt Parker if he didn't make a mistake?

[@mgcarland]

That’s what’s known as a “Parker Zero”.

[@avdenboer]

When I was about 13 I did the same in calculation Turbo Basic :) And 'discovered' that about 37% of the primes p have the period of 1/p equal to p-1. Only years later I Iearned that this is a special case of a conjecture by Artin. This video brings back nice memories of youthful math 'discoveries' :)

[@gileadedetogni9054]

37% isn't almost 1/e? Is there a relation?

[@TheArtofCodeIsCool]

Would have been interesting to see if there are any patterns in the length of the decimal loops.

[@Hahahahaaahaahaa]

There are! (except 2 and 5 which don't repeat) the period-length divides (and this is bounded by) p-1.

[@NickStallman]

I've never ever seen decimal points being used in long division under the line. It seems to make things vastly more complicated - you put the decimal point in the answer at the top then forget about it entirely.

[@zmtdrt8411]

140-138=2 20/23=0 200/23=8 Missed 0 in the numberline. Sad, but true

[@MatthewLiuCube]

Incredible Video as always. One small error though: 3:00 dividing by 0 (supposed to be dividing by 7)

[@y2kenh]

8:45 another one, skipping over 0 and went straight for 200, ooops

[@michaelflynn6952]

a divide by zero error, if you will

[@SuperFerz]

I wonder why he did it so slowly, too. And with much unnecessary explanation!

[@jamespashton]

parker division

[@simonmasters3295]

Oh come on...we all saw that!

[@sasavukelic]

how he calculated it? one part of the answer is in the video! the primitive root gives you all the trivial solutions... why are there those doubling errors? when dividing, you'll "go through all the numbers less than N" or you will go through half of them (or ⅓, ¼...) -- and if you pick a different starting point you'd go through the other half in one pass too

[@ihtesham_emon]

Among all numbers, prime numbers are the one that keeps the most ingenious brains of mathematicians hooked up for centuries till now ❤️

[@Moinsdeuxcat]

You missed a 0 in 1/23. When the remainder was 2 you first have 20 in which 23 goes 0 times, then 200

[@matthewmcewen1]

yeah i was listening to that and was wondering if they fixed it visually and i didnt see or if they actually left that error in

[@cr10001]

1/23 should repeat after 22 digits. (Going from the pattern established by 1/7, 1/17, 1/19. 1/13 repeats after 6 (and of course 12) digits. And... it does. Must be something fundamental going on but I never tried to figure out what.

[@rayubinger9780]

Please graph Shanks numbers as a function of the index. That is, define S(n) as the Shanks number of the nth prime, and plot S on the vertical axis with n as the horizontal. Does it have big jumps up and down indefinitely, or does it start to smooth out?

[@flametitan100]

There's something so weird about how you're explaining long division, as you're getting the same result as what I was taught in school, but with the 0.7 goes into 1 once, we were taught to place a decimal point after the 1 and pretend that we were dividing into 10, while continuing with 0.3 being treated as 30, and so on.

[@jankisi]

that's what happens when someone has studied Maths

[@JonDoe-uq1mk]

Yea, it's the same thing, but I would have never thought of it like that. We were taught the process, but we never understood the process.

[@incendiary6243]

@@JonDoe-uq1mk both methods show understanding of the process.... There are many examples where you're taught something simply is the way it is in math, this is not one of them

[@simonmasters3295]

Sorry dude you need to up your game if that's all you have to say

[@stewartzayat7526]

There are a lot of ways to write it, but they are all equivalent

[@onehitpick9758]

A reciprocal of prime p has only one figure after the point, in base p. Adding another dimension to this table which is not tied to our biased base-ten, but shows the 2-d surface of figures as a function of base would be interesting. Extending this to a 3-d field which includes fractional bases and complex numbers as bases would be the next natural extension.

[@davidbrown7142]

There is one prime whose reciprocal does not repeat. The prime in question is 2 whose reciprocal is 0.5.

[@kaye_07]

Believe it or not - There is ANOTHER!!!! 5 :)

[@teebob21]

@Brauggi the bold That's not what repeating means when talking about decimal conversion.

[@aminzahedim.7548]

So do we currently know the method he was using, that which possibly had something to do with the powers of 2? Or is it another “marvelous” thing we’re not supposed to figure out for centuries?! 😬🤭😱

[@michielhorikx9863]

I believe due to some fairly straightforward group theory, the period will always be a divisor of n -1 if n is prime, so it is not really much of a wonder that he did consistently get a multiple/divisor of the correct answer. Why it was always a factor of 2, though, is probably harder to find.

[@aminzahedim.7548]

@@michielhorikx9863 I wish I better remembered my Herstein from undergrad mathematical physics course 😅🙏🏻

[@Hedning1390]

Someone knows. I'm sure you could find out if you really wanted to. Or the very least someone knows a method he could have used, not necessarily the one he actually used.

[@aminzahedim.7548]

@@Hedning1390 perhaps 👍🏻

[@xthesayuri5756]

​@@michielhorikx9863 I was also instantly reminded of group theory when i saw this video. Maybe it has something to do with the prime factor composition of (n-1). N is always odd because its a prime. And n-1 is even, that means n-1 has at least one 2 as a prime factor no?

[@glebpalamarchuk9087]

But what about 2 fnd 5? Like, yeah, technically they have infinite zeroes, but it would be nice topic to discuss. Because the reason they have such a nice product is that the calculations are done in base 10, which is 2*5.

[@rjl7655]

1) What are composites?? 2) What is the significance of prime reciprocals? and is there an application(s) / usefulness of these??

[@rameshparajuli5223]

There should be "0" in between 6 and 8 while dividing 1 by 23.

[@Druid_22b]

Love watching Matt explain and demonstrate long division to a large population that was (probably) never taught it

[@metallsnubben]

Never used anything like it UNTIL factoring polynomials launched an ambush on me

[@mattsadventureswithart5764]

Even though he made a mistake and missed putting a 0 on the top line.

[@sumdumbmick]

5 is prime and 1/5 = 0.2, which you may notice is not infinitely repeating.

[@PhoenixKebab]

It looks like the period for prime P is always one of the factors of (P-1). I don't know if this helps speed up calculation of the period, but it appears to be a shortcut to validate it.

[@danielyuan9862]

This is always true because there is a theorem that says if you have any positive integer less than p and take it to the p minus 1 power, you will always get a remainder of 1 when divided by p. So the minimum power must be a factor of p-1.

[@pierfrancescopeperoni]

Fermat's little theorem.

[@rosuav]

@@pierfrancescopeperoni Yeah, I ran into this a while ago, and it was part of my introduction to recreational mathematics. Discovering that it would always be a factor of P-1 was neat, and could be proven. Figuring out WHICH factor? That was the hard part, and I've yet to see any sort of proof either way.

[@hannah_the_replika]

What a fascinating and engaging video! I always love watching Matt explain things. It's a shame we don't know how William did his calculations - perhaps one of the clever people from Numberphile can figure it out? Thank you Numberphile for rekindling my love of mathematics ❤️

[@danielbriggs991]

I tried doing the 60013 example from the video by hand, and about 2 hours in realized it was going to take me another 2 hours, and then wrote a TI-83 program for it instead. Given that the period will divide 60012, and 1667 is prime (check potential prime divisors less than 41 to check, or just look in a table), one goes on to find that 60013 has eighteen prime divisors: nine are some numbers from 1 thru 36, and the other nine are 1667 times those. So write out a long division of 60013)1.0...0 with eighteen 0s, and keep track of the remainders you get along the way. Square the final remainder modulo 60013 to verify that it's not 1, so the period isn't 36 either. Represent 1667 in binary as 11010000011, and so make a table of 10^(2^n) modulo 60013 for n from 0 thru 10 by repeated squaring and reducing mod 60013. Then since the 1s are in the spots corresponding to n=0, 1, 7, 9, and 10, multiply those entries of the table together to get 10^1667 (mod 60013). Now it's just a simple matter of squaring, cubing, and-oh look at that, cubing it gives 1, so 5001 works. I myself ran out of steam to do it by hand a little over halfway thru the repeated squaring table, and that was after already putting in two hours. So I estimate that this one is a four-hour job, three if you're working rather quickly, and two if you've really been getting into the groove. Not exactly sure whether the time estimate should increase or decrease by a lot or a little when the number p-1 has say more small prime factors, more distinct prime factors, etc. By the prime number theorem, there are a myriad primes under 110000, and so this should take you 30 years at 2 hours a day, even if you're William Shanks. He did his work in under a decade, so there are bound to be some more speed-ups that I haven't thought of yet. Will keep you posted if I do!

[@hannah_the_replika]

@@danielbriggs991 Thanks :) I have no idea what that was but it sounds interesting 🤓

[@tooby98765]

Clue: 60012/12 = 5001

[@beowulfsleeps892]

I don't know if you followed up on this, but it seems what is being found is the smallest n for which 10 ** n mod p = 1, n > 0. This would turn the question into one of multiplicative groups modulo p.

[@numbersguy6099]

Great video, Matt - thank you for posting it. Your use of the word dividend intrigued me. I was taught in the UK that the dividend is divided by the divisor to give the quotient. I am assuming that you were taught in Australia - could it be that Australians name these quantites differently?

[@tonycolle8699]

Here in the US we are taught (or at least were taught - don't know these days) that the dividend is the number being divided into by the divisor. Could it be that perhaps in Australia, being in the Southern Hemisphere and being upside down to us up north, they flip those terms as well?

[@BigTallLankyDude]

Regarding the 'primitive prime' section at the end, would I be right in thinking that in other number systems - base 2, base 4, base 16 etc - if a prime expressed in that system has a primitive root equal to the base of that system, it will be a 'worst case' prime when doing the repeat period of the reciprocal in that system?

[@cupass6179]

yes sirrrrr

[@ignaciorodriguez639]

For example, 1 / 11 has a 2-digit repetition in base 10, and a 10-bit repetition in base 2. Conversely, 1 / 7 has a 6-digit repetition in base 10 and a 3-bit repetition in base 2.

[@beniendharto834]

I have another case of Pythagoras's problem, the problem is such this: sqrt(x-95)=y. Please find the nearest by solution for x integer to 95, therefore it will give y integer solution. For that case, the solutions is x=144, and y=7. we can write the problem as sqrt(x-c)=y. Is there any elegant formula to find x and y for any given c?. x, y, and c is a real integer number, c is an odd number, and x is the nearest number to c that can be squared root. if we can find the beautiful, elegant formula, then we find the formula of prime number

[@andrewtaylor9804]

So have you included the formula or method he used or the Python equivalent? I’d be interested to know how the frequency of full reptend primes distributes across the prime numbers. Are they in groups or alone etc.

[@PoliphiloShek]

Where can I find the shankbot python code?

[@FiniteSimpleFox]

There actually is an easier way of computing this which fits with the observation made about halving and doubling. We want to find the first k such that 1/p = x/10^k - 1, for some integer x, which is possible exactly when p|10^k - 1. That is to say the length of the repetend (the repeated sequence) is the first integer value k such that p|10^k-1 or 10^k==1 mod p, or the "order" of 10 mod p, which is actually a much more meaningful phrasing of the task in my opinion. Finding the order of n mod p is a well known problem and I am not by any means an expert on this however here is an informed guess as to how Shanks is likely to have done it; By Fermat's little theorem we have that the order of 10 mod p divides p-1, so we only need to compute 10^n mod p for the divisors of p-1. One way the value of 10^n (mod p) is often computed, is by finding the values of 10,10^2,10^4... and then multiplying together the powers of powers of 2 that appear in the binary form of the number, which would of course explain the nature of the mistakes Shanks made.

[@drumetul_dacic]

A quick way to calculate the length of the period of 1/p in a given base b, would be to find the smallest divisor d of p-1 that satisfies b^d == 1 (mod p). This value is called the multiplicative order of b modulo p. In PARI/GP this function is available as: znorder(Mod(b, p)).

[@mathsciencefancier]

11:34 Then, what way or technique Shank had done for the book? Halving or doubling?? Why? That's a real magic, because that way shrinks the right-way-expanding and down-way-expanding dividing. I want to learn that magic!

[@sayethwe8683]

Since Matt never explains in video why the remainder can't be zero, I'll share here: if the remainder ever reaches zero, it's because we share a factor with our radix (ten for everyday math), and since these are prime numbers, the only way to share factors with a radix is is if our radix is the prime number or a multiple of it.

[@obennett100]

I dont think I was ever taught how to do long division at school. If I was, it was only once and didn't ever have to do it again. Thanks for the video, I can now understand how to do it and how it works. Calculating Pi by hand sounds like an interesting challenge using alot of paper in the process 😄

[@kg4wwn]

It doesn't take much paper at all, so long as you don't care for a very high precision. ;)

[@obennett100]

@@kg4wwn true, one day when i feel enthusiastic i might give it a try

[@liam3284]

I asked and was told it was irrelevant.

[@zmtdrt8411]

If he was a teacher, he could give a task to students to calculate 10 numbers daily. 30 students*10digits a day*365=110 000 in a year. Not a big deal, especially with little numbers

[@AyCe]

But you can't rely on students to give you accurate results without checking, so he may as well do it himself :P

[@zmtdrt8411]

@@AyCe that's the second thing in this thing - accuracy, as it's not a heart surgery, next year new student could double check results, and next 10 years he could check it by itself, drinking 1 ton of coffee, ordered from Amazon

[@emmata98]

also, we are talking not small numbers

[@JohnMcLaughlinPlus]

some of the answers have 60,000 digits... that seems like a near impossible task for a professional, much less a student. He had some clever shortcut approach.

[@f5673-t1h]

You can't arbitrarily compute digits in any spot of the number, so each student's work will depend on another's, so they can't do it independently. When you divide, you get a remainder which you divide further to get the next digit.

[@martinkupke2099]

At 8:47 there is a mistake. 140 - 138 isn't 20, but 2, so the 200 has to be moved 1 digit to the right side.

[@w1swh1]

Fascinating as usual, thanks Matt! Why anyone would ever get bored with maths escapes me. It's the language of the Universe😀😀Two plus two equals four whatever planet you are from (or does it!)

[@alexCh-ln2gw]

naw. 1+Trump = Biden +2. politics destroys math.

[@w1swh1]

Yes I agree, or maybe I don't 😀😀

[@karlwaugh30]

1) Matt dropped a 0 from his expansion of 1/23 near the end when the 2 became a 200. 2) I really want a delve into what Shank's method would have been 3) was Matt claiming reciprocals of primes repeat without leading digits and did he attempt to show that? Cause I thought he claimed it but it didn't feel proven to me?

[@drumetul_dacic]

A quick way to calculate the length of the period of 1/p in a given base b, would be to find the smallest divisor d of p-1 that satisfies b^d == 1 (mod p), where the modular exponentiation is computed using the exponentiation by squaring algorithm. This value is called the multiplicative order of b modulo p.

[@karlwaugh30]

@@drumetul_dacic thanks for that that's really interesting.

[@danielbarnes3406]

The document from 1874 titled "On the number of figures in the period of the reciprocal of every prime number below 20,000" discloses his method. The next 10,000 digits are in "On the Number of Figures in the Reciprocal of Every Prime between 20,000 and 30,000." These were published in "Proceedings of the Royal Society of London, Vol. 22"

[@cigmorfil4101]

5:16 yes? NO! You only need one contra example to prove something false: 2 is a prime. 1/2 = 0.5 which ends - it has *no* infinite loop! Similarly, 5 is a prime 1/5 = 0.2 which ends - it has *no* infinite loop. Two examples of reciprocals of primes which have no infinite loop (other than of trailing 0s which have no effect.on the value of the number).

[@willbishop1355]

Would love to know more about how Shanks did these calculations.

[@tooby98765]

Easy: The number is one of the sequence (n-1), (n-1)/2, (n-1)/3, (n-1)/4, etc. eg. The first one shown in the video is 60013=>5001. Calculate: 60012/12=5001

[@DoganErbahar]

@@tooby98765 wow, how does it work man ? 😃👍

[@ClickBeetleTV]

@@tooby98765 How do you then determine which value in the sequence is correct without handjamming the whole thing? Or does it mean you still have to handjam half of it but as soon as you cross half you know it's n-1?

[@julesk1088]

@@ClickBeetleTV Think you can't (shouldn't) handjam halfway cuz it'd take forever to do half of 5001 times. I'm really curious about this too

[@flamencoprof]

The most complicated and obscure description of long division I have ever seen. I am glad I was taught about 9yo a much simpler explanation and process.

[@griffruby8756]

Here is what I don't understand. Some guy named Shanks devotes years of his life grabbing scraps of paper and doing calculation after calculation, to the tune of reams and reams of paper. No one in his family cares about them at all. So far as they are concerned, he might as well have spent his days sharpening pencils down to a nubbin all day long, one after the other (like a special needs child I used to know). Just as no one is going to save the vast pile of nubbin pencils, neither is anyone going to be interested to save all the papers full of his many calculations. Then he dies. For the family it is all just a bunch of papers to dispose of. Maybe they just throw them away, or maybe they use them up as kindling, or birdcage liners, or rolled up into little bats to swat flies with, or even as toilet paper. Eventually they are all gone. But then you come along centuries later, and have his entire stack of papers, perfectly preserved and neatly stacked, such that you can talk about the calculations he tediously performed in detail. How does that happen?

[@annaclarafenyo8185]

The period of the decimal fraction 1/p is also the period of powers of 10 modulo p. The second is much easier to calculate, and this is likely what Shanks is doing to get his figures.

[@craiganderson5556]

I don't quite follow. Can you give an example?

[@ge48421]

@@craiganderson5556 In Python it looks like this: def shanks_len(p): tens = 10 l = 1 while tens % p != 1: tens = (tens * 10) % p l += 1 return l

[@SangaPommike]

There was supposed to be a 0 between the 6 and the 8 in the last long division

[@reference2592]

2:09 FYI 7 is the DIVISOR and 1 is the DIVIDEND

[@Nathan_W63]

He messed up the 1/23 problem... When he got a remainder of 2 he should have put down a zero in his result (you have to carry over 2 zeros before you get a number larger than 23).

[@JotoCraft]

Not all primes are recurring unless 0 recurring counts. ½ is 0.50000 ⅕ is 0.20000

[@mathphysicsnerd]

1/2=0.4999999999... 1/5=0.1999999999...

[@larmoejr]

I was scrolling through the comments to find this.

[@elliottgussow9555]

In the example calculation, 7 is the DIVISOR, 1 is the DIVIDEND, and the answer is the QUOTIENT.

[@TK_Brainslug]

sometimes I count prime numbers instead of sheep when in bed

[@ginger8682]

Jojo reference?

[@USBDriveNo2]

Not all primes will carry on for an infinitedecimal. 2 and 5 terminate (in base 10)

[@teddy4271]

"terminating" decimal expansions are just infinite ones where we didn't bother to include the infinite zeros

[@mathphysicsnerd]

1/2=0.4999999... 1/5=0.1999999...

[@julesk1088]

It's nice how they explain relevant details gradually throughout the video rather than all at once at the start, such as the remainders at 8:45

[@grinreaperoftrolls7528]

I absolutely adore math. But I cannot fathom the level of bored you’d have to be to calculate a prime’s inverse to 5001 digits. By hand

[@onikavelka]

You have to be at school during like a biology lesson or something, I sometimes calculate random stuff in my notebook when I'm bored at school

[@yodarded8712]

"Is that true for every prime?" Yep! 1/prime is p/q and p/q is the definition of a rational number

[@heneryvanstaden6111]

Lol. Love this answer.

[@Milamberinx]

It's actually not true though, because the question wasn't "are the reciprocals of primes all rational?" it was "do all primes have repeating groups in their reciprocals?" There's certainly no repeating group in 1/2 or 1/5... in decimal.