Player (80)
Joined: 8/5/2007
Posts: 865
Adding on to OmnipotentEntity's comment, we can also look at the stability of these two fixed points. Begin by writing the expression as an iterated sequence: x_(n+1) = 2/(3-x_n) Now choose some value close to 1 or 2. I'll start with 1: x_n = 1 + δ This gives us x_(n+1) = 2/(2-δ) Performing a Taylor expansion or other approximation will quickly yield x_(n+1) ≈ 1 + δ/2 which proves that if we start with a number close to x=1, the series will converge to x=1. Now play the same game with numbers near x=2: x_n = 2 + δ Now we get x_(n+1) = 2/(1-δ) And the Taylor expansion for this will give us x_(n+1) ≈ 2 + 2δ which is farther from 2 than x_n, proving that x=2 is unstable. There is no reason you can't write either 1 = 2/(3-2/(3-... or 2 = 2/(3-2/(3-..., but in some sense, the "true" value is 1 because the slightest error will drive the sequence away from the value of 2.
Editor, Expert player (2080)
Joined: 6/15/2005
Posts: 3284
Warp wrote:
We can do so forever, so: 1 = 2/(3-(2/(3-(2/(3-(...)))))) ... We can do so forever, so: 2 = 2/(3-(2/(3-(2/(3-(...)))))) As you can see, both expansions are the same, and therefore: 1 = 2/(3-(2/(3-(2/(3-(...)))))) = 2
You can use the same argument to claim that 1=sqrt(sqrt(sqrt(...)))=0. (Didn't we just go over that a few weeks ago?) This is why things like 2/(3-(2/(3-(2/(3-(...)))))) and sqrt(sqrt(sqrt(...))) are not well-defined. One way to make it well-defined would be to define it as an iterative sequence depending on the starting value C, like: a0=C ai=2/(3-ai-1) for i≥1. In this case, this is a fixed-point iteration problem. Based on the following image: almost all starting values of C converge to 1. Only C=2 converges to 2, and a countable set of numbers (in the interval 2<C≤3) fail because the sequence hits 3 at some point, which makes it undefined.
Tub
Joined: 6/25/2005
Posts: 1377
The "solution" to last week's Riddler classic infuriates me. So is there a minimum length, where every number can be turned into an equation or not? This is not a computational problem. Even showing 100% solvability for n says nothing about n+1. And you cannot compute all n. I tried to find a strategy to turn any sufficiently long string into 0, turning the equation into (stuff) * 0 = (stuff) * 0 * (stuff), but with mere addition and substraction of single digits, that's not always possible up to n = 10.000 (I aborted the search there). I found no way to generalize a more complicated strategy. Did any of you have more luck?
m00
Editor, Skilled player (1348)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
I agree with Tub this was a bad problem. Also, The Riddler claims 4870798 is the only 7 digit number with no equations. Isn't (4/8)^(-7) + 0 = (7+9)*8 a solution, though?
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Editor, Skilled player (1348)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Tub wrote:
The "solution" to last week's Riddler classic infuriates me. So is there a minimum length, where every number can be turned into an equation or not? This is not a computational problem. Even showing 100% solvability for n says nothing about n+1. And you cannot compute all n. I tried to find a strategy to turn any sufficiently long string into 0, turning the equation into (stuff) * 0 = (stuff) * 0 * (stuff), but with mere addition and substraction of single digits, that's not always possible up to n = 10.000 (I aborted the search there). I found no way to generalize a more complicated strategy. Did any of you have more luck?
I just realized that if you proof it always works for N, then it always works for every sequence with 2N digits or more. We can split a sequence with 2N digits in 2 sequences with N digits. Each sequence with N digits starts with 'something' = 'something'. There might be more = symbols, but it doesn't mater. Just tweak it to ('something' - 'something') = ('something' - 'something'), and you have 0 = 0. For sequences with more than 2N digits, just multiply the remain numbers by the 0 you've got. Since we know that every sequence with 7 digits has a valid equality, we can say for sure that for every sequence with N ≥ 14 digits there is a valid equality. Edit: I also tried to find a way to sum up to 0 as you mentioned, but with only sum and subtraction it wouldn't work for any n. If the first digit is odd and the others are even, for instance, the sum would always be odd. Edit2: I'm pretty sure if you test sums and subtracts of every sequence of digits contained by a sequence of size n, (that is, not necessarily summing or subtracting all of the digits) you will find an n that always gives you 0 somewhere.
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Tub
Joined: 6/25/2005
Posts: 1377
BrunoVisnadi wrote:
Since we know that every sequence with 7 digits has a valid equality, we can say for sure that for every sequence with N ≥ 14 digits there is a valid equality.
That is true. I can sleep better now. It's not a pretty proof if it involves a 10-million-element lookup table, but it's a proof. Now that I have a bit more time, let me document my failed approaches anyway. Try to prove that every sequence with at least N digits contains a subsequence that evaluates to 0 when you add the right amount of ()+-*/^, but not =. If you can prove that, then every sequence with 2N digits can be turned into an equation 0 = 0. Trivially, if there's a 0 in the sequence, you're done. If there's a repetition (11 or 123123), you're done (1-1 or 123-123). If two neighbouring subsequences are permutations of each other (123321), you're done (1+2+3)-(3+2+1). I've tested the latter by recursively generating a counter-example; as said I've found a sequence with 10.000 digits that was free of successive permutations. Fun fact: you can generate such a sequence with only four different digits. Using this approach, I can answer the riddler's question in all bases up to 4 (yes, given a sufficient length, you can always make a true equation), but not for base 5 and above. Another approach I tried involves finding a subset that satisfies the Partition Problem. The wikipedia example is S = {3,1,1,2,2,1} => S1 = {1,1,2,1} and S2 = {3,2} Prefix everything from S1 with + and everything from S2 with -, then 311221 can be turned into -3+1+1+2-2+1 = 0 But not every sequence can be partitioned in such a way, no matter the length (like you mentioned, if the sum of all digits is odd). Fortunately we only require a subsequence to be partitionable, but I wouldn't know how to prove that, if it is true. Going away from 0, you can also try to prove that every sequence of length >= n begins with a subsequence that can evaluate to 1. Then every sequence >= 2n can be turned into 1^(stuff) = 1^(stuff) I had no luck with that, either.
m00
Editor, Expert player (2080)
Joined: 6/15/2005
Posts: 3284
BrunoVisnadi wrote:
I agree with Tub this was a bad problem.
Well, it isn't a bad problem, just a mainly (but not completely) computational one. I thought it was obvious that if all strings of length n work, then all strings of length 2n and greater work as well, since any string that represents an equation can be trivially modified to represent 0. It's easier for a string to represent 0 than it is to represent an equation, so I believe the lookup table isn't going to be as big as 10 million or so. Also remember that there is no guarantee of quality for Riddler questions, or even solutions! The Riddler isn't some mathematical genius. I accepted that a while ago and I feel better for doing that.
BrunoVisnadi wrote:
Also, The Riddler claims 4870798 is the only 7 digit number with no equations. Isn't (4/8)^(-7) + 0 = (7+9)*8 a solution, though?
Oh, now that you mentioned it, I don't think this solution considers negation of a single number to be a valid operation. Subtraction of two numbers, yes, but negation of one number, no. That's just how the Riddler rolls.
Editor, Skilled player (1348)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
BrunoVisnadi wrote:
Also, The Riddler claims 4870798 is the only 7 digit number with no equations. Isn't (4/8)^(-7) + 0 = (7+9)*8 a solution, though?
Oh, now that you mentioned it, I don't think this solution considers negation of a single number to be a valid operation. Subtraction of two numbers, yes, but negation of one number, no.
Some people posted in the comments this other solution: 4*(8-7)*(0-7+9)=8. I believe this one is valid, thus, we can in fact be sure every 14 digit long sequence has a equation.
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Editor, Expert player (2080)
Joined: 6/15/2005
Posts: 3284
I didn't even know there were comments on the blog all this time and just thought nobody bothered to comment. Sites should always auto-expand their comment sections. Anyway, I found out a way to get n+1 from n, provided that n≥5: Suppose we have a sequence of n+1 digits. If any pair of two consecutive digits is not increasing (decreasing or the same), then subtract them and replace them with that number. This gives a sequence of n digits for which we have a solution. If, on the other hand, the above does not apply, then since n+1≥6, there must be a pair of two consecutive digits (say, bc) such that 0≤b<c≤5 (for example, 45 in the sequence 456789). Add them and replace them with that number. Again, this gives a sequence of n digits for which we have a solution.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
FractalFusion wrote:
This is why things like 2/(3-(2/(3-(2/(3-(...)))))) and sqrt(sqrt(sqrt(...))) are not well-defined.
This leaves me wondering what exactly is it that makes it not well-defined. Is there some rule of mathematics that's being broken by extending that expression infinitely, or is it just that it's not well-defined because in this particular case the result is ambiguous?
Player (36)
Joined: 9/11/2004
Posts: 2631
Remember how you originally defined the expression. You began with an initial value and then found an expression that it was equal to and iterated it. The initial value is important to the expression and governs what the expression evaluates to. So because it's missing from your expression it's not well-defined. A well defined version of the same expression would be: a_0 = 1 a_n+1 = 2/(3-a_n) lim n->infinity(a_n) = ? Without the a_0 initial condition then you're left with an expression that cannot be evaluated because it's not complete.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Editor, Expert player (2080)
Joined: 6/15/2005
Posts: 3284
BrunoVisnadi wrote:
Some people posted in the comments this other solution: 4*(8-7)*(0-7+9)=8. I believe this one is valid, thus, we can in fact be sure every 14 digit long sequence has a equation.
I'd be a bit more careful before declaring that every 7-digit sequence has a solution just because someone found a solution for the supposedly one missing sequence of an erroneous result. Since the winner's program couldn't find something as simple as 4*(8-7)*(0-7+9)=8, the entirety of the Riddler's "solution" is now thrown into doubt. In fact, I did some calculations myself as a programming exercise, and came up with completely different conclusions for n=3 and n=4. I got 237 out of 1000 for n=3 (not "about a third of all possible strings") and 5934 out of 10000 for n=4 (not "about 80 percent"). So, who even knows what the actual answer is anymore.
Warp wrote:
FractalFusion wrote:
This is why things like 2/(3-(2/(3-(2/(3-(...)))))) and sqrt(sqrt(sqrt(...))) are not well-defined.
This leaves me wondering what exactly is it that makes it not well-defined. Is there some rule of mathematics that's being broken by extending that expression infinitely, or is it just that it's not well-defined because in this particular case the result is ambiguous?
Ambiguity is probably the biggest reason why things are sometimes left undefined. For example, the difficulty in defining a value for 00 comes from the number of possible interpretations and limits. But in some cases, even if not ambiguous in a technical context, in other more basic contexts defining any value may be misleading, unhelpful, and/or useless. See this video (which in fact you linked some years ago and illustrates this perfectly) for what I mean by this.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
2017 Raytheon MATHCOUNTS National Competition It's actually fun to pause the video when the questions are shown, and solve them in your head.
Player (80)
Joined: 8/5/2007
Posts: 865
Warp wrote:
2017 Raytheon MATHCOUNTS National Competition It's actually fun to pause the video when the questions are shown, and solve them in your head.
These were a lot of fun! I got 42 out of 54 questions, averaging what I believe was about a minute per question. I feel okay about my performance as I'm a little out of practice and these were tough questions answered by some of the sharpest students in the country. Some notes (approximate timestamps in parentheses): I don't know if this was by design, but it seemed like when contestants buzzed in almost instantly with the correct answer, the answer was often 4. Examples included questions 20 (26:40), 25 (31:30), 32 (40:00), and 45 (48:30). I don't think I fully understand question 10 (15:00). Had they intended to write that K is an integer? I see that the solution is K = 17^2, corresponding to y = 1000 (or y = 1017). But what's wrong with y = 1008 (or y = 1009), giving K = 1? What's really being asked here? Question 16 (22:00) annoyed me because the problem statement is ambiguous as to whether the empty set is included. I included it and obtained an answer of 50, instead of the "correct" answer of 49. Question 24 (30:30) confused me. I figured that two of the numbers being squared had to be zero and the third had to be one. There are five ways to make zero in each of those two squared numbers and three places to put them, totaling 75. I now see that there are eight ways to produce 1 in the remaining term, which is where I miscounted. I got stuck on question 26 (34:30). I was able to simplify it to the sum over n>1 of 1/(n*(n+3)), but that looks too much like the Basel problem to me. I have no idea how this slight modification turned pi^2/6 into 13/36. Can someone help me? The writers knew what they were doing with question 28 (35:30). I even caught that they were asking about formats, not license plates, but quickly thought, "Nah, they must mean plates." Question 41 (45:30) is just evil. As if the counting weren't tricky enough (I was off by 1), I forgot to multiply my answer by 4, the square of the length of one side. Question 42 (46:30) stumped me. I wasn't able to come up with a simple expression for the area of a kite, probably because the kite is not uniquely defined by the length of its sides. Of course, the kite of maximal area is uniquely defined by the length of its sides. Could someone explain the quick-and-dirty approach that was likely used to solve the problem? I'm baffled that someone was able to answer question 48 (51:30) so quickly and I can't even reproduce their result. just now reproduced the result, almost immediately after typing this! This process is identical to casting out nines. My mistake was somehow thinking that 3^2017 was not divisible by 9. For some reason, I thought it had to be raised to an even power for 9 to be a factor. Oops. Finally, Luke looked hilariously frazzled by the end of the competition. Good for him for eking out a victory, especially by what was probably a matter of seconds.
Editor, Skilled player (1348)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Found it pretty fun as well
Bobo the King wrote:
I don't think I fully understand question 10 (15:00). Had they intended to write that K is an integer? I see that the solution is K = 17^2, corresponding to y = 1000 (or y = 1017). But what's wrong with y = 1008 (or y = 1009), giving K = 1? What's really being asked here?
One of the 2 solutions for y must be a multiple of 100, that's why K must be at least 17²
Bobo the King wrote:
Question 16 (22:00) annoyed me because the problem statement is ambiguous as to whether the empty set is included. I included it and obtained an answer of 50, instead of the "correct" answer of 49.
They actually said 'one or more coins', thus the answer must be 49.
Bobo the King wrote:
Question 24 (30:30) confused me. I figured that two of the numbers being squared had to be zero and the third had to be one. There are five ways to make zero in each of those two squared numbers and three places to put them, totaling 75. I now see that there are eight ways to produce 1 in the remaining term, which is where I miscounted.
Haha, I also found 75 when I tried that one! I solved it as if it was (a² - x²) (...) = 1, so the only possibility would be a=1 and x=0.
Bobo the King wrote:
I got stuck on question 26 (34:30). I was able to simplify it to the sum over n>1 of 1/(n*(n+3)), but that looks too much like the Basel problem to me. I have no idea how this slight modification turned pi^2/6 into 13/36. Can someone help me?
It simplifies to (1/3)*(1/2 + 1/3 + 1/4) = 13/36. See that everything that has denominator bigger than 4 is cancelled out.
Bobo the King wrote:
Question 42 (46:30) stumped me. I wasn't able to come up with a simple expression for the area of a kite, probably because the kite is not uniquely defined by the length of its sides. Of course, the kite of maximal area is uniquely defined by the length of its sides. Could someone explain the quick-and-dirty approach that was likely used to solve the problem?
Consider the left half of the kite. It's a 6-10-X triangle, and it's area is 10*sin(a)*6/2, (of course, a is the angle between sides 6 and 10). To maximize that area, we need a = 90º, which gives us area 30. Double that, and you get the maximum area of the kite.
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Editor, Expert player (2080)
Joined: 6/15/2005
Posts: 3284
Revisiting the Riddler's problem, I found a simple way to prove that, for every base b, there is a minimum N, depending on b, for which all base b sequences of length ≥N have a solution. I assume this is what Tub really wanted to believe the actual problem was: A simple proof only that there is a minimum N in base 10, without going through tables or computer programs which may themselves be full of errors. May as well, since the given Riddler solution is a bit off (and who's to say my computer program is correct either). Proof: It is enough to show that all base b sequences of some length N(b) (N depending on b) represent 0 (i.e. can evaluate to 0) using only subtraction(-), multiplication(*), and brackets. Then it follows that all longer sequences represent 0 by multiplication, and all sequences of length ≥2*N(b) have a solution, by representing 0 in two disjoint blocks of length ≥N(b). For b=2:
00: 0*0
01: 0*1
10: 1*0
11: 1-1
Consider a sequence S in base b of length 2*N(b-1). If S contains the digit 0, then it clearly represents 0 by multiplication. Otherwise, from left to right, replace every instance of consecutive digits (b-1,x) (digit b-1 followed by x, where x is a digit from 1 to b-1) with their difference b-1-x. This results in a sequence S' whose first N(b-1) digits are from 0 to b-2. By induction (as if these digits are from a sequence of base b-1), these N(b-1) digits represent 0; therefore so does S', and therefore so does S. QED From above, N(2)=2 and N(b)≤2*N(b-1), and so N(10)≤2*28=512. Therefore, without needing to use tables or computer programs, we can conclude that every base 10 sequence of length 1024 or greater has a solution.
Bobo the King wrote:
I don't think I fully understand question 10 (15:00). Had they intended to write that K is an integer?
Even if they say K is a real number, you can figure out easily that K has to be an integer.
Bobo the King wrote:
I got stuck on question 26 (34:30). I was able to simplify it to the sum over n>1 of 1/(n*(n+3)), but that looks too much like the Basel problem to me. I have no idea how this slight modification turned pi^2/6 into 13/36. Can someone help me?
BrunoVisnadi already answered it. By the way, the Basel problem concerns the sum of reciprocals of squares, not the reciprocals of the numbers themselves which is the harmonic series.
Bobo the King wrote:
Question 42 (46:30) stumped me. I wasn't able to come up with a simple expression for the area of a kite, probably because the kite is not uniquely defined by the length of its sides. Of course, the kite of maximal area is uniquely defined by the length of its sides. Could someone explain the quick-and-dirty approach that was likely used to solve the problem?
As well as what BrunoVisnadi said, it is also possible to get the answer as follows: A quadrilateral with given side lengths has its area maximized when it is cyclic. When maximizing area, the order of the side lengths is completely irrelevant and so we can rearrange the sides of the kite into a 6-by-10 rectangle. Rectangles also maximize the area (since they are cyclic), so the answer is 60.
Player (80)
Joined: 8/5/2007
Posts: 865
A quick thanks to BrunoVisnadi for his post! That cleared up a lot.
FractalFusion wrote:
Bobo the King wrote:
I got stuck on question 26 (34:30). I was able to simplify it to the sum over n>1 of 1/(n*(n+3)), but that looks too much like the Basel problem to me. I have no idea how this slight modification turned pi^2/6 into 13/36. Can someone help me?
BrunoVisnadi already answered it. By the way, the Basel problem concerns the sum of reciprocals of squares, not the reciprocals of the numbers themselves which is the harmonic series.
Yeah, but 1/(n*(n+3)) = 1/(n^2 + 3n) resembles the Basel problem thanks to the squared term. Anyway, I'm facepalming hard at the fact that most of the terms cancel. I'm usually a bit better at catching telescoping sums.
FractalFusion wrote:
Bobo the King wrote:
Question 42 (46:30) stumped me. I wasn't able to come up with a simple expression for the area of a kite, probably because the kite is not uniquely defined by the length of its sides. Of course, the kite of maximal area is uniquely defined by the length of its sides. Could someone explain the quick-and-dirty approach that was likely used to solve the problem?
As well as what BrunoVisnadi said, it is also possible to get the answer as follows: A quadrilateral with given side lengths has its area maximized when it is cyclic. When maximizing area, the order of the side lengths is completely irrelevant and so we can rearrange the sides of the kite into a 6-by-10 rectangle. Rectangles also maximize the area (since they are cyclic), so the answer is 60.
Well it certainly doesn't help that I misheard the answer-- I thought they said "16". The best I could come up with was to conjecture that the maximal area is the square of the difference in lengths between the two sides (i.e., A = (10-6)^2). This, of course, makes no sense as a kite with four sides of length 10 would supposedly have maximal area of 0. Now this makes a lot more sense.
Editor, Skilled player (1348)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
I'd like to bring JXQ's problem up again. For those who didn't see the rules:
JXQ wrote:
This is a problem I came up with a little while back and have enjoyed kicking around, especially if I have time to kill and not much around to help kill it. I initially thought of this in an airport when I noticed some patterns in the floor tile. The initial problem: You are given a 3x3 square grid in the plane, through which you may draw as many straight "piercing lines" as you would like. A particular square on the grid is considered "pierced" if it contains one or more piercing lines within the area defined by its edges. The goal is to "skewer" the grid: pierce all the squares in this grid. (Note: piercing lines drawn exactly along a border between two rows/columns of squares do not count as piercing any squares - otherwise the problem becomes trivial). You can clearly do this in 3 lines, by drawing a line through each row or each column. Can you do it with just 2 lines? How about 1 line? Can you prove the lowest value (prove that a solution with less than a certain number of lines does not exist)? Larger grids: How about a 4x4 or a 5x5 grid? Do they follow similar patterns from the 3x3 case? How about an NxN grid? Can you come up with an algorithm for the general case to get an upper bound less than N? Can you prove that this is indeed the lowest number of lines possible? Grids in higher dimensions: Given a 3x3x3 grid of cubes, define piercing lines in a similar way: a cube is pierced if it contains one or more piercing lines within the volume defined by its edges. We can clearly skewer this grid in at least 3 times the optimal solution for the 3x3 grid, as we could draw piercing lines for each "slice" of the third dimension. Can it be done with fewer lines? From here the problem can continue to expand into higher dimensions and larger sizes. I haven't solved all of the aspects of the problem which I've put forth below, but they've been fun to think about. Formalizing geometric stuff into constructs that are more mathematically.. uh, generalizable(?) is not my strong suit, so I haven't gotten very far with any of the proofs.
We tried some cubes in higher dimensions. A 2x2x2x2 cube, for instance, requires 4 lines to be fully pierced. A 2x2x2x2x2 requires 6, and it's easy to proof you can't do it with 5. For the 3x3x3x3 cube, though, my best attempt was using 12 lines. I can't improve this solution neither proof you can't improve it. So, any ideas/suggestions here? Also, since this problem has a simple statement, I wouldn't be surprised if there is already some advances made on it somewhere.
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Tub
Joined: 6/25/2005
Posts: 1377
FractalFusion wrote:
Revisiting the Riddler's problem, I found a simple way to prove that, for every base b, there is a minimum N, depending on b, for which all base b sequences of length ≥N have a solution.
Beautifully simple. Induction over base is a clever approach. N10 = 1024 is quite a loose bound, but that's fine.
FractalFusion wrote:
I assume this is what Tub really wanted to believe the actual problem was
Brute forcing wouldn't answer the question if there was no minimum length, and it wouldn't answer the question within a week if the minimum length was just a bit larger than 7. It just didn't seem like a promising approach.
m00
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Every even perfect number ends in 6 or 28, base ten. Since there's a one-to-one correlation between even perfect numbers and Mersenne primes, wouldn't this mean that the above fact can be used to narrow the search for new Mersenne primes? In other words, take a candidate Mersenne number 2p-1, calculate its correspondent perfect number, and if it doesn't end in 6 or 28, we know it can't be a Mersenne prime.
Tub
Joined: 6/25/2005
Posts: 1377
That test is technically true, but in practice it rejects too few candidates to be useful. To figure out the exact percentage, try figuring out (or finding) a proof for your first claim. Work backwards to figure out the minimal requirements for your candidate for the proof to work. See how many mersenne candidates satisfy those requirements. (I've done it, but I won't spoil the results for now. It's insightful to do on your own.)
m00
Player (80)
Joined: 8/5/2007
Posts: 865
The Riddler wrote:
A kite shape is inscribed in a circle, as shown below.2 What is the kite’s area?
Ooh! I know this one! You see, there's these things called cyclic quadrilaterals... As for the rectangle, I don't know if there's a shortcut, but a simple application of the Pythagorean theorem should give you both sides. The dwarf puzzle is (mostly) recycled from a similar puzzle with-- if I remember correctly-- 100 seats on an airplane. (I think there may have even been one other riddle of the same form.) The answer to the first question is directly from the previous riddle. The second question is a bit trickier, but shouldn't be too difficult overall. I'll get to work on it.
Editor, Skilled player (1348)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Bobo the King wrote:
The dwarf puzzle is (mostly) recycled from a similar puzzle with-- if I remember correctly-- 100 seats on an airplane. (I think there may have even been one other riddle of the same form.) The answer to the first question is directly from the previous riddle.
The only difference I could notice between these puzzles is that, unlike the mad passenger, the dwarf can only choose among the 6 other beds. Because of that, I believe the answer is 5/12 instead of 1/2.
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Tub wrote:
That test is technically true, but in practice it rejects too few candidates to be useful.
So what you are saying is, formally speaking, that the decimal representation of most numbers of the form (2p-1)2p-1, where p is a prime, ends in either 6 or 28? Maybe I'll try to figure out why.
Player (36)
Joined: 9/11/2004
Posts: 2631
If n > 0, 2^n ends with the following values indexed on mod 4. 6, 2, 4, 8 Primes are odd so they are either 1 mod 4 or 3 mod 4 (disregarding 2), which implies 2^p ends with either 2 or 8, and 2^(p-1) will end with 6 or 4 respectively. 2^p - 1 ends with either 1 or 7. 1 * 6= 6 7 * 4 = 28 For 28 we have to ensure that the 10s digit is locked as well. If n > 1, the last TWO digits of 2^n end with the following values indexed mod 20: 76, 52, 4, 8, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88 Of these, the following are some of the values we're interested in, as they are also 3 mod 4: 8, 28, 48, 68, 88 And these are the others, as they are 2 mod 4: 4, 64, 24, 84, 44 Subtracting one from the first list and multiplying pairwise we get: 28, 1728, 1128, 5628, 3828 Which are all 28 mod 100. So in other words, numbers constructed from any number of the form (2^n - 1)*2^(n-1) with n as an odd whole number will "look like" a perfect number from the 6/28 test.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.