Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
Edit: Some edits to this post.
Since we've been talking about infinite series a lot recently, the Riddler Classic problem this week might interest you:
(My edits in square brackets to hopefully clarify things)
----------------------------------------------------------
[A] tortoise and [a] hare are about to begin a 10-mile race along a “stretch” of road. The tortoise is driving a car that travels 60 miles per hour, while the hare is driving a car that travels 75 miles per hour. [Assume both cars instantly attain those speeds during movement.]
The hare[, wanting to end at the same time as the tortoise,] realizes if it [were to wait] until two minutes have passed, they’ll cross the finish line at the exact same moment. And so, when the race begins, the tortoise drives off while the hare patiently waits.
But one minute into the race, after the tortoise has driven 1 mile, something extraordinary happens. The road turns out to be magical and instantaneously stretches by 10 miles! [The road stretches linearly, taking whatever is on the road with it, including the hare, tortoise, and finish line.] As a result of this stretching, the tortoise is now 2 miles ahead of the hare, who remains at the starting line.
At the end of every subsequent minute, the road stretches by [an additional] 10 miles [in a similar fashion]. With this in mind[, how] long after the race has begun should the hare wait so that both the tortoise and the hare will cross the finish line at the same exact moment?
----------------------------------------------------------
Hint: You don't actually need to find how long it takes for the tortoise to finish the race to answer this problem.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
Encode:
Edit: It is possible to playback video now, even though Youtube messed up and still said 95% processing.
Link to video
With the TAS being over 4.5 hours long, I didn't make a high-quality encode this time. Sorry about that.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
The numberphile calculation is indeed not rigorous, it would require a p-adic completion at "p=1", which we still can't make sense of, but it's far from "nonsense". It's related to the mysterious field with one element, that people have trouble defining, but has the potential to solve lots of problems.
The way you are describing p-adic completion at "p=1" (???) and the "mysterious field with one element" only makes me think there are better ways to describe ζ(-1).
By the way, it is pretty clear that a lot of people see the Numberphile calculation as nonsense. That is entirely on Numberphile. There are ways to present ζ(-1) and other similar series without it coming across as nonsense.
p4wn3r wrote:
It looks like Mathologer has no idea that non-archimedean completions exist, and I don't think it's too much to expect someone to understand a little of the subject they are talking about before dismissing it as nonsense.
Is it not possible to prove that ζ(-1)=-1/12 using analysis in complex numbers only? If it is possible, then I wouldn't expect anyone to bring in p-adics when it is not necessary to do so.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
p4wn3r wrote:
So, for this exercise, replace the usual absolute value of the real numbers with p-adic norm for p=2, also known as the 2-adic norm or the dyadic norm. Prove that, with respect to this metric:
1 + 2 + 4 + 8 + ... = -1
Well, it seems no one solved it. It's not very hard, though.
I solved it. I just never bothered to tell you.
It is conceptually easy once you understand p-adics.
p4wn3r wrote:
FractalFusion wrote:
You are studying a new strain of bacteria, Riddlerium classicum (or R. classicum, as the researchers call it). Each R. classicum bacterium will do one of two things: split into two copies of itself or die. There is an 80 percent chance of the former and a 20 percent chance of the latter.
If you start with a single R. classicum bacterium, what is the probability that it will lead to an everlasting colony (i.e., the colony will theoretically persist for an infinite amount of time)?
Extra credit: Suppose that, instead of 80 percent, each bacterium divides with probability p. Now what’s the probability that a single bacterium will lead to an everlasting colony?
Suppose that the probability of an everlasting colony is x. After a time lapse, the bacterium will either split or die. If it splits, we have two bacteria. The probability of both of them not generating an everlasting colony is (1-x)^2, so we'll have an eternal colony with probability 1-(1-x)²=2x-x².
Therefore, we have x = p(2x-x²), so either x=0, or 1 = p(2-x) => x = 2 - 1/p
Since x is a number between 0 and 1, the second solution only makes sense for p >= 0.5.
In particular, for p<0>0 for all N and still satisfy that limit.
Now, for p >0.5, I will argue that the correct solution is x = 2 - 1/p. If it were x=0, we would have that the expected number of bacteria after N events is 0, but it's in fact (2p)^N, which does not tend to 0 if p>0.5. So the probability should be positive, and therefore x = 2 - 1/p.
Yes, the probability is 0 if p<=0.5 and 2-1/p if p>0.5.
I mentioned that there are paradoxes when p=0.5. This is because, as you said, the expected number of bacteria after N events, starting from 1 bacterium, is (2p)^N. When p=0.5, the expected number of bacteria is 1, which may indicate that the colony may survive with positive probability. Yet, as we have figured out, the colony is guaranteed to die out eventually.
Even better, if you take the expected number of splits before dying out, you would expect that a colony dies out if and only if the expected number of splits before dying out is a finite non-negative number. This is false. The expected number of splits before dying out when p<=0.5 is 1/(1-2p): for p=0.5, the expected number of splits before dying out is infinite, despite that it is guaranteed to die out!
You can think of this as a kind of random walk; a person standing at the position n and having 0.5 chance each of going to n+1 or n-1 each step, will eventually reach 0, yet the expected number of times the person will increase their position number before reaching 0 is infinite.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
Patashu wrote:
It's notable that 2 and 4 are both important values for sqrt(2) infinite power tower - 2 is the first time it crosses the line y = x where the derivative is less than zero, 4 is the second time but this time with derivative greater than zero. But I'm not sure if this is coincidence or not.
I assume that by "it" you mean the exponential function sqrt(2)^x being the function which you iterate to get the sqrt(2) power tower, and that you mean the derivative is less than 1 when x=2 and greater than 1 when x=4.
None of what you said is a coincidence. In fact, it explains exactly why the sqrt(2) tower power converges to 2, and not to 4. Here is the diagram for fixed-point iteration using sqrt(2)^x:
Notice that the orange iterations converge to x=2 and the purple ones diverge from x=4.
In general, if a function f(x) crosses the line y=x at a point x=a, iteration converges to that point if |f'(a)|<1, and diverges if |f'(a)|>1.
Anyway, here's an interesting Riddler Classic question. I copied it below as well:
----
You are studying a new strain of bacteria, Riddlerium classicum (or R. classicum, as the researchers call it). Each R. classicum bacterium will do one of two things: split into two copies of itself or die. There is an 80 percent chance of the former and a 20 percent chance of the latter.
If you start with a single R. classicum bacterium, what is the probability that it will lead to an everlasting colony (i.e., the colony will theoretically persist for an infinite amount of time)?
Extra credit: Suppose that, instead of 80 percent, each bacterium divides with probability p. Now what’s the probability that a single bacterium will lead to an everlasting colony?
----
Note: This question is a little deeper than just solving a quadratic. In fact, for p=0.5, you might get some interesting paradoxes.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
So, I'm impressed with the improvements you made.
But is there something special about species 0x0615 that triggers the glitched egg hatch into ACE? Are there other species numbers for which it works?
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
(a) A category where every morphism is an isomorphism is called a groupoid. A perverse definition of a group is: a groupoid with a single object. Make sense of this.
(b) Give an example of a groupoid that's not a group.
I might as well answer this. (Am I learning category theory just to answer p4wn3r's questions?)
(a) Consider a groupoid on a single object A, so all isomorphisms are in Mor(A,A). Let f and g be isomorphisms in Mor(A,A). Then g○f is in Mor(A,A) by property of composition, so composition is closed. Composition is associative. idA is the identity morphism in Mor(A,A). f has an inverse isomorphism f-1 in Mor(A,A). So a groupoid on a single object A forms a group.
Likewise, a group is a groupoid on a single object A (elements of the group are isomorphisms of the groupoid, and the group operation is "composition").
(b) Take the category on two objects A,B with four isomorphisms: idA in Mor(A,A), idB in Mor(B,B), f in Mor(A,B), and f-1 in Mor(B,A). Then all the groupoid conditions are satisfied, but this groupoid is not a group (group theory definition): f○f does not exist in the groupoid so it is not closed under composition.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
r57shell mentioned competitive programming problems. Recently I saw one that's very interesting: https://codeforces.com/problemsets/acmsguru/problem/99999/511
Essentially, write an efficient computer program that finds a solution to a Fermat's Last Theorem-like equation for a field of prime characteristic. The prime and exponent can be as large as 1 million, and the program should run in 750 ms.
Just talking about math theory here (no programming):
By multiplying both sides by the multiplicative inverse of x (mod p), you can simplify it to solving 1+Y^n=Z^n, where Y and Z are nonzero (mod p). Then you just generate nth power residues until you get a collision of two consecutive values (which is extremely likely if the nth power residues constitute more than even a small fraction of all modulo classes) or you exhaust them all.
If the nth power residues constitute a very large fraction of all modulo classes, such as 1/3 (this happens when n=3 and p=6k+1), then for large enough p a solution is a practical certainty due to how many collisions there are (in fact, it is a proven certainty). So in that case, you just need to guess at a few small values and check whether they are nth power residues until you find two consecutive numbers that work (which can be done efficiently), then find their nth roots using polynomial factorization over Zp, or by other, possibly more efficient, methods such as the https://en.wikipedia.org/wiki/Tonelli-Shanks algorithm.
Not sure what your program is like, but I'm guessing it goes along these lines.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
For the Korok seeds problem, 2 seeds are enough. (It is easily shown that 1 is not possible.) Below is a diagram showing the positions of the two seeds (labelled by X). The top left one is closer to the blue circles than the center, and the bottom right one is closer to the red circles than the center.
p4wn3r wrote:
Consider a non-constant function f: R -> R satisfying:
f(x+y) = f(x)f(y),
for all real x and y.
Mark as true or false:
(1) f(x) is not even.
(2) f(0) = 1
(3) f(x) > 0 for all x in R
(4) f(x) is an exponential function
Answer: (1), (2) and (3) are all true, and (4) is false
Explanation:
(3)
f(x)=f(x/2)^2 and so f(x) is always non-negative. Furthermore, no f(x) can be 0; otherwise if f(c)=0 for some c, then f(x+c)=f(x)f(c)=0 for all x and so f(x) is the constant zero function, which is not allowed. So f(x)>0 for all x in R, and so (3) is true.
(2)
f(0)=f(0)^2, and since f(0) is positive from (3), f(0) must be 1. So (2) is true.
(1)
If f(x) is an even function, then f(x+(-x))=f(x)f(-x)=f(x)^2 but also f(x+(-x))=f(0)=1 (from (2)), so f(x)^2=1. Since f(x) is positive from (3), f(x)=1 for all x (f is the constant one function, which is not allowed). So f(x) is not an even function, and so (1) is true.
(4)
This is similar to how there are nonlinear solutions to Cauchy's functional equation; that is, f(x+y)=f(x)+f(y) for all real x and y. The explanation runs along similar lines as follows:
It is true that f(0) must be 1 (from (2)), and that f(x)>0 for all x (from (3)). However, none of f(x) when x is nonzero is fixed; they are described as follows:
Let S be a Hamel basis for R over Q. Here R is considered as an infinite-dimensional vector space over Q, and S is uncountable. Note that S exists because of the axiom of choice but cannot be explicitly described.
Then f(x) is uniquely described by the values of f(s) for each s in S, where we can set the value of each f(s) to be any positive number. The equation f(x+y)=f(x)f(y) is sufficient to determine values for all real numbers, given the values over the basis S. This is through closure under addition, subtraction, negation, scalar multiplication by a positive integer, and scalar division by a positive integer.
So f(x) need not be an exponential function, and so (4) is false.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
Riddler has an interesting Ridder Express problem, as follows:
----
While spending more time at home in recent weeks, I’ve had the chance to revisit one of my favorite video games from recent years — The Legend of Zelda: Breath of the Wild. Within the game, there are hundreds of hidden “Korok Seeds,” which I’m having an increasingly difficult time finding.
Fortunately, there’s a special mask you can acquire in the game that makes a sound any time you’re within a certain distance of a Korok Seed. While playing, I marked nine distinct locations on the game map, forming the 3-by-3 grid shown below:
9 icons in a 3x3 grid. No Korok seeds were within range of the central icon, but all 8 surrounding icons were within range.
Each leaf symbol is within range of a Korok Seed, while the point in the middle is not within range of a Korok Seed. Given this arrangement, what is the minimum possible number of Korok Seeds I could have detected?
----
May look a bit tricky at first, but this isn't too hard of a problem.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
merrp wrote:
Do you remember what phrases you used to make it do that? On Route 110?
I've been doing research and found out the exact area it modifies, but I haven't been able to make it crash yet.
Sorry, I've been busy with real life and forgot to reply to this until now.
I can't remember exactly, but any phrase that replaces a wall with something that allows you to walk through it should work (I believe such phrases are mostly located in the Pokemon name phrases). After walking through the wall in Route 110 (as well as some other areas), if you keep walking left to "leave" the area, the freeze should happen.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
Next one! Prove that
(All products are over the prime numbers)
There are two important identities:
prod(1-1/p^s)=1/ζ(s)
prod(1+1/p^s)=ζ(s)/ζ(2s)
First one is by Mobius inversion; second is because prod(1+1/p^s) = prod(1-1/p^(2s))/prod(1-1/p^s) = ζ(s)/ζ(2s)
So:
prod[(p^4+1)/(p^4-1)] = prod[(1+1/p^4)/(1-1/p^4)] = (ζ(4)/ζ(8)) / (1/ζ(4)) = ζ(4)ζ(4)/ζ(8)
and by ζ(4)=pi^4/90 and ζ(8)=pi^8/9450, ζ(4)ζ(4)/ζ(8) simplifies as 7/6.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
In a previous post, I mentioned the following result:
If a and b are two positive integers, with gcd(a,b)=1, then the set
S = {ma+nb | m,n integers in Z} = Z
However, if we constrain m and n to be non-negative integers, it's in general not true that the set will be {0, 1, 2, ...}. For this case, however, we still can say something. Namely, if we define f(a,b) the largest integer not expressible by the form ma+nb (or, as a mathematician would say, a linear combination with non-negative integer coefficients), we have:
For any integers a, b greater than 1 such that gcd(a,b)=1, f(a,b) = ab-a-b
Prove this.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
Warp wrote:
Prove that no partial sum of the harmonic series is an integer (other than, rather obviously, the very first term, which is just 1).
(And by "partial sum" I mean 1+1/2+1/3+...+1/n for any given n.)
As I thought, this is a blackpenredpen problem. Anyway, I solved it without looking at how it was done in that video:
Let 2^k be the largest power of 2 which is less than or equal to n (where n>1). Then:
* The largest power of 2 that divides LCM(1,2,...,n) is 2^k (k>=1)
* So the largest power of 2 that divides LCM(1,2,...,n)/2 is 2^(k-1)
* 2^k is the only number from 1 to n that has k (or more) factors of 2
* Therefore 2^k is the only number from 1 to n that does not divide LCM(1,2,...,n)/2
Suppose 1+1/2+1/3+...+1/n is an integer. Multiply it by LCM(1,2,...,n)/2. This causes all summation terms to be integers except the term corresponding to 1/2^k, and so the resulting sum is not an integer. This contradicts that 1+1/2+1/3+...+1/n is an integer, because an integer times an integer is supposed to be an integer.
PS: This is "essentially" how p4wn3r solves it, just in elementary terms.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
For a more modern example, consider Fermat's little theorem from the point of view of someone who only knows factorization in natural numbers. It looks quite odd why prime numbers are magical, and allow ap-a to be a multiple of p. In contrast, by noticing that multiplication mod p defines a group, Fermat's little theorem is almost a triviality! This is the idea behind good definitions, they invite us to focus on the relevant properties to solve the problems.
Yes, but your example is about the concept of mod p, an absolute essentiality in elementary number theory.
The thing about "negative primes", is that allowing them in elementary number theory would cause many well-known statements involving primes to be wrong. Not just the fundamental theorem of arithmetic, but also, for example:
* Fermat's little theorem as stated, a^p=a (mod p) fails if p is allowed to be a negative prime. Even the related statement a^(p-1)=1 (mod p) when a is coprime to p, is false for negative prime p.
* The statement that for an odd prime p, -1 is a quadratic residue mod p iff p is of the form 4k+1, is false if p is allowed to be a negative prime (for example, p=-3). Related: The statement that primes of the form 4k+1 are a sum of two squares is false if p is allowed to be a negative prime.
* Gauss's Lemma wouldn't make sense if p is allowed to be a negative prime.
I don't think having the concept of "negative primes" and fitting these theorems around them would help us understand these theorems in any way.
Also, looking at the topics in Hungerford's textbook, elementary number theory clearly is not the end goal here. The only thing it has in common with elementary number theory is modular arithmetic and the Chinese Remainder Theorem, neither of which are affected by allowing primes to be negative. An actual elementary number theory textbook, one which goes over things like Fermat's little theorem, primality testing, sum of squares, Pythagorean triples, etc., would most likely define primes the same way most people have done it for centuries: natural numbers only.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
Warp wrote:
Blackpenredpen recently tackled the question of whether any of the numbers of the form
1010101...01
or in other words
1 + 100 + 1002 + 1003 + 1004 + ... + 100n
can be prime, other than 101.
It would be interesting to see your approaches at this.
1 + 100 + 1002 + 1003 + 1004 + ... + 100n cannot be prime for n greater than 1. In fact there is a simple way to factor the number at least partially.
The reason is that the number is of the form 1+x2+x4...+x2n (where x=10). This can be rewritten as:
1+x2+x4...+x2n
=(x2n+2-1)/(x2-1)
=(xn+1-1)(xn+1+1)/(x-1)(x+1)
If n is odd, then (x-1)(x+1) divides (xn+1-1) and we can factor it as
(xn-1+xn-3+...+x2+1)(xn+1+1).
If n is even, then x-1 divides xn+1-1 and x+1 divides xn+1+1, and we can factor it as
(xn+xn-1+...+x+1)(xn-xn-1+...-x+1)
----
Warp wrote:
p4wn3r wrote:
If you ask me, I do think the most elegant definition of prime numbers, even if we work entirely in elementary number theory, is to allow them to be negative.
One problem with that is the same as why 1 isn't considered a prime: It contradicts the fundamental theorem of arithmetic, which states: "Every positive whole number can be written as a unique product of primes."
Allowing for negative primes would break the uniqueness requirement.
Negative numbers (and 0) are not relevant to the fundamental theorem of arithmetic. The fundamental theorem of arithmetic is a statement about natural numbers. (Technically, 1 is also not relevant either.)
So it makes no sense to talk about negative numbers being prime or not prime, in this context.
p4wn3r wrote:
The modern definition of unique factorization only requires that the factorization be unique up to permutations of the factors and multiplication by units.[/url]
I'm not sure "modern" is the right word here, unless by "modern" you mean "applied to rings in general, rather than just the natural numbers".
Warp wrote:
I have never heard of such a definition. A unit, or multiplicative identity element, is the only value that leaves the original value unchanged when multiplied by that element.
Technically, the multiplicative identity element of a ring is called "unity", not "unit". A unit is any number that divides the unity.
E.g. In the ring of integers, 1 is the unity, and -1 and 1 are units (because they are both divisors of 1).
p4wn3r wrote:
The reason I think Hungerford, and other algebra authors, prefer negative primes, is because it makes theorems much simpler.
I don't know if that is the reason Hungerford does that, but as for whether it makes theorems much simpler, if we're talking about elementary number theory, I doubt that.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
For example, a very popular algebra textbook states (I changed some symbols because LaTeX is not supported here):
Hungerford wrote:
DEFINITION An integer p is said to be prime if p is not 0,1,-1 and the only divisors of p are 1,-1 and p, -p.
EXAMPLE 3, -5, 7, -11, 13, -17 are prime, but 15 is not (because 15 has divisors other than 1,-1 and 15,-15, such as 3 and 5).
I noticed the textbook you cited is in the Graduate Texts in Mathematics series.
Outside ring theory, there is no need whatsoever to address negative numbers or zero when talking about prime numbers. It is only when studying ring theory that you need to consider this. Prime numbers can then be reformulated as prime elements of Z, in which case the primes are ±2, ±3, ±5, ±7, ±11, ...
I suppose the definition of prime number given in that textbook is written with ring theory in mind, although technically the definition given is for irreducible elements rather than prime elements.
Edit: Forgot to mention, but the link to the textbook doesn't work.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
Now, Fractal, I am curious. Did you find the transformation by unwrapping the elliptic curve from the point doubling operation or managed to derive it in a more intuitive way?
I derived it based on two applications of a well-known characterization of primitive Pythagorean triples:
x=s^2-t^2, y=2st, z=s^2+t^2
Let u^2=s^2-t^2. Then:
u=a^2-b^2, t=2ab, s=a^2+b^2
giving the above formulation of (x,y,z).
It so happens that xy/2 has the same squarefree part as ab/2, which is the key. It wasn't entirely unexpected from my end though; I had a feeling something like this would work based on infinite descent arguments I have seen before.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
Prove that there are infinitely many right triangles with rational side lengths whose area equals 6.
The notation (a,b,c) denotes a right triangle with leg lengths a,b and hypotenuse length c (a^2+b^2=c^2).
To prove this statement, we'll just prove that there is an infinite family of non-similar right triangles (a,b,c) with the following properties (＊):
● Integer side lengths
● gcd(a,b)=1 (so it is the smallest integer triangle of all triangles similar to it), and
● Area is 6 times a square integer; that is, of the form 6p^2.
(To get the corresponding rational right triangle with area 6, divide all sides by p.)
If (a,b,c) is a right triangle satisfying (＊), then we can construct another non-similar right triangle (x,y,z) satisfying (＊), as follows:
x=(a^2-b^2)^2, y=4ab(a^2+b^2), z=a^4+6a^2b^2+b^4
It is easily checked that x^2+y^2=z^2 and gcd(x,y)=1 (one of a,b is even and the other is odd). Furthermore, the area of the triangle (x,y,z) is:
and so if the area of triangle (a,b,c), which is ab/2, is 6 times a square integer, then the area of triangle (x,y,z) is also 6 times a square integer.
Finally, the right triangle (3,4,5) satisfies (＊). So we can use the above process to construct an infinite family of non-similar right triangles satisfying (＊) and thus prove the statement.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
McBobX wrote:
If we look at BCAS, the most enjoyable thing is the high speed and the air sliding.
I just watched BCAS now, and actually that was the least enjoyable part of the run for me. The most enjoyable part of the run was the autoscroller.
Did it combine two gimmicks or something? (Just from its name I thought it was a hack like that.) It just doesn't feel like Mega Man.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
It seems to me that it only makes sense to define the ring of polynomials mod p, where it is, in fact, Euclidean. If we define them over a composite number n we get the problem that the group of units mod n is not closed under addition, so in this case, the ring wouldn't even be an integral domain. That's why polynomial mod a composite number can have more roots than their degree, but not modulo a prime number.
For example, take x^2-1 over Z/8Z. Not only does it not have unique factorization (x^2-1 = (x-1)(x+1) = (x-3)(x+3), for example), you could even factor x^2-1 into two polynomials of higher degree, like x^2-1 = (4x^4+x-1)(4x^4+x+1). Certainly there is no Euclidean property here.
p4wn3r wrote:
What I thought when he presented it was: Every permutation can be broken up into cycles, the sign of the permutation is found by multiplying (-1)^(length+1) for each cycle.
Oh, I didn't even think about it in terms of cycles. Well in that case rearranging and relabelling is just equivalent to relabelling the numbers in the cycle representation, and whether a permutation is even or odd depends only on cycle structure and not on the labels.
Note that conjugation also preserves cycle structure.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
Maybe it's just me, because I know most of the math concepts, but I also thought his final observation, where he uses a relabeling to prove that the sign of the permutation is the Legendre symbol very difficult to follow. The argument in the blog post, which uses permutation cycles, although more mathy, is more natural in my opinion.
I assume you are referring to the proof of Zolotarev's Lemma. I'll try to summarize what I got from it in the video.
Every prime p>2 has a primitive root. There is a proof which uses field theory: Basically, if the max order of elements in (Z/pZ)* (multiplicative group) is some m<p-1, then every element satisfies x^m-1=0 over the field Z/pZ, and so x^m-1 has p-1 factors, contradicting that x^m-1 can only have at most m factors. It is nonconstructive (no algorithm is known in general that gives a primitive root).
If g is a primitive root of Z/pZ, then g^2, g^4, ... , g^(p-1) are all squares, and so those are all the quadratic residues and the rest (g^1, g^3, ... , g^(p-2)) are all quadratic nonresidues.
The rearranging and relabelling trick is better described as conjugation. So for a permutation x, rearranging and relabelling turns it into zxz-1: left-multiplying by a permutation z corresponds to rearranging, and right-multiplying by z-1 corresponds to relabelling. Because parity of a permutation when multiplying is like even/odd numbers under addition, x and zxz-1 have the same parity. This is why rearranging and relabelling does not change parity. (So you don't have to wait for Mathologer to prove it next time.)
So because of the rearranging and relabelling trick, the permutation based on x→bx (mod p) is turned into a permutation based on x→x+c (mod p-1), by taking discrete logarithms, where g is a primitive root and b=g^c. The parity of x→x+c (mod p-1) is even if c is even, and odd if c is odd. Based on the property of primitive roots above, x→bx is even if and only if b is a quadratic residue mod p.
Notice that the orange iterations converge to x=2 and the purple ones diverge from x=4.
In general, if a function f(x) crosses the line y=x at a point x=a, iteration converges to that point if |f'(a)|<1, and diverges if |f'(a)|>1.
Anyway, here's an interesting Riddler Classic question. I copied it below as well:
----
You are studying a new strain of bacteria, Riddlerium classicum (or R. classicum, as the researchers call it). Each R. classicum bacterium will do one of two things: split into two copies of itself or die. There is an 80 percent chance of the former and a 20 percent chance of the latter.
If you start with a single R. classicum bacterium, what is the probability that it will lead to an everlasting colony (i.e., the colony will theoretically persist for an infinite amount of time)?
Extra credit: Suppose that, instead of 80 percent, each bacterium divides with probability p. Now what’s the probability that a single bacterium will lead to an everlasting colony?
----
Note: This question is a little deeper than just solving a quadratic. In fact, for p=0.5, you might get some interesting paradoxes.
9 icons in a 3x3 grid. No Korok seeds were within range of the central icon, but all 8 surrounding icons were within range.
Each leaf symbol is within range of a Korok Seed, while the point in the middle is not within range of a Korok Seed. Given this arrangement, what is the minimum possible number of Korok Seeds I could have detected?
----
May look a bit tricky at first, but this isn't too hard of a problem.