Collatz update

I've got a nice way of expressing the previous posts in terms of binary numbers. I'll put something up on it shortly as I think it adds a lot of clarity to the thought process (although it doesn't provide a magic proof).

Collatz - one more little bit...

I just want to explain a bit about how it works when powers are skipped. I gave this example in the last post (the start of a much longer sequence):

55

165+1

497+1+2

1497+1+2+4

4505+1+2+4+32

Here's one way of seeing what happens at the next stage, we compare the mod values of the next two powers - if they are different we don't skip, if they are the same, we skip:

55 (1 mod 2, 3 mod 4, don't skip 2)

165+1 (1 mod 4, 5 mod 8, don't skip 4)

497+1+2 (1 mod 8, 1 mod 16, skip 8)

1497+1+2+4 (At this stage it is more complicated - by adding 1+2+4 we reach a multiple of 32 so can skip 16 as well.)

Here's a slightly better way I found to look at this:

55 = 56-1

Now, we get to the next number by multiplying the first term by 1.5 and doubling the second, then subtracting the next power of 2:

(84x2)-1-2 = 165

And again

(126x4)-1-2-4 = 497

And again

(189x8)-1-2-4-8 =1497

However, because 189 is odd, we can also express this as

(95x16)-1-2-4-16

Or as

(48x32)-1-2-4-32

But we can't skip 32 because 48 is even.

48x32 = 1536

The first terms above are actually one more than the Collatz chain 55, 83, 125, 47. To find out what happens next, we can look at 1497 - this is 64n-39, but also 128n-39, 256n-39, and 512n-39. This means that after 32 we will be adding 64, 128 and 256 before we can skip 512. Honest, this does work, though it's a pain to try and explain why without writing a pamphlet.

4505+1+2+4+32 = 71 x 64

13593+1+2+4+32+64 = 107 x 128

40985+1+2+4+32+64+128 = 161 x 256

123417+1+2+4+32+64+128+256 = 121 x 1024

371225+1+2+4+32+64+128+256+1024 = 4192 x 91

Obviously the numbers involved get unwieldy and large very quickly, but it is the logic of how these chains work that interests me.

Edit:

One more thing worth a quick look - what happens when we reach a power of 2? Well, the chain looked at this way keeps climbing, but we skip a power of 2 each time. So:

5
15+1= 16 
15+16+16=47
47+1+16=64
47+64+64=175
175+1+16+64=256
175+256+256=687
687+1+16+64+256=1024
And so on

It's interesting to note that the sequence tends down towards 2/3 of the power of 2 that the equation reaches. For instance 

47/64 = 0.734
175/256 =  0.684
687/1024 = 0.671
This ratio will converge down towards 0.666.

Collatz - more thoughts

Edit: nb Everything that this posts tries to explain is given a cleaner exposition in this post http://barkerhugh.blogspot.co.uk/2013/10/a-binary-representation-of-collatz.html

Here's a bit more on this, following on from some earlier thoughts (in fact this post and the next one contains a compressed version of the three previous Collatz posts, focusing on the bits I am currently most interested in).

I mentioned before this kind of series:

A+1
B+1+2^p
C+1+2^p+2^q
D+1+2^p+2^q+2^r (where r > q > p)

To get from A to B etc, you add the first term to 2x the full equation. For instance:

A + 2(A) = B

B + 2(B+1) = C

C + 2(C+1+2^p) = D

Etc. Here is a worked example.

7

21+1=22 (=11*2)
21+(2*22)=65
65+1+2 = 68 (=17*4)
65+(2*68)=201
201+1+2+4=208 (=13*16)
201+(2*208)= 617
617+1+2+4+16 = 640 (=5*128)
617+(2*640)=1897
1897+1+2+4+16+128 = 2048

                       

Now, the point of this is that this method gives us a series which can be shown to be equivalent to a Collatz sequence. The sequence above is equivalent to 7, 11, 17, 13, 5, 1, ignoring the halving.

7 = 7

22 = 2 x 11

68 = 4 x 17

208 = 16 x 13

640 = 5 x 128

2048 = 1 x 2048

What the sequence above is doing is starting from this way of expressing a Collatz sequence (without halving):

(7 x3)+1 = 22

(22 x 3) + 2 = 68

(68 x 3) + 4 = 208 etc

Which we can also express as:

3^1 x 7 + 1 = 22

3^2 x 7 + 3 + 2 = 68

3^3 x 7 + 9 + 6 + 4

In this form, a number X's chain will reach 1 if it satisfies an equation of this sort:

(3^n x X) + 3^(n-1) + [2^a x 3^(n-2)] + [2^b x 3^(n-3)] …. + [2^c x 3]+ 2^d = 2^e

Where e>d>c>b>a

For instance, for 7 we end up with:

(243x7) + 81 + (27x2) + (9x4) + (3x16) + 128

1701 + 81 + 54+ 36 + 48 + 128 = 2048

So… the process I started with is a way of finding the number that reaches the same sum as this equation, but without the powers of 3.

21+1 = 22

63 + 3 + 2 is equivalent to 65 + 1 + 2

189 + 9 + 6 + 4 is equivalent to 201 + 1 + 2 + 4

567 + 27 + 18 + 12 + 16 is equivalent to 617 + 1 + 2 + 4 + 16

1701 + 81 + 54+ 36 + 48 + 128  is equivalent to 1897+1+2+4+16+128

Now, the important thing about this is that we can explore the pattern of how to reach a power of 2 in steps of powers of two relatively easily, since it reduces this problem to a binary number problem - and to a problem where we know every chain reaches the "target" of a power of 2. 

(Because, from any number we can reach the next power of 2 in steps of increasing powers of 2 for instance

89+1+2+4+32 = 128

67+1+4+8+16+32 = 128

119+1+8 =128)

Where the next power of 2 is 2^n then in the region between 2^(n-1) and 2^n the maximum number of steps this can take is n-1 (for instance between 16 and 32 the maximum number of steps is four, from 17 + 1 + 2 + 4 + 8. The average number of steps in the same region is (n-1)/2 (this is easy to show, I'll skip it for brevity).

Now, as we go up through the A, B, C, D sequence etc we can make several  observations.

At each step we are increasing by a factor of just over 3. So the maximum number of steps in the region increases by about 1.5-1.6, the average number of steps increases by about 0.75-0.8 (again, this can be made a bit more rigorous, I’m summarising to keep this brief).

At the same time, each time we take a step through the sequence, the minimum number of powers of 2 we need to be able to add increases by 1. For instance in each of the sums below, we add one more term.

21+1

65+1+2

201+1+2+4

617+1+2+4+16

The consequence of these two things put together is that for any starting number we eventually reach a point where (for an equivalent Collatz sequence that doesn’t reach 1) each number we hit has to be more than the average number of steps from a power of 2 – approximately 1.25 x the average.

As an example of how this works - for the Collatz sequence for 27, after about 18 steps we are in region where the average number of steps to a power of 2 is 18 - thereafter it takes until about the 40th step to reach a power of 2.

Also, each time we skip a power of 2, we have to reduce the maximum number of steps available by 1 – for instance as we extend the sequence above, we will never be able to reach a number that adds 8, as each time we will have to start by adding 1+2+4+16. So while we are in the region 2^8-2^9, the maximum number of steps available is reduced to 8-1 = 7.

Now, while it is impossible to have an infinite sequence of steps that don’t skip a power (again, this can be proven but I’m skimming), quite long sequences of this sort are possible (for instance starting from 255 there are 7 upwards steps before we skip a power).

So the challenge facing this approach is to try to prove that the sequence A, B, C, D, starting from any number can’t be infinitely extended without hitting a number where the number of steps we need to reach 2^n is equal to the minimum number of steps we need.

(Below is very rough, as it's a bit fiddly to explain...)

I’ve noticed something else which takes us a tiny bit closer to this.

When we reach a number like 201 in the sequence above, after which we are going to skip a power, the number of subsequent upwards steps without skipping a power is partly defined by how many powers we skip this time. This sounds woolly, so let me give a couple of examples.

201+1+2+4+16+32 = 256

We know at this stage that we will skip 8 (because the next number will be 201 + 208 + 208 – this means we are adding 0 mod 16, and will land on another number that is 9 mod 16, meaning that adding 1, 2, 4 will take us to a multiple of 16).

Also, we don’t skip the subsequent power, 32. This means we won’t have an upward step without skipping next time, which is correct – 617 + 1+2 +4+16+128+256 = 1024 – we are now going to skip 32 and 64.

Let’s look at a different sequence:

55

165+1

497+1+2

1497+1+2+4

4505+1+2+4+32

The turning point (where you skip a power) comes after 1497

The continued equation here would be 1497+1+2+4+32+512.

1497 = 8n+1 and 16n+1 and we are going to add 0 mod 8, 8 mod 16 to get to the next number, 4505. So we have to skip 8. We actually skip 16 too (I’ll explain the logic of this later ) so the next number we add will be 32. Thereafter, 1497 is 64n-39, 128n-39, 256n-39, 512n-39, so we will subsequently have upwards steps of 64, 128, 256, before skipping a power.

So to get to an upwards sequence of 3 steps without skipping, we need to hit a number that skips 3 numbers.This means we can't hit a sequence of n steps where n is more than the difference between the maximum number of steps in the region and the minimum number of steps we are obliged to take.

Putting this stuff together we get 1) for all numbers we will eventually reach a region where we are obliged to take about 1.25 x the average number of steps in that region at every stage. 2) In order to get uninterrupted upwards runs of numbers (eg not skipping a power) in the next step, we need to skip that many powers this step. 3) Whenever we hit the latter stages of a region there will be some powers that we are forced to skip. For instance, from 1897, it is impossible for us to add 256 or 512 as part of the path to 2048. This makes it hard to see how we could avoid reaching a power of 2, but falls short of being a proof unless it can be refined some more.

Collatz chart

I quite like this chart as a way of thinking about Collatz chains.

Each column after the first one is 2n-1 (where n is the cell to the left). This produces the pattern given in the column titles, 2n+1, 4n+1 etc.

Numbers in the 2n+1 column produce upward moves within the column (eg 15 -> 23 -> 35) or a move to a number to the right of the column. Numbers in the 8n+1 column and all columns to the right produce downward moves, two columns to the left and down the chart (eg 65 -> 49 -> 37).

The 4n+1 contains all gateway numbers (1, 5, 21, 85) which lead to a power of 2 and thus to 1. Other numbers in this column can lead to any other column or a move within the column.

Giuga Numbers - an introduction

A modular problem revisited aka Giuga numbers

I think this is quite interesting… I’ve been messing with this problem for a while. Eventually I found some more examples and this enabled me to track down work that others have done.

The original question was this:

Are there any odd numbers with factors a<b<c for which

ab = 1 mod c

ac = 1 mod b

bc = 1 mod a

Apparently these kinds of numbers are called Giuga Numbers. You can also define them thus:

If X is a Giuga number, then for any of its prime factors p

X/p – 1 = 0 mod p

(I already knew that an even Giuga number exists, 30, for which

2x3 = 1 mod 5

2x5 = 1 mod 3

3x5 = 1 mod 2)

Now, it’s fairly easy to prove that you can’t find an odd Giuga number with less than nine factors. (I’ll put my version of this proof at the end for anyone interested). But the question becomes more complicated for numbers with more factors, for instance is there an odd Giuga number abcdefghi for which

abcdefgh = 1 mod i

abcdefgi = 1 mod h

And so on.

I wanted to start by looking at how we can construct/discover a Giuga number, regardless of whether it is even or odd.

First, let’s start with the really trivial case of a Giuga number with two factors. And (for reasons which will become clear) let’s also look for numbers for which

a = -1 mod b

b = -1 mod a

Clearly this isn’t going to work for many numbers because where a < b, a = a mod b

The only cases where it does work are:

1. 2 – this is trivial but worth noting. If you allow the idea of “mod 1”, we can use a residue number system where the co-ordinates are mod 1 and mod 2 and we get

1 = 1 mod 2

2 = 1 mod 1

a+b = (0,1) + (1,0) = (1,1) = 3

ab = (0,1) x (1,0) = (0,0) = 2

2. The above is trivial but it leads to one more example which isn't a Giuga number, but which has a related form, 6 (2 x 3):

2 = -1 mod 3 = (0,-1)

3 = -1 mod 2 = (-1,0)

a+b = (-1,-1) = 5

ab = (0,0) = 6

From here, we can go on to construct a few examples of Giuga numbers.

Firstly, we already know that 30 is a Giuga number so let’s look at how it works, using the residue number system for mod (2,3,5):

2 = (0, -1, 2)

3 = (-1, 0, 3)

5 = (-1, -1, 0)

2x3 = (0,0,6) = (0,0,1)

2x5= (0,1,0)

3x5 = (1,0,0)

We’ve added c = 5 to the grid, and because ab = ± 1 mod c we end up with ± 1 in the appropriate position (in place of 6 in the co-ordinates for 2 x 3)

The next step is to see if we can repeat the trick using abc = ± 1 mod d.

It doesn’t work for 2x3x5x29 or 2x3x5x31 because we end up with an uneven mix of +1s and -1s (see Appendix 2 for the calculations).

So let’s take a step back and look at 2x3x7 = 42

2 = (0, -1, 2)

3 = (-1, 0, 3)

7 = (1, 1, 0)

2x3 = (0,0,6) = (0,0,-1)

2x7= (0,-1,0)

3x7 = (-1,0,0)

So ab = -1 mod c

ac = -1 mod b and

bc = -1 mod a

This isn’t a Giuga number – so let’s call it a primary pseudoperfect number (OK, I googled that – basically it means one where the factors X/p = -1 mod p for all the prime factors p of the composite X).

The interesting thing here is howwe can extend this using d, where abc = ± 1 mod d.

2x3x7x41 = 1722

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

7 = (1, 1, 0, 7)

41 = (-1,-1,-1,0)

2x3x7 = (0,0,0,42) = (0,0,0,1)

2x3x41 = (0,0,-6,0) = (0,0,1,0)

2x7x41 = (0,1,0,0)

3x5x41 = (1,0,0,0)

This works to produce a new Giuga number, because the +1s and -1s balance out (because the one negative result, -6, is nonetheless +1 in mod 7)

So 1722 is a Giuga number

(At this stage I cheated a bit by googling “30,1722” and found via the lovely OEIS - that what I was looking for was called a “Giuga number”. See Appendix 2 for more detail on the relationship between Giuga numbers and primary pseudoperfect numbers.)

As it happens, 858 is also a reasonably small Giuga number so let’s see how this one works.

2x3x11x13

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

11 = (-1,-1, 0, -2)

13 = (1, 1, 2, 0)

2x3x11 = (0,0,0,-12)

2x3x13 = (0,0,12,0)

2x11x13 = (0,1,0,0)

3x11x13 = (1,0,0,0)

In the next post I will give what I think it is a proof that all Giuga numbers are even

Appendix

Here’s the original proof of the original problem for three odd numbers - using a residue number system.

ab = (0,0,1) = abc/c

ac = (0,1,0) = abc /b

bc = (1,0,0) = abc/a

ab + ac + bc = (1,1,1) = ab +1 (or = 1 or a higher multiple of ab + 1)

ab + ac + bc = abc/a + abc/b + abc/c

So ab + ac + bc can’t add up to more than 1/3 + 1/5 + 1/7 = 70/105

RAA

This proof works up to eight factors as 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + 1/17 + 1/19 + 1/23 < 1 but thereafter it fails.

You also can’t have an odd Giuga number with less than 1415 factors and an odd number of factors because all of abcdefg…etc are odd, so for an odd number of factors, the sum abcd + abce + abde + acde + bcde is odd and can’t be abcde+1.

This proof works up to 1415 factors because that is how many factors would be needed before this sum can equal 2abcde+1.

However if the proof in the next post works, neither of these proofs are needed.

Edit nb the next post is missing because there were some flaws, which I might or more likely might not be able to iron out.

Appendix 2

It also turns out that if a primary pseudoperfect number is one less than a prime then the product P(P+1) gives a new primary pseudoperfect number. However if a primary pseudoperfect number is one more than a prime then the product p(P-1) gives a Giuga number.

For instance we’ve seen that 42 x 41 = 1722. (Giuga)
And 42 x 43 = 1806 (Primary pseudoperfect)

47508 x 47507 = 2214408306 which is a Giuga number

Appendix 3

2 x 3 x 5 x 29 = 870

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

5 = (-1, -1, 0, 5)

29 = (-1,-1,-1,0)

2x3x5 = (0,0,0,30) = (0,0,0,1)

2x3x29 = (0,0,-6, 0) = (0,0,-1,0)

2x5x29 = (0,-1,0,0)

3x5x29 = (-1,0,0,0)

This doesn’t work because we have an uneven mix of +1 and -1s. The same problem applies to the next attempt:

2 x 3 x 5 x 31 = 930

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

5 = (-1, -1, 0, 5)

31 = (1, 1, 1,0)

2x3x5 = (0,0,0,30) = (0,0,0,-1)

2x3x31 = (0,0,6, 0) = (0,0,1,0)

2x5x31 = (0,1,0,0)

3x5x31 = (1,0,0,0)

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

5 = (-1, -1, 0, 5)

29 = (-1,-1,-1,0)

2x3x5 = (0,0,0,30) = (0,0,0,1)

2x3x29 = (0,0,-6, 0) = (0,0,-1,0)

2x5x29 = (0,-1,0,0)

3x5x29 = (-1,0,0,0)