Thursday, 26 January 2012

Self-similarity in composite patterns (expressed as difference of two squares)

Here's a minor example of self-similarity in the patterns I have been looking at.

The first row of each chart is N^2 - 1.

When we sieve for composites next to multiples of 24, the pattern is 6, 24 , 54, 96... (as seen in the first line of the diagram below).

For composites of 48, we halve this and get 3, 12, 27, 48... This is a series which ascends by 6X+3 at each step, with X increasing by 1 at each step.

For composites next to multiples of 96, the pattern is 6, 24 , 54, 96

For composites next to multiples of 192 it is once again 3, 12, 27, 48

Thereafter these two patterns are completely self-replicating, but increasingly stretched out, as can be seen below.

It's a bit fiddly to explain the reason why though it basically comes down to the fact that for each even number X in the pattern we find the even number 4X 4 spaces away . As a result, the pattern keeps repeating.

I won't get bogged down trying to explain this more formally as it doesn't really impinge on anything else I want to say. It is just interesting to note that in at least one aspect this pattern is perfectly self-replicating.

There are however more interesting things to be seen with respect to self-similarity in other parts of the pattern, which I will come to next.

Edit: Coming back to this post later on, I see that there is a simple way to explain what I was fumbling to say above in terms of differences.

For the series 3, 12, 27, 48 the first difference is 3, 9, 15, 21, and the second difference is 6. (eg the first difference increases by 6 each time).

For the series 6, 24, 54, 96, the first difference is  6, 18, 30, 42 and the second difference is 12 (so they are both twice the series above). when we halve this series we get the first, when we halve the first we get the second and lose the odd numbers, so this is an endless loop.

Wednesday, 25 January 2012

Composite numbers seen as the difference between two squares Part 6

Here is a section of the pattern of composite numbers adjacent to multiples of 192. I know it's getting hard to read the numbers, and I won't keep picking out the kite-shaped pattern I've previously noted. The main thing to look at here is how everytime we go up to the next multiple, we lose half the composites from the previous pattern and a similar pattern develops.

And here is the pattern for composites adjacent to 384 (numbers in pink/purple) - in this one I've left the composites adjacent to 192 in blue as it helps to see how one pattern turns into the next one. (The squares with heavy black outlines are all part of the pattern for composites adjacent to 384 and coloured pink).

And this is a longer view of the same pattern (getting ridiculously cramped now...) The black squares are composites adjacent to multiples of 384 up to 24 x 384 - note the same kind of kite-shaped pattern (though I didn't quite have space to fit this all in).

OK, there's no point going on reiterating larger versions of this pattern as it is already impossible to read. The next thing is to go back and look at some of the reasons (based on modular arithmetic) why we keep seeing the same kind of pattern recurring.

Composite numbers seen as the difference between two squares Part 5

The next step of this slightly laborious exploration is to move on to composite numbers that are adjacent to multiples of 96. Here is the chart adapted for this purpose. It was getting fiddly changing the settings so from now on the second column indicates which multiple of 48 the composite number is adjacent to - so the even multiples of 48 are multiples of 96 and odd multiples are eliminated (these have been left in yellow).

First let's look at a fairly small section, up to 96 and 95 on the horizontal and vertical axis.

Pink indicates a composite number adjacent to a mutliple of 96.

At this stage we start to see a more complex symmetry. The outlined boxes indicate the areas which reflect. Vertically there is a symmetry from 1 to 47 around the line between 23 and 25, also from 1 to 95 around the line separating 47 and 49. Horizontally, the symmetry is around the 24 line and the 48 line. Within the boxes formed by the axes of symmetry, there is a group of four composite numbers that repeats in each - the first four in the 0 and 12 columns vertically and the 1-23 columns horizontally. This group of four reflects vertically. Horinzontally it repeats (or you can see it as a symmetry with the 24 column as the axis). This builds up into predictable numbers of composites within these boxes - in the area before the 96 column there are 16 groups of 4, 64 composites altogether. I'm pointing this out here because it is a pattern that repeats in later charts.

There are some more complex issues about these symmetries (based on modular arithmetic) which explain why successive eliminations leave a very similar pattern in place, but  I'll come back to that.

Here is a longer view of the pattern.

You can't really see the numbers on this one, however you can see the kite-shaped pattern recurring in the blue numbers, which is all the composites adjacent to multiples of 96 up to 24 x 96. A similar pattern would apply (at twice the size) to multiples up to 48 x 96. 

We find 39 instances of composite numbers up to 24 x 96 (including repeats). Because of the repeats, there are 3 gaps in the pattern, at 2 x 96 (twin primes 191/193), 12 x 96 (twin primes 1151/1153) and 22 x 96 ( twin primes 2111/2113).

1) There is a predictable number of composite numbers in the boxes I have indicated - for instance within the largest box here (not counting the composites within the 192 column which has a line either side of it) there are 4 x 64 = 256 composites.

2) We can see the area within which it is possible for there to be multiples up to a certain threshold. There are limits on this area, which I will look at in more detail later. The choice of 24 as the threshold is a slightly arbitrary one - I've just chosen it in order to show the self-similarity as we move up through these charts and narrow down the area in which we are looking for composite numbers.

More on this to follow in later posts.

Monday, 23 January 2012

Composite numbers seen as the difference between two squares Part 4

One quick point I should maybe emphasize. I explained already that the difference between two squares must be a composite number. What I didn't show was that any composite number in the form 6X+/-1 can necessarily be expressed as the difference between two squares (of integers that are separated by more than 1). This is the basis of Fermat factorisation, so well known, but just to run through the logic...

This is because the factors of a composite number of the form 6X+/-1 must themselves be numbers of the form 6X+/-1. And regardless of how many factors a number has it will be possible to express the factors as AB where A and B are numbers in the form 6X+/-1 (and A > B).

Let N = (A - B)/2 + B = A/2 + B/2
Let M = N - B = (A/2 - B/2)

Since A and B are odd numbers, N and M are both positive integers.

N^2 - M^2 = (N+M)(N-M) = (A/2 + B/2 + A/2 - B/2)(A/2 + B/2 - A/2 + B/2) = AB

So unless N - M = 1, and AB is odd, then AB is a composite number.

Thus the chart we started with, with an array of the differences between all square numbers, necessarily contains all composite numbers of  the form 6X+/-1 (if extended infinitely). What we are doing after that is gradually eliminating the parts of that array that can't contain numbers adjacent to 3 x 2^n as the value of n increases.

Part Five

Sunday, 22 January 2012

Composite numbers seen as the difference between two squares Part 3

We've been looking at composite numbers adjacent to multiples of 3x2^n as n increases (alternatively I could say adjacent to successively doubling 6, so we get 12, 24, 48, 96.) The reason I am doing this will become more clear shortly as we see the next few rounds of sieving this way.

We've seen how the density of composite numbers in these diagrams halves each time we double the multiple of 3x2^n (eg move from 6 to 12 to 24 to 48...)

Next I want to narrow the search down from composites adjacent to 24 to composites adjacent to 48. This results in half of the lines in the previous diagram being eliminated:

The yellow lines contain composites adjacent to a multiple to 48, the white lines are eliminated.

Note that the pattern of yellow lines is symmetrical, repeating every 8 lines. We will see more complex symmetrical eliminations on subsequent stages, but at this stage the symmetry is very simple.

Pink squares are composites adjacent to the first 12 multiples of 48, blue squares are the next 12 (13 to 24). There are 15 of the former and 17 of the latter, 32 in all. This would be more than enough to eliminate all of the first 24 pairs if they were spread across all numerical values, but there are some values that appear several times, for instance 6 (because 289 and 287 are both composites) and 8 (which appears three times because 385 is a multiple of 5, 7 and 11 as explained in the previous post).

Note that collectively these are in a "kite-shaped" band similar to the region which we saw for multiples of 24. Eventually I will give a more formal description of this area, at this point it is just the similarity that interests me.

As a result of instances where both the 6N+1 and 6N-1 number are composite, and instances of composites with distinct factorisations, there are gaps left in the pattern, which indicate twin primes.

In the next few posts we will see a more obviously fractal pattern develop and I will also give some explanations based on modular arithmetic as to why these patterns develop in a rather self-similar manner.

Part Four

Composite numbers seen as the difference between two squares Part 2

OK, so next we want to go from looking for composite numbers adjacent to multiples of 12 to looking for composite numbers adjacent to 24. This is fairly easily done. The square of any number that is 6 (mod 12) will be 12 (mod 24). The square of any 6N+/-1 number is 1 (mod 24), so the difference between the 2 will always be 11 or 13 (mod 24).

So from the previous chart, we can eliminate all the columns for numbers that are 6 (mod 12), in other words 6, 18, 30. And we can also eliminate every second entry in the columns for numbers that = 1 or 5 (mod 6) - so we eliminate 17^2 - 6^2, but not 17^2 - 12^2 and so on. The red numbers here are the eliminated ones.

This eliminates half of the entire pattern (just as we eliminated half of the cells, the orange ones when we moved from composite numbers adjacent to 6 to those adjacent to 12).

At this point I want to use a different style of array to demonstrate the patterns in these numbers.

In this array we unify columns so that we simply subtract the squares of 6N+/-1 numbers from the squares of multiples of 12. This produces all composite numbers that are 1 more or one less than a multiple of 24. 6N+1 numbers are shown as negative numbers, but the important thing is the numerical value, not the sign (because 17^2 - 12 ^2 has the same numerical value as 12^2 - 17^2).

After the column showing the composite numbers generated this way, the next column indicates which multiple of 24 the composite number is adjacent to. For instance 12^2 - 5^2 = 95, which is adjacent to 96 so the cell next to 24 gives the value of 4.

The grey numbers on the diagonal are cases where the difference between N and M is 1 and thus do not indicate a composite number unless the same value appears elsewhere.

The cells coloured pink are all the cells where we have a composite adjacent to a multiple of 24 from 1 to 12, in other words 288 or lower. We will see this basic pattern recur in later diagrams so it is important to understand why this is the only region in which these numbers can be found. I'll look at this in more detail in a later post.

If each number from 1 to 12 were present it would show that there are no twin primes adjacent to the first 12 multiples of 24. In fact there is no instance of 3, 8, or 11, which is what we would expect given that 71/73, 191/193 and 239/241 are twins.

It's also useful to note the reason why these pairs are not present in the pattern. There are 12 cells coloured pink. If each of these were a different numerical value it would be enough to eliminate every pair. However 5, 6 and 9 appear twice in the pattern, once for a 6N+1 number and once for a 6N-1 number. This means there aren't enough composites in this pattern to cover every pair adjacent to 24 up to 288.

(The other reason why a number will appear more than once is where the composite number has 2 or more distinct factorisations. For instance in the next pattern we will see several instances of the number 385. This is because it is 5 x 7 x 11 and thus can be expressed three ways:

35 x 11 = 23^2 - 12 ^2
55 x 7 = 31^2 - 24^2
5 x 77 = 41^2 - 36^2)

Part Three

Composite numbers seen as the difference between two squares.

I've been looking at a different way of thinking about the distribution of primes and twin primes. I want to make some notes about it here to help clarify the patterns I am looking at.

The general plan of what I want to do over the next few posts is this:

1. Explain how composite numbers are related to the difference between two square numbers. Show a way of sieving for composites/primes using this. (This is the basis of Fermat factorisation, but I am going to approach this from basics as I want to understand the nuts and bolts).
2. Look at the pattern of composite numbers that are adjacent to (eg 1 more than or 1 less than)  multiples of 12.
3. Extend this analysis to composite numbers that are adjacent to 24, 48, 96 etc, doubling each time (3*2^n as n increases).
4. Make some observations on the elements of (fractal-like) self-similarity in these patterns.
5. Conjecture as to how these patterns help to explain or suggest (not prove) the infinitude of twin primes.

OK, so firstly, why does the difference of two squares always produce a composite number? This is easy to explain - N^2 - M^2 = (N+M)(N-M) so if N and M are two different positive integers, the result is a positive composite number, unless N - M = 1, in which case the number may be prime (for instance 7^2 - 6^2 = 1x13 = 13 whereas 18^2 - 17^2 = 35, but this can also be expressed as 6^2 - 1^2).

Here is a chart showing composite numbers generated by subtracting the square of M (the vertical axis) from the square of N (the horizontal axis). Note that the first row is N^2 - 0^2 = N^2. Obviously this is also always a composite number.

When looking for primes > 3 we are considering odd numbers of the form 6X+1 or 6X-1 where X is a positive integer.

The chart doesn't consider cases where N - M < 5 because these cases don't generate any composite 6N+/-1 numbers (see below for the reason why).

Where N and M are both even or both odd, the difference between the two squares will be even, so we will only be looking at cases where one is odd and the other is even. It is also clear that you only get a number of the form 6X+/-1 where (N+M) and (N-M) are also both of the form 6X +/-1. (I hope this is obvious enough not to need a lengthy explanation)

Examples of this include.
5^2 - 0^2=  5 x 5 = 25
6^2 - 1^ 2 = 5 x 7 = 35
7^2 - 0^2 = 7 x 7 = 49
8^2 - 3^2 = 5 x 11 = 55
9^2 - 2^2 = 7 x 11 = 77
9^2 - 4^2 = 65
10^2 - 3^2 = 91
11^2 - 6^2 = 85
12^2 - 1 ^2 = 143
12 ^2 - 5^2 = 119
12^2 - 7^2 = 95

The final thing I will note in this post is that the numbers that are pink above are all 11 or 1 (mod 12) while the numbers coloured orange are 5 or 7 (mod 12). The pink numbers are thus adjacent to (one more or one less than) multiples of 12.

It's pretty clear that we only get a composite odd number of the form 6N+/-1 adjacent to a multiple of 12 when one of N and M is a multiple of 6 and the other is 1 or 5 (mod 6).

(Briefly, the reason for this is that squares of 6N+/-1 numbers (eg 1 or 5 mod 6) are always 1 (mod 24) and squares of multiples of 6 are always 0 (mod 12) so the difference between them will always be 1 or 11 (mod 12). Whereas squares of numbers that are 3 (mod 6) are always 9 (mod 12) while squares of numbers that are 2 or 4 (mod 6) are always 4 (mod 12) - meaning the difference between them will always be 5 or 7 (mod 12). )

This all means that we can take out 3 out of every six vertical columns in the chart (the ones containing orange numbers) if we only want to sieve for composite numbers adjacent to 12.

In subsequent posts I will look at how the number of composites in the pattern halves as we double up to look for composite numbers adjacent to 24, 48 and so on.

Part Two

Tuesday, 10 January 2012

Fractal patterns in composite n-factor numbers

Here's something I find weirdly fascinating, quite likely better understood by proper mathematicians... In a previous post I observed that

"The pattern of 6N+/-1 primes eg 1 x 5, 1 x 7, 1 x 11 etc is also fractally replicated in n-factor numbers. For 2-factor numbers a new pattern (congruent to the overall pattern of primes) starts at each prime  eg 5 x 5, 5 x 7, 5 x 11…  7 x 5, 7 x 7, 7 x 11…. and so on. For 3-factor numbers we have a new repeat of the prime pattern starting from each 2-factor number and so on."

Now, we can tell a few things about these overlaying patterns. Firstly, we know that each iteration of the pattern is congruent (or is "isometric" a better word??) to the original prime pattern albeit proportionately bigger - so, 5, 7, 11, 13, 17 is congruent to 25, 35, 55, 65, 85, which is congruent to 35, 49, 77, 91, 119 with each entry in the latter being 7/5 bigger than the second, and 7 times bigger than the first. the first 3-factor iterations of the pattern are 125, 175, 275, 325, 425... then you get 175, 245, 385, 455, 595 etc.

Secondly, we know that as we overlay the n-factor patterns, each number can only appear n times - in other words, 35 can appear twice in the lists above, but only twice as it only has two factors. (25 can only appear once as it is a square, so the key thing is how many distinct factors a number has, not how many factors).

Next, and this is something I find intriguing, we know that each iteration of these congruent patterns picks out a unique set of numbers - this means that there is no number that is in both the 2-factor pattern and the 3-factor one. So, to take a visual approach, the set of composite numbers of the form 6N+/-1 is made up of infinite iterations of the same original infinite pattern of primes, all delicately avoiding landing on the same number off to infinity.