Caboose Numbers - Numberphile
HTML-код
- Опубликовано: 27 сен 2024
- Matt Parker explores caboose numbers, also known as Euler's Lucky Numbers. Part 2 is here: • Tree-house Numbers - N... --- More links & stuff in full description below ↓↓↓
Get your signed copy of Love Triangle at mathsgear.co.u...
Love Triangle on Amazon US (unsigned): amzn.to/3XoRlf4
And on Amazon UK (unsigned): amzn.to/3xh9Siw
More Matt on Numberphile: • Matt Parker (standupma...
Matt's own channel is Stand-up Maths: / standupmaths
Euler's Lucky Numbers on the OEIS: oeis.org/A014556
Patreon: / numberphile
Numberphile is supported by Jane Street. Learn more about them (and exciting career opportunities) at: bit.ly/numberp...
We're also supported by the Simons Laufer Mathematical Sciences Institute (formerly MSRI): bit.ly/MSRINumb...
Our thanks also to the Simons Foundation: www.simonsfoun...
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Videos by Brady Haran
Thanks to fact checkers from The Numberphile Society, including Debbie Chakour and CJ Smith.
Numberphile T-Shirts and Merch: teespring.com/...
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9
Part 2 is here: ruclips.net/video/mw4DM1952KI/видео.html
Um the title looks off...
2 hours before uploaded
With the exception of 3, all of these numbers are equal to 5 mod 6.
IIRC one of my lecturers at Cambridge (approx 40 years ago) proved there were no more Caboose after 41.
I haven't seen any reference to this, but a few other students knew at the time he was famous for this.
Just wanted to point out that at 2:37 we could prove that any n of the form 41k+1 also breaks the process.
Suppose n ≡ p (mod 41). If we suppose that n^2 - n + 41 is a multiple of 41, then we can write
p^2 - p = p(p-1) ≡ 0. Since 41 is prime, we can conclude that either p≡0 or p≡1 (mod 41) (yes I know that we cannot do that with composite numbers).
This does not address the possibility that n^2 - n + 41 could be composite but not divisible by 41, but I think it should be pointed for Brady's question.
Edit: I just realized that all n that satisfy n = k^2 + 41, where k is a nonnegative integer, also break the pattern.
101 can be the first and only Parker Caboose Number.
Underrated
@@daniel_77. It's the top rated comment. How is that underrated? It couldn't be more rated.
The Parkerboose number, if you will.
@@QuantumHistorian I mean when I first saw it. Probably some hours later it will be the top comment. Can you understand?
@@daniel_77. No, I don't understand, it was top comment when you posted your comment. It's likely to stay there. Why some people have to (implicitly) complain that others don't like something enough rather than just saying they like that thing is beyond me.
5:14 Matt can join a long line of mathematicians who when studying an interesting piece of maths discover that the work has already been done extensively by Euler
Euler really is the Simpsons of the maths world 😂
You got Eulered! I'm sure even Derek has been Eulered.
@@htspencer9084 Don't forget Gauss!
You know what they say, things in math are usually named after the second person to discover them, or else they would all be called "Euler's" something.
An hour In the library saves 10 in the lab.
This would be a good moment for a sequel to "people online made my code 40 million % more efficient".
The easiest optimization for me would be: No need to check even numbers for c: n squared minus n will always give an even number. 50 % quicker: done.
@@martinmarhold1798 Surely that would be 100% quicker...
Precomoute a map with all the prime us to the the highest number. Certainly faster than isPrime
This was my thought as well, if you had a list of the first m primes, that would probably help significantly @@jonbaltz8559
Not just evens. Caboose numbers are a subset of the primes since every other number would fail for the n=0 and n=1 cases.
The dog in the background is thinking: "this Python code is gonna take ages - time for a nap"
Pup needs really big keys on a a waterproof keyboard to code python.
from weenie_dog import nap
nap(600)
Obviously this code can be improved by 41 billion percent
Let's start with the fact that checking even numbers as cabooses is pointless! ... and the caboose has to a prime number if we're anticipating 100% prime results, because "n=0,1" leaves only "c"
Even if we dismiss "n=0,1" as trivial boundary conditions, then we only have to check "c" that are a prime number minus two ("n=2" means the answer is "c+2")
I think the dog is Sky.
"Honorary, near caboose" - definitely what people will call a near miss found by Matt
Lemme get a look at that Parker Caboose 😏
Why do you call Euler “they”?
@@SantiagoArizti Matt uses neutral pronouns for mostly everyone.
@@SantiagoArizti Euler used they/them pronouns
@@B-fq7ff this is true
Using red pen to mark correct while the green pen is right next to it..... Such a Parker move 👏.
I was thinking the same thing! Who draws red check marks?!
@@backwashjoe7864 Teachers
That's Japan's way of doing things.
@@backwashjoe7864: At least in Finland teachers use red check marks if the answer is wrong. (The check mark looks like letter 'v' and 'wrong' is 'väärin' in Finnish.)
10^n + 37 is prime for an inordinate number of integers n. My favorite prime is 10^39+37 which is a one followed by 37 zeros and then the number 37. If found this incidentally in the context of some research I was doing.
Do you remember roughly how many it works for?
Is "inordinate" thousands, millions, googological?
@@alansmithee419 hippopotamical?
@@alansmithee419 since primes don't end, i assume it would go on forever but "inordinate" may just be used to say "a lot of n's but not all of them"
Somwhat percentage of them?
@@alansmithee419 Here's a little python program you can play with:
from sympy import *
for n in range(100):
x = 10**n+37
if isprime(x):
print(n)
Up to 40 I got 1, 2, 4, 6, 8, 13, 15, 39.
Checking if a Boolean is "== True" is certainly a Parker way of programming.
Only benefit is that you are also verifying it is a Boolean which of course wouldn’t be a problem in a real language 😂
@@BaptistPianoYou are not though. 1==True is True in Python.
@@MichalMarsalek wait really??? I haven’t used python in a long time but kinda assumed they wouldn’t do coercion since they don’t have a threequals. Well learn something every day
I spotted that too. Much as I enjoy the ongoing joke, Matt should really learn to write not-terrible python code.
@@bobthegiraffemonkey Such a thing does not exist. Python code is terrible by definition.
Hi. Train enthusiast here. 2 issues with the animation:
1. Your boxcars shouldn't have 8 axles. Probably 4 axles is plenty for the sort of train you're drawing.
2. Wheels on a steam locomotive have rods connecting them to the pistons, but wheels on the cars don't.
Okay, I'll sit down now.
Quite the parker train!
The wheels also don't turn fast enough compared to the landscape flying by....
This train predates the introduction of bogeys .. so two axles for the boxcars is probably sufficient.
I was gonna complain too, but you Eulered me on it.
you've been training for this
Sounds cool. Also, the train seems to be a diesel because there is no funnel at the front. Unless the funnel travels back through into the cabin but that would be a very unconventional arrangement, especially considering the steam would have to go to the cylinders and then back.
On the note of the rods, it could have internally mounted vertical pistons (like on the LBSCR E2). On the whole though, it probably is a diesel locomotive. It might even be a really powerful shunter based on the size but I think, regardless of the power, it would probably shear the crank pins on the front axle with all of that straining.
Nice to hear from a fellow train enthusiast.
Nice Video.
I ran some code for my self that confirmed that there are no other Caboose Numbers up to 100 million.
Which if you think about it makes sense since the gaps between primes do not get smaller as the primes become bigger 😢 sadly
A356751. Positive integers m such that x^2 - x + m contains more than m/2 prime numbers for x = 1, 2, ..., m : 3, 5, 7, 11, 17, 41, 47, 59, 67, 101, 107, 161, 221, 227, 347, 377. No more is known, and it is conjectured that 377 is the largest one.
any caboose number has to be prime. if it's a composite number, say a*b, then a^2-a+ab = a * ( a - 1 + b ) which is 2 factors greater than 1 (since a and b are greater than 1).
more intuitively: C has to be prime since for N = 0 and N = 1, N^2 - N + C will always equal C
It is also true that a caboose number must be a smaller prime part of a twin prime couple.
This is because when substituting n=2 there will be added 2²-2 = 2 to the original prime, and we get the bigger twin prime. (101 is a twin prime with 103, and a 6 apart cousin prime with 107)
Caboose numbers are possible because n² -n is always even. And we can find cousin primes (that are an even number apart). And maybe this is why we can't find bigger ones. For larger primes it gets increasingly difficult to find other cousin primes always 2, 6, 12, 20... apart from a caboose prime.
damn. ab is my favourite composite number by far.
@@LW-zb8bf aren't cousin primes just all pairs of primes that don't include 2?
Except for the one Matt forgot, which is 2. Because 0²-0+2 = 1²-1+2=2 is prime, and you don't have to worry about 2²-2+2 = 4, because 2 is not less than 2.
Also, I guess 0 is vacuously a caboose number, because there are no natural numbers less than 0, so all none of them result in a prime.
Two small observations that Matt didn’t outright say.
A caboose number has to itself be prime, because the caboose outputs itself for n=0 and 1.
And to generalize the logic about n=42, any n greater than the caboose by a square number would create a difference of squares, and therefore output a non-prime.
Not only prime, but (with the exception of c=2), the lower of a pair of twin primes since n=2 gives c+2.
Also n^2 - n + c is the same as n*(n-1) + c so of course it will not be prime for c or c + 1 because either of those means the left side of the + is divisible by c and so is the right side. So the whole thing is divisible by c.
One way to speed up the program. n^2 - n + c is not prime for (nearly all) number which are not coprime with c. So check c for primality first and don't try to calculate the rest if c is not prime. in addition, (n+1)^2 - (n + 1) + c - (n^2 - n + c) = 2n. So, rather than recalculating the whole formula, just add 2n on to the nth result to get the (n+1)th.
Also, when asking, "when does this fail?" for the original formula, my immediate thought was that the answer was 42, of course.
Caching the list of primes up to the largest _n_ that will be tested would also probably help, a set membership check will be faster than a call to some library. Would be even faster to have a binary array that's _n_ long whose k'th entry is whether _k_ is prime or not. You're quickly going to be limited by the speed of python's for loop after that.
You might get a +20x speed boost by simply not using python.
You could also do step sizes of 2, since even c's will obviously result in numbers divisible by 2.
@@QuantumHistorian After reading some useful comments about Caboose numbers, I got the following ideas:
caboose no.s are prime
if x=n^2-n+c is the nth caboose no, add 2n to x to get the next caboose no.
use already generated lists of primes
.
So I thought I might try to write an efficient python code to find the next Caboose number. But then I saw the follow-up to this video (named Tree-house numbers) and realized there are no more Caboose numbers after this or no more Treehouse numbers after 163, because they are both related to the Heegner numbers which there are no more of after 163 (you can see the follow up video for more info)
@@QuantumHistorian I did something like this. I just cached if an odd number is prime or not as the index into an array. So to look it up I just divide the number in half and return a bool if its prime or not.
My brain hurts trying to unravel
"for i in [i for i in range(3,n)]"
It’s the same as doing for i in range(3,n) aha
@@morethejamesx39 If only that were true.
It's actually a less efficient version of list(range(3,n)) - i.e. it does the unnecessary work of building a list out of the range before iterating over it.
Worse, making a list out of j² - j + i for each j up to i is also unnecessary. Matt does use len(values) in later calculations, but len(values) has to be the number of integers generated by range(1,i), which is simply i-1.
@@c.jones-yt Yeah sorry I meant it will run the same as*
He did warn us it was awful.
He wasn't kidding
Heck yeah, love me some Parker maths
Love that there are already more efficient code structures being discussed, I look forward to the follow-up "numberphile viewer caused a maths breakthrough" video
Where I live in Northwest Oregon, our two area codes are 503 and 971, both of which I already knew were primes, but I didn't know they were both primes in 41's sequence! Even prouder :)
I feel like there should definitely be an "easy" upper bound on this. If a number C is Caboose that means that there are C primes between C and C^2 - 2C (the values of n=1 and n=c-1). Now use any bound you like on the amount of prime numbers within a region, and you have your easy bound on the largest possible C. Then use a computer to hopefully check the remaining small C.
It's been proven that 41 is the last caboose number. Rabinowitz showed that c is a caboose number if and only if 4c-1 is a Heegner number, and the Stark-Heegner theorem proves that the largest Heegner number is 163. See the Wikipedia page for "Heegner number" for more information about all these points.
Or see the second part of this video - ruclips.net/video/mw4DM1952KI/видео.html
Or sequence A014556 of the OEIS, which every mathematician should consult zeroth before first writing some Python.
@@landsgevaer A014556 doesn't state it's proven to be limited, but it links to A003173, where it is stated that Heenger proved that list complete, implying Caboose/Lucky numbers are limited to this set.
What c=3, 5, 11, 17, 41 (and also 1 and 2 and no other numbers with 4c-1 square-free) have in common is that extending Q by a root of the polynomial x^2 - x + c gives a quadratic number field of class number 1. The near-examples at 7:56 give number fields of class number 2, except for x^2 - x + 7 whose discriminant -27 is not square-free (in this case Q(sqrt(-27)) = Q(sqrt(-3)) has class number 1).
See also Goudsmit S.A. (1967) Unusual Prime Number Sequences, Nature Vol. 214, 1164.
I was totally going to say that about the discriminating fields of something, something number stuff
your channel is one of the best discoveries i’ve made online!
It's worth considering negative numbers as well. For instance, -109 has about 76% primes up through 108, and -73 has 75% primes up through 72.
7:07 the snoozing dog is so cute
"41" a clasic case of a parker anwser to life, the universe and everything
For quadratics, there are actually quite a few that spit out some number of primes.
n^2 - 61n + 971 gives you primes from 0-71
n^2 - 79n + 1601 gives primes from 0-80
Matt gives of an "every man" mathematician vibe and got saddled with a legacy of not quite being right which helps make this all approachable. But that instant spot of difference of two squares to explain the non prime shows how hip with the numbers he really is. He's always so quick to call himself a recreational mathematician but you sit in the soup long enough and you start to look like Stu.
The legacy of the Parker square :D
"Time... line?
Ugh, time isn't made of lines! It is made out of circles. That is why clocks are round!"
-Caboose
I had to scroll too far to find a single RvB reference
Matt wants to draw a checkmark in a different colour, reaches for the place with 2 black, 1 red and 1 green and picks… red. The obvious colour for checkmarks.
"I consider 5 the first prime number" is incredible
This video is very important, I love the moral of that story. More than ever we need a way to show smart people how easy we can trick ourselves by believing patterns that might not be there. I get into theological and strange conversations sometimes where people tell me about patterns they see and how their spiritual, and I think of either Daniel dennett or Robert soapulski who wrote about seeing patterns where there might not be one could have been an evolutionary trait that perhaps helped us to survive on the Savannah.
I have similar conversations with people about patterns and their meanings( or lack of such). I often will show that, if one tries hard enough, one can find patterns in almost any collection of occurrences.
I love the spurious correlations website for illustrating how often things can be correlated just by happenstance
"Euler came up with this" can describe half of mathematics
this video taught me one important thing, and that is that caboose is not an onomatopoeic way of saying "butt"
*Red vs. Blue has entered the chat*
Caboose numbers will always be prime, because if you plug in 1 for n, they will cancel out and leave the caboose number.
the reason is that being 42 the answer to the ultimate question, that makes 41 the most human number, just in the limit of knowing everything
Numberphile, the only RUclips channel with paper change music.
you'll notice, as shown in the example for c=41, that any n=c+x^2 is also going to fail, because n^2-n+c will also always be a difference of two squares, (c+x^2)^2 and x^2, resulting in factors of c+x^2-x and c+x^2+x
Euler's Lucky Numbers are soooo cool! I think it's fortunate that they never intersect with the other sequence of lucky numbers
Or is it unfortunate that no numbers are double lucky :(
@@fluffyllama1505 3 is double lucky
When Brady said 42, I immediately thought it had to be composite. An easy way to see this is 42²-42+41=42²-1=(42-1)(42+1)=41•43. In general, if your number n is a perfect square larger than 41, you will necessarily get a difference of squares which will be composite. This is another set of numbers which breaks the pattern aside from the multiples of 41.
3:11
"again, just off.. the top of my headdd..."
*camera zooms in on phone*
I love how matt is just casually inventing new names for maths
I love the way Matt says "one".
wähn
There are some important between mathematics and science, but I sometimes hear people (especially other students when I was in college) imply that mathematics _is_ a science. The fact that mathematicians "can't trust patterns" is one of these differences, so I'm happy to see that it's the lesson of a video.
Caboose numbers must all be prime because of the cases where n = 1
1^2-1+c 1^2 is 1
1-1+c 1-1 is 0
0+c Adding 0 to a number will keep the same number
c If c is prime, the result would be prime
Matt is just begging to have 101 declared the Parker Caboose, isn't he?
The times when it breaks is when N = C + k^2. I noticed when I saw where it generated non primes on the scrolling list. This holds true until 82, or Cx2. After that, it broke at 82+1, 82+3, and 82+6. I did check when n = 82+10, but it was not prime. I was just playing in excel and comparing to the first 1000 primes. I did try using 5 and 7 as well for values of C and the statement holds true for values below 10 and 14 respectively. After the point N = 2C, the values of N where it the formula generates non primes does not follow the same pattern of breaking only when N = C + k^2. It includes more, but I can't discern the pattern at a glance.
I first came across the word "caboose" and had to look it up its meaning, in the lyrics of Bob Dylan's 1963 song "Only a Pawn in their Game". So I've known the word for over sixty years and never had an occasion to use it, until today.
1st step is to toss the sequence into the oeis
Good ol Matt. You can always count on him for a pretty close result.
Each set is only the difference of n^2-n, the gaps between primes increases for larger values of c, so yeah you're unlikely to match the first few numbers of the set to primes, so it's no surprise (you just need to find an offset where shifting by 0,2,6,12,20,30,42,56... is another prime, it's tricky on the low end, and gets more difficult with a larger offset)
I like how the “paper change” card is up probably as long as it takes to actually change the paper.
This also means you can do the inverse function for n^2 - n + 41: 0.5 + √(n - 40.75). If the function outputs an integer below 41, you know the input is prime. (This also works for other integers that are excluded by that 41, 42, 45, 50, 57, ... sequence.)
The caboose function doesn't generate all primes until n=41, it only generates 40 of them. While it gives a handful of numbers a shortcut to check primeness, the sqrt for the evaluation is likely to be more expensive than any more conventional test.
Not to downplay the interesting math(s), the alluring Matt, and the interrogative Brady, but my second favorite part of the video is the framed Parker Square on the floor.
But the best thing hands down is Sky asleep on the couch.
"I consider 5 the first prime number." - MP
You say even numbers never produce cabooses, but 2 works. Granted, it's trivial, but it still works.
2:29 Those great "Brady questions" are always amazing :D
I love numbers, and etymology: "caboose" mid 18th century: from Dutch kombuis. And "kombuis" is a ship's kitchen.
A couple of simple improvements: a. Only check if c is prime. b. Do not calculate %, if one non-prime is found then skip it. This will get though the numbers much faster. But it is likely that no more Caboose numbers will be found because the probability of all numbers generating a prime gets smaller and smaller.
I love how, given the option of red or green, Matt chose red for correct.
#ParkerTick
Sharpie pens used to have the phrase “not for letter writing” because they’re not really designed for use on paper. Now the manufacturer no longer cares so long as they keep selling…
I know Matt wasn't in the thumbnail earlier and now he is, funny
Euler really lacked imagination. That was Euler’s problem.
It seems trivial to use the prime number theorem to find the probability that we found the largest caboose and Parker caboose number at 99% confidence.
I like how Matt Parker is is this genius mathematician and he still writes "If X == True" as an If Condition lol
101 at 68 percent is an ideal candidate for dark energy.
I don't know about anybody else, but I think "Euler's Caboose" has a nice ring to it.
Love the little background sound of the caboose
I would also explore more general forms as A*n^2 + B*n +C
Ironically, most railroads no longer use cabooses. They have "End of Train Devices" that attach to the air hose on the back of the last car and provide air-pressure readings via radio link to the head locomotive.
Matt says every mathematician immediate starts coding ugly Python. I thought he was gonna say every mathematician immediately consults the OEIS.
That lists these as finite. They are related to Heegner numbers, which were proved to be exhaustively enumerated.
Sequence A014556, if interested (YT removes the link).
"Patterns in Prime" might make a good movie title!
Brady's house must look like the Library of Alexandria by now, there are so many papyrus scrolls
68% - there's a joke about almost being 69 and being "near caboose" but this is a serious channel.
By the way, yes, c does always need to be prime. For n=0 and n=1 the result is just c
.75*(X^2)+(1.5*X)+23 = mostly prime numbers when X is an even number. This formula generates Eisenstein prime numbers.
Lovely Conjunction Junction vibe
Omg, I actually did the same calculation like ~2 years ago and checked until a few million or so and was so interested in whether someone could actuallly prove, that 41 is the biggest caboose number (cool name btw). Can't wait to watch part 2!
I put Numberphile on to comfort me/cheer me up. Quality and fun videos ✌🏼 and informative for lay people
For fun I decided to write some similar rust code to run it multi-threaded on my decently powerful but couple year old PC. I've checked up to 400 million so far without finding any other caboose numbers. Not a proof, but fun to play around with as a fairly straightforward problem in a programming language I don't use very much.
Just compute n^2-n for all integers into memory array/vector THEN add c and check for prime in a table.
Can we get a doggo cam sitting in the corner for math reasons
I would say if you really want to find them, forget about seeing how may there are, just stop when you find a single number that isn't prime and go to the next possibility.
Ideally, start with a list of primes, or at least something that will significantly restrict the numbers, like 6n-1 or 6n+1.
1, 2, and 3 also work as caboose numbers!
6:36 Caboose numbers would all need to be prime, for the cases of n=0 and n=1, which both leave only c to be a prime result.
(n^2) - (n) + (41) = guaranteed prime? That's insane and this is why I love this channel. I'm gonna plug in some numbers just for fun. Have a great day everyone!
Another way to see why c = n never works is that -n + n = 0, so you're just left with n^2, which is never going to be prime (will always be divisible by at least n)..
Also 42^2-42+41=42(42-1)+41=42*41+41…you could see it was composite (multiple of 41) from a mile away!
It's easy to see that this doesn't work for n=c+1, since you can rewrite n^2-n as n(n-1). If n=c+1, the equation rewrites to (c+1)(c+1-1)+c = (c+1)*c + c = (c+2)*c. Which you saw as factors 41 and 43 in the end result.
I have solved maths once and for all by inventing a function that outputs every prime number. I call it Prime_Number(). So, for example, Prime_Number(1) returns 2. Prime_Number(2) returns 3. And so on. You might ask: but how does the function work? OH HEY LOOK OVER THERE
That code clearly needs to be optimized... Seems a clear example of Parker code
"for i in [i for i in range(3, n)]"
I've seen this one before, it's called a Parker For Loop
Caboose numbers will never beat the Parker Square 😂
Has a green pen. Picks up red pen for a tick. 😳
I tried with slightly more optimized code to check further. Matt checked up to a quarter of a million. I checked up to a hundred million (so far). Still no Caboose number greater than 41.
Caboose numbers have to be prime, so I used a list of primes to check only those.
(And now, I've just checked on oeis, and the list has been proven to be complete. 41 is the largest Caboose number.)
101 must be considered a Parker Caboose number!
I wonder if there's a way to prove that 41 is the biggest caboose number
What always fascinates me with these is we apparently don't have the mathematical tools to prove or disprove questions like "is there another caboose number" beyond literally just checking numbers
"I consider 5 the first prime number." All primes greater than or equal to 5 will be the Parker Primes.
2:23 - "You can't trust a pattern just because it works for a long time"
Just earlier today, I learned of the Pólya conjecture, which was disproven with a counter-example that breaks it. Said example was estimated to be 1.875E361.
There are times when I think Matt should write a book.