I've been working on some stuff about prime quadruplets. For reasons too dull to explain just now I started by looking for a formula that always generates composite numbers. At some point when I get the chance I'll explain this a bit more, but after a bit of thought I came up with this:
2x -1+4y(x+y) for all positive integer values of x and y.
It does work, which is nice - it generates all the odd composites (which is all you need since all evens are composite except 2.
More later.
Edit: Obviously a formula like xy where x and y are positive integers > 1 is a great deal simpler, but for various reasons I wanted one for which you didn't need to exclude 1.
Monday, 28 May 2012
Thursday, 24 May 2012
Is the difference of two squares always composite?
Someone arrived here via this google search - briefly, the difference between X^2 and Y^2 is always a composite number (where X and Y are positive integers) if the difference between X and Y is greater than 1. The reason for this becomes apparent when you look at this way of working out the difference between X and Y.
If the difference is 1, to get from X^2 to Y^2 you add X + (X+1). This will be an odd number and can be prime or composite (every odd number can be expressed as the difference between two consecutive squares.)
If it is 2, you add X + (X+1) + (X+1) + (X+2). This can be rewritten as 4(X+1)
If it is 3 you add X + (X+1) + (X+1) + (X+2) + (X+2) + (X+3). This can be rewritten as 6(X + 1.5) = 3 (2X+3)
If you continue in this way it is clear that where the difference is greater than 1, the sequence of numbers can always be rewritten as an equation that is a composite integer.
Another way of thinking about this: the difference between two squares is always the sum of a series of consecutive odd numbers. For instance to get from 25 to 64, you add 11 (=5+6) then 13 (= 6+7) then 15 (=7+8). If there is an odd number of these, then the sum will be (the quantity of odd numbers in the series) x (the middle number in the series). If there is an even number, then the sum will be (the quantity of odd numbers in the series) x (the average of the middle two numbers in the series). This latter term will be N+1/2 but since you are multiplying by an even number the total is a composite.
Hope that all makes sense. This is the basis of Fermat factorisation, which I have talked about elsewhere.
If the difference is 1, to get from X^2 to Y^2 you add X + (X+1). This will be an odd number and can be prime or composite (every odd number can be expressed as the difference between two consecutive squares.)
If it is 2, you add X + (X+1) + (X+1) + (X+2). This can be rewritten as 4(X+1)
If it is 3 you add X + (X+1) + (X+1) + (X+2) + (X+2) + (X+3). This can be rewritten as 6(X + 1.5) = 3 (2X+3)
If you continue in this way it is clear that where the difference is greater than 1, the sequence of numbers can always be rewritten as an equation that is a composite integer.
Another way of thinking about this: the difference between two squares is always the sum of a series of consecutive odd numbers. For instance to get from 25 to 64, you add 11 (=5+6) then 13 (= 6+7) then 15 (=7+8). If there is an odd number of these, then the sum will be (the quantity of odd numbers in the series) x (the middle number in the series). If there is an even number, then the sum will be (the quantity of odd numbers in the series) x (the average of the middle two numbers in the series). This latter term will be N+1/2 but since you are multiplying by an even number the total is a composite.
Hope that all makes sense. This is the basis of Fermat factorisation, which I have talked about elsewhere.
Monday, 14 May 2012
Dirichlet's Theorem and composite numbers seen as the difference of two squares
Back in January I made a series of posts where I explored the patterns in composite numbers adjacent to numbers of the form 3*2^n (= 6, 12, 24, 48, etc).
What I've recently realised is that what I was seeing there was a specific, narrow example of Dirichlet's Theorem on arithmetic progressions, which states that "for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n ≥ 0."
For instance, the series of numbers adjacent to (eg 1 more or 1 less than) 48, can be expressed as the two series 1+ 48n and 47 + 48n. The patterns I was seeing show that each time we go to a higher multiple of 3*2^n, half the composite numbers remain, so we have a very similar pattern - and because the composites are distributed in this way it also seems reasonable to expect that primes are also being divided in more or less the same manner. The first diagram in the post linked to above, shows how composite numbers divide equally between numbers that can be expressed as 12n+1, 12n+5, 12n+7 and 12n+11 - I tend to use the pigeonhole analogy to picture the process which leads to equal numbers of composites being put into each of these modulo residues.
So then when you look at composite numbers adjacent to 24, half of the 12n+1 numbers will go into the 24n+1 pigeonhole and half of them will go into the 24n+13 pigeonhole, while half of the 12n+11 composites go to 24n+23 and half go to 24n+11.
Going back to Wikipedia, I see that "stronger forms of Dirichlet's theorem state that, for any arithmetic progression, the sum of the reciprocals of the prime numbers in the progression diverges, and that different arithmetic progressions with the same modulus have approximately the same proportions of primes." Which is kind of what I was just trying to say (though obviously seeing a pattern is not the same as proving a theorem).
Of course this applies to all values of d, not just multiples of 3*2n - for other values (for instance 4n+3 and 4n+1, or 10n+1, 10n+3, 10n+7, 10n+9) there will also be an ongoing process whereby the composites are evenly spread among the available pigeonholes, which will lead to each having a similar proportion of primes.
I have looked at a few proofs of Dirchlet's theorem and haven't got my head round them yet. Will try a bit harder but I think they might be too technical for me to follow.
The other question which I am interested in is whether this has any significance for twin primes and other Polignac primes - in the later posts on composite numbers expressed as the difference of two squares, I was also exploring the fact that (for instance) the patterns for 48n + 1 and 48n + 47 can be seen as the same progression, going "through zero" (if you ignore the minus signs) -95, -47, 1, 49, 97.
When it comes to composite numbers as the difference of two squares, it works like this. Take x^2 - y^2 where the difference between x and y is 7.
24^2 - 17^2 =287, 12^2 - 5^2 = 119, 0^2 - 7^2 = -49, 12^2-19^2 = -217
Which can also be expressed as
7*41, 7* 17, -7*7, -31*7
So this is a continuous arithmetic progression with a gap of 7*24 = 168 - if we extend it a bit further we get this series
If we look at this in modulo 96, the same series produces these remainders
25, 49, 73, 97, 25, 49, 73, 97, 25, 49, 73, 97, 25, 49...
Which is a constant loop, meaning that half of these numbers are next to a multiple of 48, and half of those are next to a multiple of 96 and son.
Of course, if we ignore the minus signs, the first few would instead be 23, 47, 71, 95... (eg 6n-1 numbers instead of 6n+1 numbers). But with regard to which multiples of 24 they are adjacent to the pattern is a continuous one.
I'll try to come back to look at this again soon to see if I have anything useful to say about how this relates to twins.
What I've recently realised is that what I was seeing there was a specific, narrow example of Dirichlet's Theorem on arithmetic progressions, which states that "for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n ≥ 0."
For instance, the series of numbers adjacent to (eg 1 more or 1 less than) 48, can be expressed as the two series 1+ 48n and 47 + 48n. The patterns I was seeing show that each time we go to a higher multiple of 3*2^n, half the composite numbers remain, so we have a very similar pattern - and because the composites are distributed in this way it also seems reasonable to expect that primes are also being divided in more or less the same manner. The first diagram in the post linked to above, shows how composite numbers divide equally between numbers that can be expressed as 12n+1, 12n+5, 12n+7 and 12n+11 - I tend to use the pigeonhole analogy to picture the process which leads to equal numbers of composites being put into each of these modulo residues.
So then when you look at composite numbers adjacent to 24, half of the 12n+1 numbers will go into the 24n+1 pigeonhole and half of them will go into the 24n+13 pigeonhole, while half of the 12n+11 composites go to 24n+23 and half go to 24n+11.
Going back to Wikipedia, I see that "stronger forms of Dirichlet's theorem state that, for any arithmetic progression, the sum of the reciprocals of the prime numbers in the progression diverges, and that different arithmetic progressions with the same modulus have approximately the same proportions of primes." Which is kind of what I was just trying to say (though obviously seeing a pattern is not the same as proving a theorem).
Of course this applies to all values of d, not just multiples of 3*2n - for other values (for instance 4n+3 and 4n+1, or 10n+1, 10n+3, 10n+7, 10n+9) there will also be an ongoing process whereby the composites are evenly spread among the available pigeonholes, which will lead to each having a similar proportion of primes.
I have looked at a few proofs of Dirchlet's theorem and haven't got my head round them yet. Will try a bit harder but I think they might be too technical for me to follow.
The other question which I am interested in is whether this has any significance for twin primes and other Polignac primes - in the later posts on composite numbers expressed as the difference of two squares, I was also exploring the fact that (for instance) the patterns for 48n + 1 and 48n + 47 can be seen as the same progression, going "through zero" (if you ignore the minus signs) -95, -47, 1, 49, 97.
When it comes to composite numbers as the difference of two squares, it works like this. Take x^2 - y^2 where the difference between x and y is 7.
24^2 - 17^2 =287, 12^2 - 5^2 = 119, 0^2 - 7^2 = -49, 12^2-19^2 = -217
Which can also be expressed as
7*41, 7* 17, -7*7, -31*7
So this is a continuous arithmetic progression with a gap of 7*24 = 168 - if we extend it a bit further we get this series
| -791 | -623 | -455 | -287 | -119 | 49 | 217 | 385 | 553 | 721 | 889 | 1057 | 1225 | 1393 |
25, 49, 73, 97, 25, 49, 73, 97, 25, 49, 73, 97, 25, 49...
Which is a constant loop, meaning that half of these numbers are next to a multiple of 48, and half of those are next to a multiple of 96 and son.
Of course, if we ignore the minus signs, the first few would instead be 23, 47, 71, 95... (eg 6n-1 numbers instead of 6n+1 numbers). But with regard to which multiples of 24 they are adjacent to the pattern is a continuous one.
I'll try to come back to look at this again soon to see if I have anything useful to say about how this relates to twins.
Friday, 4 May 2012
Collatz Conjecture - a few observations
Here are a few thoughts on Collatz sequences (by which I mean the sequence of numbers you get by applying the rule "halve an even number, multiply an odd number by 3 and add 1") and why they seem to always reach 1. This isn't especially rigorous, just a few thoughts about patterns.
1) You can't have an infinite sequence of "upward steps"
If we start from an odd number, we can tell how many upward steps the sequence will take before a downward step. (An upward step is one where (3n+1)/2 is an odd number, for instance 15, 46, 23 where 23>15. A downward step is one where (3n+1)/2 is an even number, for instance, 17, 52, 26, 13 and 13<17).
If the starting number is X, we can calculate how many upward steps the sequence will take before a downward step by factoring (X+1). For each time 2 is a factor of (X+1), we will get one upward step. For instance, for 7, X+1 is 2^3 so we get three upward steps - 7, 22, 11, 34, 17, 52, 26. For 15 we get 4 upward steps (15, 46, 23, 70, 35, 106, 53, 160, 80).
Note that for the odd numbers in these sequences, the power of 2 in the factorisation of X+1 gradually decreases by 1 each time, and each factor of 2 is replaced by a factor of 3 in the next X+1 - 16 = 2^4, 24 = 2^3*3, 36 = 2^2*3^2, 54 = 2* 3^3, 81 = 3^4 - this process continues until all the factors of 2 have been replaced by a factor of 3 and we reach an odd number (meaning X is even).
This shows that you can't have an infinite sequence of upward steps without intervening downward steps.(I would say it proves it but I think it would need a more rigorous exposition of the reasons for this pattern to call it a proof).
2)You can't have an infinite sequence of downward steps
This is way too obvious to even mention, but of course the number of downward steps from the even number Y also depends on the power of 2 in the factorisation of Y. Each time you halve you lose one of the powers of 2. The only way you can get into a closed loop of numbers which are all pure powers of 2 is when you get to 4, 2, 1, 4, 2, 1 (seeing as how 1 = 2^0).
So we will always be alternating between sequences of upward and downward steps and the number of steps each way is determined by the power of 2 (of X+1 for odd numbers and in Y for evens).
OK, so that's all fun stuff, but unfortunately it doesn't rule out two ways in which you could have a Collatz sequence that never reaches 1 - A) an infinite loop which keeps passing through the same number Z (where Z isn't 1, 2, or 4). B) an infinite run of upward and downward steps which keeps climbing overall.
I think it must be especially hard to prove that the second of those two options isn't possible.
1) You can't have an infinite sequence of "upward steps"
If we start from an odd number, we can tell how many upward steps the sequence will take before a downward step. (An upward step is one where (3n+1)/2 is an odd number, for instance 15, 46, 23 where 23>15. A downward step is one where (3n+1)/2 is an even number, for instance, 17, 52, 26, 13 and 13<17).
If the starting number is X, we can calculate how many upward steps the sequence will take before a downward step by factoring (X+1). For each time 2 is a factor of (X+1), we will get one upward step. For instance, for 7, X+1 is 2^3 so we get three upward steps - 7, 22, 11, 34, 17, 52, 26. For 15 we get 4 upward steps (15, 46, 23, 70, 35, 106, 53, 160, 80).
Note that for the odd numbers in these sequences, the power of 2 in the factorisation of X+1 gradually decreases by 1 each time, and each factor of 2 is replaced by a factor of 3 in the next X+1 - 16 = 2^4, 24 = 2^3*3, 36 = 2^2*3^2, 54 = 2* 3^3, 81 = 3^4 - this process continues until all the factors of 2 have been replaced by a factor of 3 and we reach an odd number (meaning X is even).
This shows that you can't have an infinite sequence of upward steps without intervening downward steps.(I would say it proves it but I think it would need a more rigorous exposition of the reasons for this pattern to call it a proof).
2)You can't have an infinite sequence of downward steps
This is way too obvious to even mention, but of course the number of downward steps from the even number Y also depends on the power of 2 in the factorisation of Y. Each time you halve you lose one of the powers of 2. The only way you can get into a closed loop of numbers which are all pure powers of 2 is when you get to 4, 2, 1, 4, 2, 1 (seeing as how 1 = 2^0).
So we will always be alternating between sequences of upward and downward steps and the number of steps each way is determined by the power of 2 (of X+1 for odd numbers and in Y for evens).
OK, so that's all fun stuff, but unfortunately it doesn't rule out two ways in which you could have a Collatz sequence that never reaches 1 - A) an infinite loop which keeps passing through the same number Z (where Z isn't 1, 2, or 4). B) an infinite run of upward and downward steps which keeps climbing overall.
I think it must be especially hard to prove that the second of those two options isn't possible.
Subscribe to:
Posts (Atom)