Gaps in Co-primes & some interesting properties

Page 1 of 2           

While I was working on understanding more about co-primes and the totient function, I came across this property related to their distribution. The co-primes of a number N are symmetrically distributed about the number (N-1)/2. As an example, you can check the image below. The picture gives 2 different views of the symmetry. The highlighted numbers are co-prime to 15 and 35 respectively.

As you may notice, for N=15, the pattern to the left of 7 (inclusive) is the same as pattern to the right of 8 (inclusive). Similar symmetry can be observed for n=35, around numbers 17 and 18.
This is not the property we intend to discuss at length, but this leads us to the observation that for any given n, if gcd(N,k) = 1, then so is gcd(N,N-k). For eg. gcd(15,1) = gcd(15,15-1) = 1, and so on.

Thus, if a number k is co-prime to N, then so is N-k.
Now let's pay attention to the pattern itself. The numbers coprime to N occur in clusters of 1 or more, that is they leave gaps (where numbers are not co-prime) and thus form a pattern. The pattern is symmetric. For e.g.

The pattern for 15 looks like 2-1-2-1-2 and for 35 it looks like 4-1-2-3-4-3-2-1-4. I call this the "sequence generated by co-prime gaps (or gaps in co-primes)".
I was curious to find out how patterns for other numbers look like. A small program was good enough to generate such patterns for odd numbers from 1 - 10000. I chose odd numbers because for even numbers, every other number shares a factor of 2, and possibly won't produce an interesting pattern, but I may be wrong (we'll see). The result for odd numbers, however, was that the patterns show some interesting properties. We'll talk about in a bit, but if interested, you can download the file from here. Listed below is the pattern for first few numbers. Dashes(-) are used for separation, they are not minus signs.

Number [1] = -
Number [3] = -2-
Number [5] = -4-
Number [7] = -6-
Number [9] = -2-2-2-
Number [11] = -10-
Number [13] = -12-
Number [15] = -2-1-2-1-2-
Number [17] = -16-
Number [19] = -18-
Number [21] = -2-2-1-2-1-2-2-
Number [23] = -22-
Number [25] = -4-4-4-4-4-
Number [27] = -2-2-2-2-2-2-2-2-2-
Number [29] = -28-
Number [31] = -30-
Number [33] = -2-2-2-1-2-2-2-1-2-2-2-
Number [35] = -4-1-2-3-4-3-2-1-4-
Number [37] = -36-
Number [39] = -2-2-2-2-1-2-2-2-1-2-2-2-2-
Number [41] = -40-
Number [43] = -42-
Number [45] = -2-1-2-1-2-2-1-2-1-2-2-1-2-1-2-
Number [47] = -46-
Number [49] = -6-6-6-6-6-6-6-

Now, let's talk about some interesting things that we observe about these patterns. I do not have proof for these observations, but feel free to chime in if you come up with one.

  • For all numbers, the pattern contains odd number of numbers, i.e. length of the sequence is an odd number. (Would be cool if we could prove this.)
  • For all numbers, the pattern is symmetric. (Proving this should be easy using the fact mentioned earlier.)
  • If N is a prime, then the pattern contains only one number, N-1. It is obvious why.
  • The largest number that appears in the sequence for a number N is the (smallest prime factor of N) minus 1.
  • No two numbers have the same sequence i.e the sequence uniquely defines the number. Thus we can consider this sequence a "signature" of the number. In other words, the number should be "derivable" from the sequence (I haven't found out a good way of doing this, though).
  • For all N, the pattern starts and ends with the same number. It also contains the very same number right in the middle! (How can we prove this?)
    This number also happens to be the largest number in the sequence.
  • For all N, the sequence is one of the following 2 types:
    - [Type 1]: It contains repeated instances of the same number. E.g. Sequences for Number[9], Number[25], Number[27], Number[49].
    - [Type 2]: If it contains more than one distinct number, then it contains all numbers from 1 to the largest number!
    (This property deserves some more discussion, which we will do later. Also will be interesting to prove this!)
    Check Number[35] above. A classic example of this type would be Number[143] = -10-1-8-3-6-5-4-7-2-9-10-9-2-7-4-5-6-3-8-1-10-. It contains all numbers from 1 to 10. Similarly sequence for Number[4757] contains all numbers from 1 to 66!
  • If a number is a power of a prime p, for instance p raised to k, then its sequence is made up of the number (p-1) repeated exactly p^(k-1) times. The sequence contains no other number. (E.g. see pattern for Number[9], Number[25], Number[27], Number[49])
  • Let k be a number appearing in the sequence of a number N.
    If k appears in N's sequence along with some other numbers less or more than k, then we can always find a number less than N whose sequence is made up entirely of k's.
    E.g. for N=25, the sequence consists of only 4's. Except for N=5, which we can call as 'trivial appearance', 4 does not appear in any sequence before Number[25]. The sequence for Number[25] is made up entirely of 4's, and then 4 is 'free' to 'mingle' with other numbers in the sequence of any N > 25, such as in sequence of Number[35]. As another example, observe that 6 does not 'mingle' with any other numbers except after its first repeated appearance for number 49. That is no sequence for N < 49 contains non-trivial appearance of number 6. Why?? That really is food for thought!
  • Now here's a kicker.
    Notice anything peculiar with these sequences?

    Number [15] = -2-1-2-1-2-
    Number [35] = -4-1-2-3-4-3-2-1-4-
    Number [143] = -10-1-8-3-6-5-4-7-2-9-10-9-2-7-4-5-6-3-8-1-10-
    Number [323] = -16-1-14-3-12-5-10-7-8-9-6-11-4-13-2-15-16-15-2-13-4-11-6-9-8-7-10-5-12-3-14-1-16-
    Number [899] = -28-1-26-3-24-5-22-7-20-9-18-11-16-13-14-15-12-17-10-19-8-21-6-23-4-25-2-27-28-27-2-25-4-23-6-21-8-19-10-17-12-15-14-13-16-11-18-9-20-7-22-5-24-3-26-1-28-

    Here's a hint. Since the sequences are symmetric, cut them in half (e.g. -10-1-8-3-6-5-4-7-2-9 for Number [143] and look again)
    No worries if you don't see it. The surprise is yet to come, but notice that the odd numbers 1,3,5,7,9 appear in alternate positions in ascending order from left to right. And the even numbers appear in alternate positions in descending order from left to right.

    And here's the suprise.
    What's special about the numbers that generate this sequence, viz. Number[15], Number[35], Number[143], Number[323], Number[899]?
    Well, let's see: 15 = 3 * 5,    35 = 5 * 7,    143 = 11 * 13,    323 = 17 * 19,    and   899 = 29 * 31.
    They are all product of twin primes!!
    Isn't that simply fantastic? Do products of all twin primes display this property? No idea, but among the list generated till 10000, the largest product of twin-primes is Number [5183] = Number [71 * 73]. And the property holds!

I am sure these sequences holds many more secrets, many more strange properties. So if you see something that I haven't, feel free to send a note!
Meanwhile, let's discuss some of the properties in more detail in Part 2.

  Quick Comment :
* Name     
Email    ( Your email id is safe with us! )  
* Comments       
* Type the number of characters in the word "HUMAN"