Printable View
I have to be away for a few days again. I see the way to settle the question perhaps. If the total 2's in 2n minus the trotal 2's in(2n-1) equaled n and was proven algebraically, I suppose that might do it. Go ahead and prove that while I am gone if you have a mind to.
Here is what I know for sure. The higher powers of 2 between n and 2n have to equal the lowest power of 2 between 1 and n. In other words, for n=5, after removing that first layer of 2's there is still 22 left where 8 was. 22 is exactly what was skimmed off between 1 and n. I am asking how they know this to be true in general. I am probably missing something quite basic. Maybe I will find it before I leave for a few days off.
Specifically, it needs to be shown that
i=2Σ2n↓2n/2i↓=↓n/2↓
where the arrows indicate the floor function, which is always rounded to the lowest whole value. This may prove to be a lousy way to set the problem up to find the answer. I just know it is correct. The value on the left (for 2n) is without its lowest and most numerous power of two, the value on the right (for n) is calculated only for the value of its lowest power of 2. The two should be equal.
It also says that the factors of 2 in 2n! is equal to 2n, doesn't it? In other words there are n such factors. Which is what we are trying to show. It is a nifty equality. One has to internalize that.
Well, one should prove it first, even though it is known to be true. I cannot see it intuitively, but I believe it is seeable that way.
I guess I do not see that intuitively--yet, at least. It is what I said was intuitively clear a few posts ago. But I do not see that the remaining number of 2's between n and 2n after the first layer is peeled off should always be equal to what was peeled off between 1 and n. But maybe that fact is just a consequence of the law. No, it is the law in slightly different expression.
A consequence of this would be that whenever n is a power of 2, (n)! will have (n-1) factors of 2. A power of 2 factorialized always has a value of one less than 2k. 4! is guaranteed to have three factors of 2, 8! is guaranteed to have 7, etc. People who have worked in binary know this.
For even n, n!! skips every other factor one would normally see in n!. That is, it looks like this product: 2*4*6*...*n. There are n/2 factors. Now remove 2 from each of those factors. You get 2n/2(1*2*3*...*n/2) = 2n/2(n/2)!. Let k = n/2 to simplify the notation and you get 2kk!.
For odd n, n!! skips just like for the even n. It looks like this product: 1*3*5*...*n. This is the same thing as multiplying all the numbers together less than or equal to n and then dividing out the even ones: (1*2*3*...*n)/(2*4*6*...*(n-1)). But that is n!/(n-1)!!. Note that n-1 is even since n is odd. We already have a way to write n!! when it is even and so we get the following for n odd: n!! = n!/(n-1)!! = n!/(2(n-1)/2((n-1)/2)!). Let k = (n-1)/2 and this simplifies to n!/(2kk!).
I was thinking about those double factorials. They are a way to split a factorial into the even factors and the odd factors in this manner:
n! = n!! (n-1)!!
For the even n, we can factor out the n/2 powers of 2 and continue the process. For example, if n is even then n!! = 2n/2(n/2)! Now take the (n/2)! and split it into even and odd factors. Repeat the process until all the factors of 2 are removed from n! leaving 2 to some power and the odd factors.
I suppose one could also do this for other primes but this notation is specific to 2. What one gets is the prime factorization of n!.
On my trip it became crystal clear where the oversight lay that was causing my disagreement with the formula. Math requires lots of solitude and good marijuana. I had overlooked the detail in my reckoning that the lower half of the double factorial was being filled in with odd small numbers. Here is the formula again:
(2n)!=2n[n!(2n-1)!!].
Only n factors of 2 are needed to produce the full double factorial with its complete lower end because that is exactly how many factors of 2 are contained in the upper interval. I have not seen it proved anywhere that the upper interval will always contain exactly n factors of 2, but having now examined the mechanics of the details, I fully accept that it does and has been proven elsewhere, probably by induction. It is one of those facts of life of numbers I did not know. There are plenty of them I did not know before but came to understand. I like this formula and I am glad we stopped to consider it. Whether it can help in the quest for Brocard awaits more solitude and marijuana. I believe there is a connection and I believe I see a hint of it through the smoke, sir. It is really a matter of connecting notations with the problem.
Maybe more vision will enable me to see why the part of the formula in brackets ( the factorial times the double factorial) is equivalent to multiplying the oddly labled traingular numbers together. I look forward to seeing that, and I suppose it is what I must stick with for the moment.
I was trying to make sense out of the abc conjecture. I think I have a basic understanding of what it is trying to say primarily from this wikipedia article: https://en.wikipedia.org/wiki/Abc_conjecture
What I don't see at the moment is why it implies that Brocard's problem has only finitely many solutions, but this reference is supposed to provide the key: http://www.mat.univ.szczecin.pl/file...dramanujan.pdf
I do not see it clearly yet, either. One first needs to study Diophantine equations to get the basics of their solution and become familiarized with the usual methods in the field.Quote:
Originally Posted by YesNo
I am still trying to figure out the triangular connection to the other problem, but I am looking at this problem too. I would like to understand the abc conjecture better, so I suppose I will. You never know when the insight will come, except that it will be when you are concentrating your best.
As an intersting extension of the (2n)! problem, I have realized it is possible to determine the exact number of factors of 2 in the interval (1, 2n) without recourse to the floor function which is the the usual manner. I have derived by observation the piecemeal formula that works for all values of x≥1, and I would have no need of the floor function, then, to determine the number of 2's in virtually any factorial. If I do not lay it out in a list it will be harder to conceptualize. Near the end of the list I realize I need only include even values in the range (1, 2x) to get a formula.
(2·4)!=8·7·6·5║·4·3·2·1
...........3....1......2....1
(2·5)!=10·9·8·7·6·║5·4·3·2·1
............1.....3....1......2....1
(2·6)!=12·11·10·9·8·7║·6·5·4·3·2·1
............2.........1....3......1.....2...1
(2·7)!=14·13·12·11·10·9·8·║7·6·5·4·3·2·1
............1........2.........1....3......1....2. ...1
(2·8)!=16·15·14·13·12·11·10·9║·8·7·6·5·4·3·2·1
............4........1........2........1.......3.. ..1....2....1
(2·9)!=18·16·14·12·10║·8·6·4·2·1
............1...4....1...2...1...3.1.2.1
(2·10)!=20·18·16·14·12·║10·8·6·4·2·1
..............2...1...4....1...2....1..3.1.2.1
Certain patterns now appear.
1 for even x, the two partitions have the same number of elements
2 For odd x the upper partition gets a bonus factor of 2 among its elements.
3 Every number divisible by 2 in x≥(x/2) has a double in the upper partition with exactly one more factor of 2.
4 Where x is a power of 2, the lower partition has one less factor of 2 than the upper, so the count in this special case is easy. The general method below, however, still applies.
5 To determine y in the equation below, merely count how many even elements in x are≥(x/2), and add one to the value of y for each case. If x is odd, we add one additional bonus factor, and we are done.
2x+y+k, where y is the number of even elements in the interval (1, x) that are ≥(x/2), and k=0 when x is even, k=1 when x is odd:
We already knew we needed no floor function to determine the number of factors of 5 in a factorial (for we simply count the number of 0's in the tail), but now now we have a way to avoid the floor function to determine the total number of factors of 2, as well. The fact that it is simpler and works for all factorials is impressive. It is probably an easy consequence of things I already knew, but I never put this together until now.
I checked this with Python. My program may be wrong.Quote:
Originally Posted by desiresjab
I don't know if it generalizes as you are suggesting or not.
Here is the code:
from math import factorial
from sympy.ntheory import factorint
for i in range(1,11):
b = factorint(math.factorial(2*i))
print("2 times",i,"factorial has",b[2],"factors of 2.")
Here are the results:
2 times 1 factorial has 1 factors of 2.
2 times 2 factorial has 3 factors of 2.
2 times 3 factorial has 4 factors of 2.
2 times 4 factorial has 7 factors of 2.
2 times 5 factorial has 8 factors of 2.
2 times 6 factorial has 10 factors of 2.
2 times 7 factorial has 11 factors of 2.
2 times 8 factorial has 15 factors of 2.
2 times 9 factorial has 16 factors of 2.
2 times 10 factorial has 18 factors of 2.
Here are some further values:
2 times 11 factorial has 19 factors of 2.
2 times 12 factorial has 22 factors of 2.
2 times 13 factorial has 23 factors of 2.
2 times 14 factorial has 25 factors of 2.
2 times 15 factorial has 26 factors of 2.
2 times 16 factorial has 31 factors of 2.
2 times 17 factorial has 32 factors of 2.
2 times 18 factorial has 34 factors of 2.
2 times 19 factorial has 35 factors of 2.
2 times 20 factorial has 38 factors of 2.
Looking again at the bracketed part of the formula
(2n)!=2n[n!(2n-1)!!]
for the equivalence between that and triangular numbers, let us make a set of the oddly labled triangular numbers
(1, 1+2+3, 1+2+3+4+5, 1+2+3+4+5+6+7,...)=
(1, 6, 15, 28,...)
Each new element adds the next two successive integers, which means we are adding an odd number to the total already there, so the parity of the set strictly alternates. We only need to show that the above set multipled together has identical prime factorization as the part of the formula in brackets.
1, 2 and 3 of the lower factorial are got from 1 and 6. The 4 comes from the 28, leaving a 7. This 7, along with the 5 and the 3 in the prime factorization of 15, completes the double factorial starting from (2x-1), as the 1 at the end is superfluous as a multiplier and does not change the product.
We have shown it, now we need to prove it for every case.
We note that the above ordered set shares alternating parity as a feature with the factors of a factorial. We note further that factors of prime n are introduced on the nth element of the set of oddly labled triangular numbers. We note that any remaining numbers after these factors are factored out of the triangular numbers are odd, and along with factors still remaining in the triangular set, form a double factorial beginning on 2x-1.
That is as close as I can get to a proof right now.
Here is a paper discussing the relationship between factorials and triangular numbers. I have only skimmed the introductory part, but it looks like it is discussing a similar problem to the one you are addressing: http://www.integers-ejcnt.org/l50/l50.pdf
He called the factorials the "additive analogs of factorials" which makes sense, but I did not think of it that way before.