Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
So it does turn out that there is a nice factorization of the sextic into cubics in general, even though it's not over the integers (except when 4a-7 is a square).
By the way, the (a-2-a sqrt(4a-7)) should be over 2; that is, (a-2-a sqrt(4a-7))/2.
p4wn3r wrote:
Therefore, the Galois group should be generated by two cyclic Z3 groups, and another Z2 group that switches 3 roots from one cycle to the other.
This is probably beside the point, but finding Galois groups is quite complicated and I can't be certain that the Galois group has to be Z3×Z3×Z2 (unless there's something I'm missing). Yes it's true that, if we look at the problem purely as a permutation of 6 roots (that is, the maximal subgroup of S6 satisfying the cycle conditions), then it is Z3×Z3×Z2. But Galois groups have additional properties because they describe automorphisms over Q.
I can say that if 4a-7 is a square number (which happens when a=8), then from your factorization we get two cubics over the integers. Since automorphisms over Q can only map roots to roots within the same minimal polynomial, you can't switch the roots of one polynomial with the roots of the other. So in this case it is not possible to get Z2 in there.
The second Z3 also makes the assumption that the roots of one cycle are "independent" of the other cycle. That is not necessarily so and I made that mistake in my previous post. E.g. Q(sqrt(2)) and Q(sqrt(2)+1) are the same field even though the minimal polynomials of sqrt(2) and sqrt(2)+1 are x^2-2 and (x-1)^2-2=x^2-2x-1, respectively. Indeed, the Galois group of (x^2-2)(x^2-2x-1) is not Z2×Z2, but Z2. However, I don't really have a strategy for how to determine whether the second Z3 should be included or not.
p4wn3r wrote:
... just plug the solutions in the system, which you can check with trigonometric identities.
(1+2sqrt(3)sin(pi/9))^2 = 8 - (1+2sqrt(3)sin(2pi/9))
(1+2sqrt(3)sin(2pi/9)^2 = 8 + (-1+2sqrt(3)sin(4pi/9))
(-1+2sqrt(3)sin(4pi/9))^2 = 8 - (1+2sqrt(3)sin(pi/9))
That would have been a nice way to reduce the proof to a few lines, and this was my first line of thought. Unfortunately I couldn't find a way to prove the identities within any reasonable amount of brainpower (it seems you have to use the minimal polynomial of sin(pi/9) somewhere), so I settled for proving it is the solution to one of x=±sqrt(8±sqrt(8±sqrt(8-x))) based on polynomials (which seems easier) and using numerics to figure out which one it is.
p4wn3r wrote:
Although there's of course the question of convergence that I didn't bother to check...
It shouldn't be too hard to check. The most concise version I have to prove this and other similar fixed-point iteration methods (like infinite nested radicals) is the criterion for convergence of fixed-point iteration (Theorem 1) which I linked in my previous post. I'll add a bit of detail below.
If we let g(x)=±sqrt(8±sqrt(8±sqrt(8-x))) and consider [-7,7], you just have to check that whenever -7<x<7, we have -7<g(x)<7 as well as |g'(x)|<1. In fact 1<|sqrt(8-x)|<4 → 2<|sqrt(8±sqrt(8-x))|<4 → 2<|g(x)|<4, so these can be established easily. This proves not only that g(x)=x has a unique solution in [-7,7], but also that fixed-point iteration g(g(g(...g(g(c))...))) converges to this solution when the starting value c is in [-7,7].
You can also use a fixed-point iteration diagram to show convergence (for example, http://tasvideos.org/forum/viewtopic.php?p=459785#459785 ), but the diagram of this function is a little bit hard to get without resorting to WolframAlpha.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
Prove that
sqrt(8-sqrt(8+sqrt(8-...))) = 1 + 2sqrt(3)sin(pi/9)
The pattern of signs on the infinitely nested radical is -,+,-,-,+,-,-,+,-,...
Consider equations of the form x=±sqrt(8±sqrt(8±sqrt(8-x))). It is easily shown that for each choice of ±, there is exactly one solution in [-7,7], and fixed-point iteration in [-7,7] converges to it (see http://mathonline.wikidot.com/the-convergence-of-the-fixed-point-method for the criterion). Since every solution is a root of ((x^2-8)^2-8)^2-8+x, which is degree 8, it follows that the roots of ((x^2-8)^2-8)^2-8+x satisfy exactly one equation of the form x=±sqrt(8±sqrt(8±sqrt(8-x))).
It remains to show that x=1+2sqrt(3)sin(pi/9) satisfies x=sqrt(8-sqrt(8+sqrt(8-x))). It is easily shown that 1+2sqrt(3)sin(pi/9) is a root of x^3-3x^2-6x+17 (trigonometric solution of casus irreducibilis) which in turn divides ((x^2-8)^2-8)^2-8+x. Therefore x=1+2sqrt(3)sin(pi/9) satisfies exactly one of x=±sqrt(8±sqrt(8±sqrt(8-x))). Finally, 1+2sqrt(3)sin(pi/9) is between 2.1 and 2.2; this numerically verifies the signs to be +,-,+. QED.
(I used WolframAlpha to cheat but I don't think I can come up with this any other way.)
By the way, I noticed that x → 8-x^2 is a one-to-one mapping on all the roots of ((x^2-8)^2-8)^2-8+x. In fact, since 8-α^2 is always in the field extension Q(α) (using field theory here), x → 8-x^2 maps each root to a root (possibly itself) with the same minimal polynomial (Edit: I messed up here, not sure how to fix it yet). Since x → 8-x^2 has period 1 or 3 for all roots (because ((x^2-8)^2-8)^2-8 = -x), and the only solutions with period 1 are roots of x^2+x-8 (the all-positive and all-negative cases), it follows that all other roots have period 3, and so must necessarily be degree 3 or 6. It happens that they are degree 3 here; this doesn't necessarily apply if the 8's are replaced by another number. In case anyone is wondering, the full factorization of ((x^2-8)^2-8)^2-8+x over the integers is (x^2+x-8)(x^3-3x^2-6x+17)(x^3+2x^2-11x-23).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I want to mention that, as you get into the tens of thousands of digits, you have to be extremely careful when talking about prime numbers. There is an ever increasing misuse of the term "prime" to mean "probable prime" (a usage I will not defend), the reason being that it takes far less computation to establish a number as a probable prime compared to actually proving that it is prime.
For example, OEIS has a list of indices of "prime" Fibonacci numbers, and the very first comment is "Some of the larger entries may only correspond to probable primes." Which means of course that the entry freely admits to making claims without proof. It would be accurate to say instead that it is a list of indices of probable prime Fibonacci numbers.
Now regarding the Numberphile video, some context. Even when checking just for probable primes, the amount of computation required to check everything up to "n equals a hundred thousand", in general, is far more than warranted for someone who is casually doing it "just to see what happens". However, there is a catch. It is possible that a primality-testing program can determine all of them to be composite in a reasonable amount of time precisely because they are all divisible by 3. Even a trial division program can achieve this (though you'd never want to use such a program to prove that a hundred thousand digit number is prime).
I still think it would be dumb to actually go through checking it up to a hundred thousand without checking beforehand that there is such an easy solution, especially since the use of primality testing tools requires a certain level of mathematical competence from the user. I think it is more likely that the people in the video are playing dumb, trying to sell 666 as superior to 616 for dramatic effect because 616 "somehow" fails to produce primes; the effect would be ruined if they said why this was the case.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I realized some time ago that for AD', all you need to do is this:
∠BAD = pi/2-B
∠BAO = (pi-∠AOB)/2 = pi/2 - C
∠DAO = ∠BAO-∠BAD = B-C
Therefore AD' = 2R cos(B-C). Similarly, BE' = 2R cos(C-A) and DF' = 2R cos(A-B).
I never bothered checking what happens if the triangle is obtuse (here O would be outside the triangle and two of D, E, F lie on extensions of the sides).
p4wn3r wrote:
The angle BDD' is the arithmetic mean of the arc angles BD' and CA.
This doesn't seem to me to be intuitive. Did you mean to say ∠BDD'+∠CDA = ∠BOD'+∠COA?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
From the triangle determined by points A, B, C the three altitudes are drawn, intersecting the opposite side at points D, E and F, and the triangle's circumscribed circle at D', E' and F'. Express the lengths of AD, BE, CF, AD', BE', CF' in terms of the triangle's angles and the circumscribed radius R.
Here A,B,C,D,E,F,D',E',F' are all the points specified in the problem. O is the circumcenter, the red circle is the circumcircle, R is the circumradius (R=|OA|=|OB|=|OC|), and the green lines are the heights of the triangle extended to the circumcircle. We use the following notation:
A=∠CAB, B=∠ABC, C=∠BCA, a=|BC|, b=|AC|, c=|AB|
From the diagram above, we have
∠COB=2A
since an angle at the center is twice the angle at the circumference subtending the same arc/chord. By cosine law:
a = sqrt(R^2+R^2-2R^2cos(∠COB)) = R*sqrt(2-2cos(2A))
Likewise:
b=R*sqrt(2-2cos(2B))
c=R*sqrt(2-2cos(2C))
With the sides now expressed in terms of R and angles of the triangle, we can now solve all of mathematics represent pretty much anything we want.
To get the heights of the triangle AD, BE, CF:
|AD| = c*sin(B) = R*sqrt(2-2cos(2C))*sin(B)
Likewise:
|BE| = a*sin(C)= R*sqrt(2-2cos(2A))*sin(C)
|CF| = b*sin(A)= R*sqrt(2-2cos(2B))*sin(A)
To get the chord along the heights AD', BE', CF':
∠D'AC=∠DAC=∠EBC (DAC and EBC are similar)
Similarly:
∠E'BA=∠EBA=∠FCA
∠F'CB=∠FCB=∠DAB
Let α=∠FCA, β=∠DAB, γ=∠EBC. Then β+γ=A, α+γ=B, α+β=C. Of the equations, adding two and subtracting one and then dividing by 2 gives:
α=(-A+B+C)/2, β=(A-B+C)/2, γ=(A+B-C)/2.
We also have:
∠D'BC=∠D'AC=γ (subtend same arc/chord)
∠AD'B=∠ACB=C (subtend same arc/chord)
∠ABD'=∠ABE+∠EBC+∠CBD' = α+2γ
That gives, by the sine law:
|AD'|/sin(∠ABD') = |AB|/sin(∠AD'B)
so
|AD'| = sin(α+2γ)*c/sin(C) = sin(A/2 + 3B/2 - C/2)*R*sqrt(2-2cos(2C))/sin(C)
Likewise:
|BE'| = sin(B/2 + 3C/2 - A/2)*R*sqrt(2-2cos(2A))/sin(A)
|CF'| = sin(C/2 + 3A/2 - B/2)*R*sqrt(2-2cos(2B))/sin(B)
Actually, there is an easier way to get |AD'|, |BE'|, |CF'|; I already knew about it but I didn't realize just how easy it was until I thought about it again. I'll let p4wn3r tell you.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
There are way too many autoscrollers in this hack, which affected my enjoyment of this TAS. Other than that, it looks good, and the music is pretty cool.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Looks like p4wn3r found the trick to Riddler Classic. The surprising result is that the expected number of communities formed depends only on the number of islands N and not on how they are connected. Here's how I did it below:
The expectation for N=1 is clearly 1-p (probability of surviving), and each additional island adds p(1-p) to the expectation regardless of which other island it is connected to (to add 1 to the community count, the newly added island must survive and the island it is joined to must be destroyed). This gives
E(N,p) = 1-p + p(1-p)(N-1).
For N=1, it is maximized at p=0, and the expectation in this case is 1. For N>1, E(N,p) can be written as
(image generated from latex2png.com)
So the maximum occurs at p=(N-2)/(2(N-1)) and the maximum expectation is N^2/(4(N-1)).
Example values for N, p which gives max expectation, and max expectation:
N=1: p=0, E(N,p)=1
N=2: p=0, E(N,p)=1
N=3: p=1/4, E(N,p)=9/8
N=4: p=1/3, E(N,p)=4/3
N=5: p=3/8, E(N,p)=25/16
N=6: p=2/5, E(N,p)=9/5
N=7: p=5/12, E(N,p)=49/24
Note that as N goes to infinity, the p at which the max expectation occurs approaches 1/2 and the corresponding expected number of communities is approximately (N+1)/4.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I figured out the trick behind this week's Riddler Classic. I'll leave the problem here in case you want to do it yourself. The problem is stated below:
Note: The links below are my doing. The problem can be reworded as a graph theory problem. The archipelago can be thought of as a tree, where we remove vertices independently with probability p and count the remaining connected components.
----
You live on the volcanic archipelago of Riddleria. The Riddlerian Islands are a 30-minute boat ride off the shores of the nearby mainland. Your archipelago is connected via a network of bridges, forming one unified community. In an effort to conserve resources, the ancient Riddlerians who built this network opted not to build bridges between any two islands that were already connected to the community otherwise. Hence, there is exactly one path from any one island to any other island.
One day, you feel the ground start to rumble — the islands’ volcanoes are stirring. You’re not sure whether any volcano is going to blow, but you and the rest of the Riddlerians flee the archipelago in rowboats bound for the mainland just to be safe. But as you leave, you look back and wonder what will become of your home.
Each island contains exactly one volcano. You know that if a volcano erupts, the subterranean pressure change will be so great that the volcano will collapse in on itself, causing its island — and any connected bridges — to crumble into the ocean. Remarkably, other islands will be spared unless their own volcanoes erupt. But if enough bridges go down, your once-unified archipelagic community could split into several smaller, disjointed communities.
If there were N islands in the archipelago originally and each volcano erupts independently with probability p, how many disjointed communities can you expect to find when you return? What value of p maximizes this number?
----
Even though it looks difficult (and Riddler is known for similar-looking problems that require computer-assisted computation), there is a trick that greatly simplifies the problem. The problem is doable on paper and no computers are required.
Tub wrote:
How was such a mundane problem deemed worthy of Wikipedia/Wolfram/OEIS pages? This is just one of many field-grazing problems. Can there be Wikipedia pages for all the problems I came up with? :D
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
OmnipotentEntity wrote:
If the numerical approximation is 1.1249976996... then the formula I have isn't too terribly bad after simplification, but you're correct that it's not invertible.
Assuming the field has radius 1, I got a value of about 1.15872847302 for the tether. I'll explain how I got this below.
Setting up the formula is actually not that hard and no calculus is required. The following diagram shows the field of radius 1, centered at (0,0), and the region that the goat eats if the tether, tied to the fence at (0,-1), has length c:
From the diagram above , the area that the goat grazes is 2*(area of light blue + area of yellow).
c = sqrt(2 - 2 cos θ) (from cosine law)
α = (1/2)(pi - θ)
Area of yellow = (1/2)θ - (1/2)(sin θ) = (1/2)(θ - sin θ)
Area of light blue = (1/2)αc2 = α(1 - cos θ) = (1/2)(pi - θ)(1 - cos θ)
Total area = (θ - sin θ) + (pi - θ)(1 - cos θ)
So we need to solve (θ - sin θ) + (pi - θ)(1 - cos θ) = pi/2. This can't be easily done, so we turn to WolframAlpha to solve it and we get:
θ ≈ 1.23589692428 (which is about 70.8 degrees)
That gives us the value of c:
c ≈ 1.15872847302.
If the field has radius R, then the length of the tether is about 1.15872847302*R
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
This week has an interesting Riddler Classic problem, a more conventional one:
----
A farmer owns a circular field with radius R. If he ties up his goat to the fence that runs along the edge of the field, how long does the goat’s tether need to be so that the goat can graze on exactly half of the field, by area?
----
Shouldn't be too hard to figure out.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
August 2018 rankingsSeptember 2018 rankings
Sorry for being late on Aug. 2018 rankings; I have a lot of stuff going on in my real life now. I wrote up both these rankings very quickly (which took me about 2.5 hours), so some things may be off in my translation.
MUGG wrote:
11~7
You see, Dr. Mario just won't go away. What's funny is that 4 of those 5 videos are a chain of Dr. Mario videos obsoleting each other, with the last one having the very creative name that's basically '"'"Dr. Mario - challenge to do greatest chain clear" improved' improved" improved' (no points for guessing what the other 3 titles were like).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I had no idea Doppler Attack was this broken.
I like this one more than the Rockman version. Too bad that the intro boss takes forever to beat with Forte.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Cool that you managed to break a 2nd gen Pokemon game this quickly. I admit though that it didn't really surprise me. It was just a matter of time after all.
What I found very interesting is that you cleared memory to make it "legit". And yet you managed to break the game anyway (a legit SRAM makes it harder to break). Also, naming the boxes as well as the player in order to get a checksum collision (which is two bytes in 2nd gen, as opposed to just one byte in 1st gen). You have a good understanding of how memory works in this game.
You mentioned realigning something (frame boundaries or something) in order to get the perfect frame reset. I wonder whether getting the frame reset would be easier to do in lsnes, since that emulator allows you to frame reset at opcode precision.
I admit that a lot of the 1st gen save corruption TASes abuse uninitialized SRAM (all FFs). This is the one crucial step in glitching the game to think you have 255 Pokemon so you can use the menu to corrupt more memory. Unfortunately, that technically means that:
- these two published runs,
- every one of the TASes they obsoleted (other than the JPN door glitch ones),
- all related submissions, and
- all the save corruption work we did,
are all invalid.
Though it doesn't personally affect me that much; after all that is the price to pay for breaking Pokemon to this extent. I found out about this ever since I tried to figure out exactly why memory was being filled with FFs during the glitch. What gets me the most is not that my TASes are invalid, but that as far as I know, in the 8 or so years that this category had been extensively studied, nobody made any attempt to raise this issue.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
OK, now a harder problem. A classic from Gauss.
You start with a0 = a and b0 = b.
At every step you perform the operation
an+1 = (an+bn)/2
bn+1 = sqrt(anbn)
That means, you change the two initial real numbers by their arithmetic and geometric means. Prove that this procedure converges to a value 1/L, where ...
I will assume for the rest of this post that a and b are positive real numbers.
After thinking about this for a while, I could only prove that they converge to a value, but I couldn't prove what they converge to. But since there is a whole Wikipedia page about this, I'll just link it here as the solution. The value is called the arithmetic-geometric mean.
What if we replaced a and b with their arithmetic and harmonic means? That problem is much easier to figure out. Their arithmetic mean (AM) is (a+b)/2 and their harmonic mean (HM) is (((1/a)+(1/b))/2)^(-1), which simplifies as 2ab/(a+b). When you multiply the AM and HM together, you get ab, which is the same as the product of the original numbers. Therefore the product of the two numbers on the board is always the same at every step. Since they converge to a value L (check this), the value L must satisfy L^2=ab, and so L=sqrt(ab). Note that L is the geometric mean!
What if we replaced a and b with their geometric and harmonic means? Note that the geometric mean (GM) of a and b is the reciprocal of the GM of 1/a and 1/b. As well, the HM of a and b is the reciprocal of the arithmetic mean of 1/a and 1/b. Thus we just find the arithmetic-geometric mean of 1/a and 1/b, then take the reciprocal to get the answer.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
You write all numbers from 1 to 100 on a blackboard. At any point you can choose any distinct numbers a and b, erase them and write a+b+ab on the blackboard. After doing this process 99 times, which number will be left on the blackboard?
Let a＊b = a+b+ab be the operation. Note that a＊b = (a+1)(b+1)-1. Then
(a＊b)＊c = ((a+1)(b+1)-1)＊c = (a+1)(b+1)(c+1)-1 = a＊((b+1)(c+1)-1) = a＊(b＊c)
and
a＊b = (a+1)(b+1)-1 = (b+1)(a+1)-1 = b＊a
So ＊ is associative and commutative, and so we can apply this operation on any numbers in any order and get the same result.
So:
1＊2＊3＊...＊100 = (2(3)-1)＊3＊4＊...＊100 = (2(3)(4)-1)＊4＊5＊...＊100 = ... = 2(3)(4)(5)...(101)-1 = 101!-1.
The number at the end will always be 101!-1, which is the 160-digit number:
9425947759838359420851623124482936749562 \
3127947025437683278893534169775993162214 \
7650308786159180834691162349000354959958 \
3369706302603263999999999999999999999999
Alternatively, the value resulting from adding one to every number on the board and then multiplying them all together is an invariant (is always the same at every step) that in this case equals 101!; thus when there is one value left, it must be 101!-1. It's a similar idea.
Warp wrote:
Suppose that using some benchmark, graphics card A runs at an average of 120 frames per second, while graphics card B runs at 150 frames per second.
...
So, is card B "25% faster" or "20% faster" than card A? Or something else?
There is another issue when using the word "faster".
For the most part, it is understood to compare the speeds of the graphics cards in frames per second. 150 fps is 25% more than 120 fps, so in this sense card B is 25% faster than card A.
However "faster" is often conflated with "takes less time than" (i.e. the comparison is based on time and not speed). Using your example, card A runs 600 frames in 5 seconds, card B runs 600 frames in 4 seconds. Since 4 is 80% of 5, card B takes 20% less time than card A, so in this sense one could also claim that card B is "20% faster" than card A.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
If you want the probabilities, Riddler Express can be modelled using an absorbing Markov chain.
If we call the first team (HT) Team 1 and the second team (HH) Team 2, then there are four transient (non-final) states:
OO = neither team can win on next flip
HO = Team 1 can win on next flip but not Team 2
OH = Team 2 can win on next flip but not Team 1
HH = Both teams can win on next flip
and two absorbing (final) states:
1W = Team 1 has won
2W = Team 2 has won
You can set up an absorbing Markov chain and compute the final probabilities of ending up in 1W and 2W starting from OO.
Alternatively, you can also compute: if poo is the probability of Team 1 winning starting from OO, and so on, then:
(image generated from latex2png.com)
Computing gives poo=5/8. So probability of Team 1 winning is 5/8 and for Team 2, 3/8.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
Maybe I'm not understanding the issue here. At least from my perspective, finding the recurrence relation is harder than finding the generating function. If you already have the relation, why not simply compute the numerator from the initial conditions and substitute the dominant root to find the residue?
Sorry, I misunderstood your posts and thought you were asserting that finding the recurrence relation and using a computer to calculate f(1), f(2), ..., f(15000) from this relation was, in and of itself, the solution to the problem. It's because I was unable to figure out what exactly you wanted from your posts.
You probably know me as a stickler in some of my posts around here. Perhaps the proof could be made more concise and complex analysis is not necessary. The reason I went through my reasoning in detail is because I wanted to understand certain aspects of the problem, such as why the residues/coefficients are why they are and how we know the dominant root near 2 is indeed the dominant root, with all other roots less than 1 in absolute value, without accepting it blindly. So it was partially for my understanding of the problem.
If it is just a matter of using an algorithm to compute the numerator, without worrying about proof, then almost all of my post is unnecessary; just using the final answer that I posted is sufficient.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
I was thinking of something like
F(z) = 1 - z + 2zF(z) - z16F(z)
You can substitute the Taylor expansion for F, shift the coefficients, compare the z^n terms and find the relation.
You can find the recurrence relation this way. That is, f(n)=2f(n-1)-f(n-16) when n≥16, and f(0)=1 and f(n)=2^(n-1) when 1≤n≤15. (The sequences I defined other than the empty sequence at n=0 must end with a tails.)
However, because OmnipotentEntity specifically asked whether there were exact formulas that were "not recursive" (i.e. not in the form of a recurrence relation), I decided to do a full analysis of it. Of course, since there are only 15000 flips, you could use a computer to compute it (which is how I suppose OmnipotentEntity wrote down the exact answer here), but I wanted to see if there was a reasonable way at least to estimate it in general in case someone asks "Well what about 15000000 flips? 15000000000?".
To add to this, while it is possible to get recurrence relations from generating functions, for the purpose of finding recurrence relations I would avoid generating functions and prove it directly. In this case, it is very easy to prove that f(n)=2f(n-1)-f(n-16) when n≥16, and f(n)=2^(n-1) when 1≤n≤15, assuming you define f(0)=1.
By the way, my previous post had a broken image link which I fixed. The roots of the characteristic r^16-2r^15+1 are now shown properly in the image:
Edit:
p4wn3r wrote:
Alright, I thought a bit about the problem and it's much simpler than you guys think. ...
Yes, I knew all of this already, in case none of what I posted previously clearly indicated that this was so.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
Can't you find a recurrence relation for the coefficients of z^n on F(z) instead of using complex analysis? Normally if you play with the generating functions you can derive differential equations between them, which translate to recurrence formulas.
I thought about solving it with the normal recurrence method (which is similar to the differential function method). You can easily find a recurrence characteristic of r^15-r^14-r^13-...-r-1 (or alternatively r^16-2r^15+1) which gives the form f(n) = sum[α]( Cα * α^n ) over all roots α of r^15-r^14-r^13-...-r-1, where the Cα are constants that need to be found. Note that these roots are not the roots of 1/F(z) in my previous post, but the reciprocal of them.
However, because r^15-r^14-r^13-...-r-1 (or r^16-2r^15+1) can't seem to be factored algebraically, I wasn't able to figure out the constants Cα using the normal linear equation method on the initial conditions (since you need to know the roots α for that). The values should turn out to be the residues from my above post but there doesn't seem to be a way to know that with the normal recurrence method. That is one reason why I favored the complex analysis approach.
The other reason is that to get the asymptotic behavior of f(n), you need to know the root of r^15-r^14-r^13-...-r-1 which is largest in complex absolute value, so that it dominates all the others. The largest one is a real number near 2 (about 1.9999694754, precisely the reciprocal of the ζ in my previous post) and the others are within the unit disk (|z|<1). Although WolframAlpha can verify this for the particular case h=15 (as in the image below), and seems to indicate that this is true for all sufficiently large h, I wanted to find a proof that this works, and Rouché's theorem was the only way I could find to do this.
OmnipotentEntity wrote:
From here the recurrence is simply:
C(f+1,h) = 2 * C(f,h) + ~C(f-(h+1), h)
Do you mean C(f+1,h) = 2 * C(f,h) + ~C(f-h, h)? This one instead would agree with your calculation C(6,2) = 2 * C(5,2) + ~C(3, 2) when f=5, h=2.
OmnipotentEntity wrote:
So we can say:
C(f, h+1) = (C(f, h) - ~C(f-h, h))/2
Some of my calculations don't seem to agree with this.
For example:
C(4,2)=8 (HHHH HHHT HHTH HHTT THHH THHT HTHH TTHH)
C(4,1)=15 (everything but TTTT)
~C(3,1)=1 (TTT)
8≠(15-1)/2=7
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
OmnipotentEntity wrote:
What is the probability that if I flip 15000 coins, at least 15 consecutive heads appears at least once.
Reminds me of the recent Riddler Classic problem on "Riddler Rugs", where you find the probability of finding a 4x4 same-color square within a 100x100 patch rug. However, the Riddler Rugs problem, being two-dimensional, only has inexact estimates based on inclusion-exclusion-type arguments, whereas the coin flip problem, which is one-dimensional, can be solved exactly.
It would be easier to consider the opposite probability; that is, the probability that in a sequence of 15000 flips, there is not a subsequence of 15 (or more) consecutive heads. In addition, we will add an additional tails to the end of the sequence; this does not affect whether there is a subsequence of 15 consecutive heads. Let f(n) be the number of such sequences of length n with no subsequence of 15 consecutive heads, and the sequence ending in a tails (*). The probability would then be f(n+1)/2^n.
The set B={T, HT, HHT, HHHT, ... , HHHHHHHHHHHHHHT}, the "atomic elements", are possible sequences of 0 to 14 heads terminated by a tails; B has generating function (by length) G(z) = z + z^2 + z^3 + ... + z^15. Then the elements of B construct all possible sequences (*), using any number (zero to many) of elements in any order. The generating function F(z) of f(n) is then:
F(z) = 1+G(z)+G(z)^2+G(z)^3+... = 1/(1-G(z)) = 1/(1-z-z^2-...-z^15) = (1-z)/(1-2z+z^16).
How to get z^n coefficient from F(z): We write F(z) in its partial fraction decomposition using residues. Because the roots of 1/F(z) are all simple (check this from the GCD of 1-2z+z^16 and its derivative), we can write:
F(z) = sum[α]( (lim[z→α](z-α)F(z)) * (1/(z-α)) )
where the sum is over all roots of 1/F(z). However, 1-z-z^2-...-z^15 (and 1-2z+z^16) apparently cannot be factored algebraically, so we use L'Hôpital's rule on the limit when F(z) is in the form (1-z)/(1-2z+z^16):
F(z) = sum[α]( ((1-α)/(16α^15-2)) * (1/(z-α)) ) = sum[α]( ((α-1)/(α(16α^15-2))) * (1/(1-α-1z) ).
The z^n coefficient is: sum[α]( ((α-1)/(α(16α^15-2))) * (α-1)^n ) (**).
About the roots of 1/F(z): They are all roots of 1-2z+z^16. One of the roots is a real number ζ very close to 0.5 (ζ≈0.500007631258) and the others lie just outside the complex unit disk in the annulus 1<|z|<1.2. The fact that ζ is the only root inside the unit disk, and the others have a complex absolute value between 1 and 1.2 can be proved using Rouché's theorem; I'll leave it to you to figure out.
So when α is a root other than ζ, since 1<|α|<1.2, we can bound its term in (**) by |((α-1)/(α(16α^15-2)))*(α-1)^n| < 1/70. Therefore the terms other than the one for ζ don't even add up to 0.5. This immediately gives us:
f(n) is the nearest integer to ((ζ-1)/(ζ(16ζ^15-2))) * (ζ-1)^n ≈ 0.5001068621 * 1.9999694754 ^ n.
(approximate because you need thousands of digits of ζ to calculate it exactly)
The probability of no subsequence of 15 consecutive heads is f(n+1)/2^n. For n=15000, that would be about 0.7955373. The probability of at least 15 consecutive heads at least once is one minus this, or about 0.2044627, which agrees with OmnipotentEntity.
OmnipotentEntity wrote:
I have a method of finding an explicit formula in f for a given h. But I don't know how to extend it to an arbitrary h.
The method above would be pretty similar for arbitrary h. You would find the real root ζ of 1-2z+z^(h+1) near 0.5, then compute f(n)=((ζ-1)/(ζ((h+1)ζ^h-2))) * (ζ-1)^n, and the probability would be f(n+1)/2^n.
ζ can be computed by Newton's Method on x^(h+1)-2x+1 starting with 0.5. The first iteration gives 0.5 + 1/(2^(h+2)-2h-2) which is already a very good approximation to ζ.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Hello Soig. I haven't had time to see the run, but it's good that you are still improving New Super Mario Bros.
By the way, 浮点数 is translated as "floating point" in English. "Fixed point" means something different; it would be translated as 定点数 in Chinese.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Someone asked about how the Nicovideo monthly ranking works, so I'll do my best to explain.
----
To qualify for this ranking, the video must:
- be uploaded during the month (Japan time),
- be relevant to TAS, and
- not be a compilation video or repost.
If multiple videos uploaded in the same month are "part of the same TAS", at most one of the videos can qualify for the ranking.
----
Each video is ranked by number of points on the 6th of the next month at midnight (Japan time) as follows:
Points = Views + Comments + (20 x Mylists)
(note: The comment count and comments only appear if you go to the bottom of the page and set Region/地域 to Japan/日本 and Language/言語 to Japanese/日本語)
----
The ranking lists the top 30 ranked TAS videos as well as 10-12 other TAS videos (called "Pickups") of the organizer's choice. A small snippet of the video is shown, along with information such as title, author, points, rerecord count (if available), Nicovideo tags, and such. The monthly ranking video appears approximately by the 10th of the next month.
It is generally expected that the community gives a TAS video the "TAS" tag to make it easier to find.
There is also a Nicovideo yearly ranking which runs on a similar idea but is bigger.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Warp wrote:
But now enters the color photography using color filters problem: We have a monochromatic camera, and we take three photos with it, with a red, a green and a blue filter, and we combine them and we get a color photograph.
And violet colors show up just fine! How?
I assume that by "violet colors" you are referring to violet light (400-440nm) and not digital (or otherwise) renderings of purple colors.
Actually, it depends on the colors that the filters let through (since the red/green/blue filters only form an approximation when combined together). Perhaps violet colors show up just fine because the "blue" filter is actually closer to violet than it first appears (maybe it filters 400-440nm light, rather than the 470-500nm that is typical of blue). Or maybe the blue filter allows a wider range than it appears at first glance.
Warp wrote:
It is my understanding that this is because the frequency of violet is twice that of (low) red, and there's a resonance effect going on
p4wn3r wrote:
When it receives violet, the blue cone is stimulated because its frequency is not far below violet, and the red one as well, since it's stimulated by the second harmonic
I've never heard of a resonance effect or harmonic for electromagnetic waves before, but I don't know about it. I only know about resonance and harmonics in sound waves (e.g. vibrating string).
The typical human sees color using three cones, often called "red", "green", and "blue". The typical sensitivities of the cones are shown in the image below, taken from the Color vision page on Wikipedia:
In this model, violet light mostly stimulates the blue cone, compared to the red and green cones. Note that the peak of the blue cone is in the violet range. I have seen some other models where the red cone stimulation actually increases in the violet range, but I don't know if they are accurate or not. Searching the internet reveals that there is a disagreement in this area.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
July 2018:
Link to videoRanking in detail. Dr. Mario scores a 19-hit combo! Apparently, there was a crazy frame war, and yes, there were even more Dr. Mario videos not included in the ranking.
I realized some time ago that for AD', all you need to do is this:
∠BAD = pi/2-B
∠BAO = (pi-∠AOB)/2 = pi/2 - C
∠DAO = ∠BAO-∠BAD = B-C
Therefore AD' = 2R cos(B-C). Similarly, BE' = 2R cos(C-A) and DF' = 2R cos(A-B).
I never bothered checking what happens if the triangle is obtuse (here O would be outside the triangle and two of D, E, F lie on extensions of the sides).
(image generated from latex2png.com)
So the maximum occurs at p=(N-2)/(2(N-1)) and the maximum expectation is N^2/(4(N-1)).
Example values for N, p which gives max expectation, and max expectation:
N=1: p=0, E(N,p)=1
N=2: p=0, E(N,p)=1
N=3: p=1/4, E(N,p)=9/8
N=4: p=1/3, E(N,p)=4/3
N=5: p=3/8, E(N,p)=25/16
N=6: p=2/5, E(N,p)=9/5
N=7: p=5/12, E(N,p)=49/24
Note that as N goes to infinity, the p at which the max expectation occurs approaches 1/2 and the corresponding expected number of communities is approximately (N+1)/4.
From the diagram above , the area that the goat grazes is 2*(area of light blue + area of yellow).
c = sqrt(2 - 2 cos θ) (from cosine law)
α = (1/2)(pi - θ)
Area of yellow = (1/2)θ - (1/2)(sin θ) = (1/2)(θ - sin θ)
Area of light blue = (1/2)αc2 = α(1 - cos θ) = (1/2)(pi - θ)(1 - cos θ)
Total area = (θ - sin θ) + (pi - θ)(1 - cos θ)
So we need to solve (θ - sin θ) + (pi - θ)(1 - cos θ) = pi/2. This can't be easily done, so we turn to WolframAlpha to solve it and we get:
θ ≈ 1.23589692428 (which is about 70.8 degrees)
That gives us the value of c:
c ≈ 1.15872847302.
If the field has radius R, then the length of the tether is about 1.15872847302*R
(image generated from latex2png.com)
Computing gives poo=5/8. So probability of Team 1 winning is 5/8 and for Team 2, 3/8.
Edit:
In this model, violet light mostly stimulates the blue cone, compared to the red and green cones. Note that the peak of the blue cone is in the violet range. I have seen some other models where the red cone stimulation actually increases in the violet range, but I don't know if they are accurate or not. Searching the internet reveals that there is a disagreement in this area.