Looks correct to me (though note that a "pattern" would mean any periodically repeating sequence). I don't know whether there is an intuitive explanation that doesn't involve using the diagonal argument, and I suspect there wouldn't be because the diagonal itself is involved in the statement of the claim.
Actually when I thought about it afterwards, the answer is much, much simpler than I thought. I'm in fact a bit embarrassed of not realizing it pretty much immediately, as it's pretty trivial.
The reason why 0.12345678901234... is not in the list is because it simply cannot be added to the list due to the constraint of the diagonal. There is no place in the list where you could add it without it breaking the rule imposed on the diagonal.
After all, the constraint is "the first digit (after the decimal point) must be 0, or the second digit must be 1, or the third digit must be 2, ..., or the 10th digit must be 9, or the 11th digit must be 0, or the 12th digit must be 1, ..." and so on and so forth, and that number doesn't fulfill that constraint anywhere. (And it's rather easy to prove that there are infinitely many rational numbers that don't fulfill that constraint.)
On the other hand, this leads to the semi-interesting fact that it's impossible to list the rational numbers in a manner that the diagonal of their decimal representation would be a rational number. Or, in other words, no matter how you reorder the list of rationals, the diagonal will always form an irrational number.
Apologies in advance for my lack of LaTeX.
The sum is equal to
1/(n-2020) + 1/(n-2019) + ... + 1/n + 1/(n+1) + ... + 1/(2n) + 1/(2n+1) + ... + 1/(2n+2020)
= 1/n + 1/(n+1) + ... + 1/(2n) + other terms
The 'other terms' is a finite series of fixed length and each term goes to 0 as n goes to infinity. Hence the original sum is equal to the limit of S(n) = 1/n + 1/(n+1) + ... + 1/(2n)
This is bounded below by the integral of 1/x from n to 2n+1, which is log(2+1/n) and bounded above by the integral of 1/(x-1) from n to 2n+1, which is log(2n/(n-1)) = log(2 + 2/(n-1))
So log(2 + 1/n) < S(n) < log(2 + 2/(n-1))
Hence S(n) tends to log(2) by the squeeze theorem.
We know that the sum of the first n terms of the harmonic series is given by:
Hn = ln(n)+γ+O(1/n)
where γ is the Euler-Mascheroni constant, and since the O(1/n) terms go to 0, we have:
lim[n→∞] sum[ i=n-2020 to 2n+2020 ] (1/i)
= lim[n→∞] ln(2n+2020)+γ) - (ln(n-2020)+γ)
= lim[n→∞] ln(2n+2020) - ln(n-2020)
= lim[n→∞] ln( (2n+2020)/(n-2020) )
= ln( lim[n→∞] (2n+2020)/(n-2020) )
= ln(2)
Do you like the harmonic series?
Of course. The reason I tend to post problems like this, though, is that I seem to get a lot more engagement from you guys with these a la Euler questions, which involve algebraic manipulation of expressions. I like them, too. But they become rather simple once you have enough experience, so these days I am tending more towards more abstract stuff.
All parabolas are similar. This means that you can take any parabola and by simply rotating it, flipping it, translating it and scaling it equally in all directions, you can map it exactly on any other parabola.
I was wondering if there's a name for those allowed transformations. (They are not affine transformations because those allow uneven scaling.)
I recently go the idea: Suppose you needed to represent a particular permutation of all the integers between 1 and 100 in a binary data file for example. What is the smallest space you can squeeze this data into (regardless of what permutation it is, ie. we are looking at the worst case scenario here, ie. no permutation will ever take more than this much space.)
Obviously you could just store one byte per value, which would take 100 bytes. Also likewise obviously this is very wasteful because there's a lot of unused numeric representation being wasted here.
The next idea is to store it, essentially, as a "base-100" number. In other words, we store them as values in the range 0-99 (inclusive), we take the first number, multiply it by 100, add the second number, multiply the entire thing by 100, add the third number, and so on until the last number has been added. This takes ceil(log2(100^100)) = 665 bits (ie. a bit less than 84 bytes).
But this isn't the best we can do either. After all, once we have listed 99 numbers we don't need to list the final one because there's only one possibility. We need only 658 bits for this (which fit in 83 bytes).
But wait, there's still more. We still have too much unused space. After all, once the first number has been given, there are only 99 other numbers that can come next. Since this is a permutation, the same number cannot come again. Thus we can reduce the range by one after each number. (So, for example, if the first number given was 60, the next one will be taken as-is if it was less than 60, and incremented by one if it's 60 or larger. Then the next number would be incremented by 0, 1 or 2 depending on which range it's in, and so on.)
In other words, we take the first number, multiply it by 99, then the second number, adjust it as necessary and add it, then we multiply the result by 98, take the third number, adjust it as needed and add it, and so on and so forth.
How many bits does the list take now?
Is there a way to still make it smaller?
All parabolas are similar. This means that you can take any parabola and by simply rotating it, flipping it, translating it and scaling it equally in all directions, you can map it exactly on any other parabola.
This particular subset of transformations does not, as far as I am aware, have its own special name. They are the subset of the affine transformations such that the translation matrix has orthogonal eigenvectors. This does include rotations, because a parabola rotated is still a parabola, it's just not expressible as a second degree polynomial in x.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
The entropy of a permutation of n elements is log_2(n!), which for n = 100 is 524.765... (assuming uniform probability of each elements)
So an easy lower bound is 525 bits.
It is definitely possible to simply assign each permutation of 100 elements to a unique 525 bit value without regard to ease of algorithmic implementation, so this lower bound is achievable in principle.
As for your technique, I programmed it in python to test whether it covered the entire integer range [0, n!-1] and it does.
def encode(list):
res = 0
seen = []
for i,mem in enumerate(list):
res += mem - sum(1 for i in seen if i < mem) - 1
res *= (len(list) - i - 1) or 1
seen.append(mem)
return res
Which gives:
>>> [encode(i) for i in itertools.permutations([1, 2, 3, 4)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]
>>> [encode(i) for i in itertools.permutations([1, 2, 3, 4, 5])]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119]
This isn't a proof, but your encoding seems to be optimally dense, so you should be able to reach 525 bits.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
All parabolas are similar. This means that you can take any parabola and by simply rotating it, flipping it, translating it and scaling it equally in all directions, you can map it exactly on any other parabola.
I was wondering if there's a name for those allowed transformations. (They are not affine transformations because those allow uneven scaling.)
A similarity transform is a little bit too restrictive. It doesn't allow for stretching in either the x or y direction.
As for the tan(x) > x question, it was the subject of a recent Stand Up Maths video. The answer is given here. And the number itself is 1,169,809,367,327,212,570,704,813,632,106,852,886,389,036,911
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
It's not very hard to see why it should be huge.
We're basically looking for crossings of the graph x with tan(x). For large values of x, we can approximate the graph of tan(x) by vertical lines at (n+1/2)*pi. So, we want (n+1/2)*pi to be pretty close to an integer. So, essentially, we need to compute rational approximations to pi, hoping we hit a prime number. The thing is, the better the approximation is, the larger the denominator, and the smaller the probability of the number being prime, since it falls with 1/log(n). But because log(n) grows very slowly, it's not unlikely that you will find one.
To calculate this number, one probably needs to use some assymptotics from trigonometry and number theory to make what I said rigorous, until you can prune the search enough to hit the prime number. It looks like a lot of work, but doable.
(Incidentally, the recent advances in number theory, like the proofs that there are infinitely many pairs of consecutive primes with gap smaller than a finite quantity, weak Goldbach, the proof of the Duffin-Schaeffer conjecture, etc., all came from clever combinatorics arguments that made rigorous many statistical estimates. Although the most spectacular application is to number theory, they all work in settings like dynamical systems, and hypergraphs, which do not encode any number theoretic information at all!)
I was able to find it myself: tan(x) > x 1169809367327212570704813632106852886389036911
I didn't give a proof though. Thus, I don't yet belive that it's smallest.
I was only checked everything up to 10^12 I guess (because precision loss may have issues, need to recheck). Everything beyond is under question.
Here is how I checked everything up to 10^12 (precision issues put aside).
I built up to MAXT = 10^7 remainders of whole numbers by pi. Then, iterating over segments of size MAXT:
[0, MAXT-1], [MAXT, MAXT*2 - 1]...
knowing that every number in the segment is beginning of segment + i from range 0 to MAXT-1, this means that I need to find number that has remainder close to pi/2, so I need to find:
beginning + x = pi/2 (mod pi)
rearranging you have x = pi/2-beginning (mod pi)
then you do binnary search and you find closest to pi/2 value.
Then because you have everything sorted, you just need to iterate from it downwards and search while tan(x) is greater that beginning of range.
Here is the code: https://gist.github.com/realmonster/fa760625327db51528bc32c69fc6afad
It works up to 3083975227, even though tan values are wrong. Next number that it shows is 45190661509 is wrong because of wrong tan. And, because I have issues with precision of tan(), I did change it to gmp and it was able to find next one 902209779836. Which is approximately 9*10^11 (almost 10^12).
I let it to search until 9*10^18 (approximate limit of int64) because I didn't know how far we go. I don't show code because it's mess.
And, parallely I tried to use idea that it's closest to pi/2 but disregarding any other numbers that also may be close. So I represented equation as follows:
n - pi/2 -> m*pi
(where -> means tending to, close to)
rearrange
n - pi/2 - m * pi -> 0
enclose into brackets
n - pi*(1/2 + m) -> 0
n -> pi*(1/2 + m)
divide
n/(1/2 + m) -> pi
multiply numerator and denominator by 2:
2n/(1 + 2m) -> pi
Then, I used so called Stern–Brocot tree which I learned recently (few months ago).
And using it, I was generating all rations close to pi.
Then I was filtering only fractions that has even numerator and odd denominator. Then comparing n to tan(n) and output list of numbers. First prime among them was 1169809367327212570704813632106852886389036911.
How did I check for primes? I was using numberempire site. Also then verified by "is 1169809367327212570704813632106852886389036911 prime?" query on wolphram alpha. I have no idea how to verify it in other way.
Source of solution with tree: https://gist.github.com/realmonster/c423b6a160dc34422653b12db9e51f85
run it with input 1000 1000
First number is precision, second number is number of fractions. I put output of it also there.
Now, the issue: It doesn't check any 2n/(2m+1) non-closest to pi fraction. Or may be I don't understand something. In other words: why you shouldn't search in fractions that are in same level of tree but a bit more left / right? This fraction is closest, but its numerator is bad (not prime) or wrong parity of numerator denominator, why not to check other? I don't know.
A similarity transform is a little bit too restrictive. It doesn't allow for stretching in either the x or y direction.
I assumed that Warp was referring to uniform scaling, based on what was said:
Warp wrote:
All parabolas are similar. This means ...
Warp wrote:
... scaling it equally in all directions ...
Warp wrote:
(They are not affine transformations because those allow uneven scaling.)
"scaling it equally in all directions" I assumed meant uniform scaling.
"uneven scaling" I assumed meant stretching x and y by unequal factors.
Edit: Also, I'm pretty sure that if you have uneven scaling together with all the isometries (rotation, reflection, translation), that is enough to give you all the affine transformations. So that probably explains why there isn't a special name for "similarity transformations plus uneven scaling", because that just gives you the affine transformations.
Also, I'm pretty sure that if you have uneven scaling together with all the isometries (rotation, reflection, translation), that is enough to give you all the affine transformations. So that probably explains why there isn't a special name for "similarity transformations plus uneven scaling", because that just gives you the affine transformations.
Yeah, this is definitely true.
I assumed that Warp was referring to uniform scaling, based on what was said:
I don't think your interpretation is wrong or anything. Just Warp's wording was technically wrong, but I thought I knew what he meant. All parabolas are not "similar." For instance y=x^2 and y = 1/2 x^2 are not technically similar, but they are related by an uneven scaling.
When I had written my last post I thought that It may be the case that "parabolaness" is preserved under all (non-degenerate) affine transformations, but when I attempted to prove it I wound up with a complete mess of coefficients while trying to massage it into the general conic section form: A x^2 + B xy + C y^2 + D x + E y + F = 0
I eventually managed today:
(Click for larger)
The last is sufficient to prove it's a parabola (because A x^2 + B xy + C y^2 is the square of a linear polynomial). The only caveat is that the coefficient C_2 contains a factor of 1/(a'b'' - a''b') which is proportional to 1/det A. Hence the requirement for non-degeneracy.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
How did I check for primes? I was using numberempire site. Also then verified by "is 1169809367327212570704813632106852886389036911 prime?" query on wolphram alpha. I have no idea how to verify it in other way.
WA probably used a probabilistic primality checker. So I double-checked it with cado-nfs. It's prime. It only took about half a minute to factor.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
For instance y=x^2 and y = 1/2 x^2 are not technically similar, but they are related by an uneven scaling.
y=x^2 and y=x^2/2 are similar; scaling the graph of y=x^2 uniformly by a factor of 2 gives the graph of y=x^2/2.
(It is also true that they are related by an uneven scaling, but that is beside the point.)
OmnipotentEntity wrote:
When I had written my last post I thought that It may be the case that "parabolaness" is preserved under all (non-degenerate) affine transformations, but when I attempted to prove it ...
Yes, "parabolaness" is preserved under all (bijective) affine transformations; a parabola remains a parabola when you apply uneven x/y scaling or any isometry (rotation, reflection, translation), and since those operations generate the affine transformations, a parabola remains a parabola under any affine transformation.
Yes, "parabolaness" is preserved under all (bijective) affine transformations; a parabola remains a parabola when you apply uneven x/y scaling or any isometry (rotation, reflection, translation), and since those operations generate the affine transformations, a parabola remains a parabola under any affine transformation.
If applying an affine transformation (which may include uneven scaling) to a parabola gives another parabola, and given that all parabolas are similar (something that can be proven with a bit of elementary algebra), that ought to mean that any affine transformation done to a parabola can be replaced with a similarity transformation that gives the exact same resulting parabola. Is that so?
Is there a formula or algorithm to deduce the equivalent similarity transformation from a given affine transformation?
Ok, I have a rather serious math question that I only barely know how to formulate, and I have no idea how to attack.
Given a complete graph $K_{2n}$, how many ways are there to partition its edges into $2n-1$ distinct perfect matchings?
Lay explanation:
If you have 2n people, and each round they pair off and shake each other's hands, how many ways can you do this and still have it such that after 2n-1 rounds everyone has shaken everyone else's hand exactly once?
The ordering of rounds is unimportant, because it's trivial to generate one from the other simply using a permutation.
The ordering of the people is also unimportant, because it is again trivial up to a permutation on the first hand shake.
Small examples:
For 2 there's only one round and it's AB So there is a total of one possibility.
For 4, the first round is fixed at AB CD, next AC and BD, then AD BC. Because there are no other possible choices to make at any juncture, there is a total of only one possibility.
For 6, the first round is fixed at AB CD EF, wlog (due to permutations) we can fix the selection of the edge containing A at each round, (AB, then AC, then AD, and so on) For the second round AC leaves us with two valid choices. We can choose either the edge BE or the edge BF (BD cannot be chosen because we have already used the edge EF in the previous partition. From these two choices we are forced into the following two patterns:
Option 1 | Option 2
AB CD EF | AB CD EF
AC BE DF | AC BF DE
AD BF CE | AD BE FC
AE BD CF | AE BC DF
AF BC ED | AF BD CE
So for 6 there are two distinct ways to select these edges.
For 8 it becomes somewhat difficult to keep track of the possibilities with pen and paper, and I haven't yet felt up to programming something up to crunch through the possibilities.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Yes, "parabolaness" is preserved under all (bijective) affine transformations; a parabola remains a parabola when you apply uneven x/y scaling or any isometry (rotation, reflection, translation), and since those operations generate the affine transformations, a parabola remains a parabola under any affine transformation.
If applying an affine transformation (which may include uneven scaling) to a parabola gives another parabola, and given that all parabolas are similar (something that can be proven with a bit of elementary algebra), that ought to mean that any affine transformation done to a parabola can be replaced with a similarity transformation that gives the exact same resulting parabola. Is that so?
Is there a formula or algorithm to deduce the equivalent similarity transformation from a given affine transformation?
Wikipedia's page on parabolas gives the expression for the vertex and focus of the parabola obtained by transforming the unit parabola using a given affine transformation. The vertex and focus of the unit parabola are (0,0) and (0,1/4) respectively, so all that is required now is to solve for the similarity transformation for those two points, which is relatively straightforward.
Wikipedia's page on parabolas gives the expression for the vertex and focus of the parabola obtained by transforming the unit parabola using a given affine transformation. The vertex and focus of the unit parabola are (0,0) and (0,1/4) respectively, so all that is required now is to solve for the similarity transformation for those two points, which is relatively straightforward.
Nice! I was trying to figure out how to get either of the two (there are two of them; one is a reflection of the other) similarity transformations from the affine transformation but couldn't quite figure it out.
By the way, the reasoning I gave for a parabola being a parabola under affine transformation is wrong; I assumed that it would hold for compositions of the transformations if it held for each transformation, which is wrong reasoning. After all, a rectangle remains a rectangle under the transformations I gave, but a rectangle is no longer a rectangle under a skew transformation.
For 2n=8 it becomes somewhat difficult to keep track of the possibilities with pen and paper, and I haven't yet felt up to programming something up to crunch through the possibilities.
I tried to write something down with pen and paper for 8, and it becomes quite a monstrosity. There's a lot of branches, and except one the few I tried all died. It's just very hard to see whether a suggested branch will die off rounds later without trying. In the end, I would not be surprised to see that there are 3 unique ways, and that for every step you increase n, the answer is the nth number in the fibonacci sequence (with n = (1,2,3) the #ways are (1,1,2) after all). But that is a wild guess.
Edit: obviously, thanks to r57shell, I was all wrong. I tried to find the specific ways voor 6, and that worked out, but that was already quite difficult to keep organised.
Given a complete graph $K_{2n}$, how many ways are there to partition its edges into $2n-1$ distinct perfect matchings?
I wrote brute force for your interpretation, and got for n = 4 is 416, and for n = 5 is 11672064. I didn't try to check next one because it's growing as n factorials. But then, I tried to came up with better representation and here it is:
We have complete graph. Write adjacent matrix. In each cell of it place letter from partition with A. For example, AC BE DF <- in this partition A goes with C, so put in all edges AC, BE, DF letter C. This will give some thing that is very close looking to latin square. Had to spend time to remember this name. So, when I did it in this way and fixed first row (matching of A) I got:
n = 2: 1
n = 3: 6
n = 4: 6240
n = 5: 1225566720 (this one after a while)
I thought why 6? Well, because you also fixed AB CD EF (not only AB, AC, AD, AE, AF), and this is why.
While calculating n = 5 I checked 1,6,6240 in OEIS and found this:
oeis.org/A000438
en.wikipedia.org/wiki/Graph_factorization
So, if you don't fix first partition to be AB CD EF then answer is known for n up to 7.
As far as you fix CD, EF GH... The answer we can try to find. Because it's not in OEIS
I think latin square analysis should help.
Probably something is wrong with fixing AB CD EF.
Regarding to tan(n) > n, using stupid approach with binsearch I verified all n up to 6021806150000000 and list from OEIS is correct so far. I'm still interested to know how to find all n more efficiently. My code that I give a link did skip one number, so my suspicion was true that it doesn't check everything you need.
(Click for larger)
The last is sufficient to prove it's a parabola (because A x^2 + B xy + C y^2 is the square of a linear polynomial). The only caveat is that the coefficient C_2 contains a factor of 1/(a'b'' - a''b') which is proportional to 1/det A. Hence the requirement for non-degeneracy.