3x+1

[jasong]

I've come from this website. The page in question is here.

Anyway, to quote the author about residues:

The question thus remains: can any number have a higher residue? First of all we will establish that 993 can not have any predecessors with a higher residue.

Lemma:
Every 3x+1 sequence contains at most 1 odd multiple of 3.
Proof:
Any number Si formed by taking 3 * Si-1 + 1 is obviously no multiple of 3, nor are any of its immediate descendants formed by divisions.

So in any 3x+1 sequence the contribution of odd multiples of 3 is restricted to at most a single one. The only predecessors of 993 are therefore just 993 * 2, 993 * 4 etc., which obviously have an identical residue to 993.

Can any other number, not producing 993, have a higher residue? To see that this is unlikely consider Table 1. The first six entries are all divisible by 3 and therefore have no predecessors of interest. Entry number 7 is 3,240,142,891, and it has a Residue of 1.25299194.

Now assume a number X with a residue higher than Res(993) does exist. Then X must have 'lost' quite a bit of its residue already by the time it drops below 232 for the first time. To get the 'best' chance assume it will produce the number above, 3,240,142,891.

A simple subtraction tells us that its residue is approximately 0.00015 less than Res(993). If the residue of X is to be higher than Res(993) it must have gone through a number of odd iterates. Since we assumed that X had not been below 232 before the contribution of such an odd number is limited to 1 / ( 3 * 232), or approximately 0.000000000776 (7.76 * 10-11).

Dividing 0.00015 by this maximal contribution we find that X must have passed at least 1,900,000 such odd numbers. Since after every odd number an even step occurs, the total delay for X will have to be at least 3,800,000 and that is without taking into account the further 'descent' needed after so many incremental steps, and still assuming all odd numbers make contributions of the maximum magnitude. Current data however show that below 1015 the maximum delay is only around 1860, which is nowhere near the number required. Thus most contributions will have to come from numbers beyond 1015, which requires X to have a delay of several billions.

The author feels that this is enough indication to justify

Conjecture 2b :
For all N: Res ( N ) <= Res ( 993 ) .

Maybe I'm missing something, but this "conjecture" seems to be based on the fact that it would take 100s of years of Moore's Law "iterations", assuming a brute-force attack, before we had the computing power to come up with a counter-example. In my mind, it would be the equivalent of me claiming that there is no M100, simply because I'll, in all likelihood, be dead long before it's discovered.

I'm going to put my thinking cap on and see if I can come up with a method that can come up with a higher residue number. Mind you, if I do come up with a method, the answer may be so unbelievably high that a program couldn't calculate the number. But if my method is solid, the proof will be somewhat similar to the infinitude of primes proof in explanation.

Edit:Surely, it can't be this easy. Give your critique of the following:
((3x+1)/2)^y for a high enough y to generate a better residue than R(993)

[jasong]

Sorry, I'm getting ahead of myself. My idea comes from the way the series works, so my equation makes no sense. (sorry, ADD and head-strongness again[is that a word?])

If x=1 then the equation becomes 2^y=1, which still makes no sense. Basically, I'm hypothesizing you can come up with an arbitrarily high residue by simply assigning higher and higher values of y. I haven't actually tested this, but I intend to either today or tomorrow.

So, you calculate 2^1-1, which gives the smallest possible delay, then 2^2-1, which 3, whose delay I think is 7, and then you have 7, which generates [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1] and so on.

Edit: I tested my idea, and it doesn't work. Sorry for the spamming, although this may keep people from making the same mistake.

Edit: It doesn't change the opinion I stated in the first post, it's just I don't have a way to come up with a counter-example.

[jasong]

Basically, for the residue to be high, most or all even values would have to turn into odd values on the next iteration, so ((3x+1)/2)^y would have to be odd, ((3x-1)/2)^(y-1) would have to be odd, and so on for at least a million iterations, with y being over a million to begin with. Well, not every iteration would have to be odd than even, but considering that every 3x+1 produces an even number(since x is always even, which is a requirement for the 3x+1 step to be done) the vast majority of even numbers would have to immediately become odd after division by 2.

[jasong]

Okay, I think this problem is solvable, but the recursion involved would probably be a real hassle to program. Basically, you'd have to find a way to generate numbers that alternate odd/even within the problem. The question is whether or not one iteration can be used to lead to the next.

I'm going to think about this a little more, not sure whether I'm onto something or not. Probably not, but it's a fun thought problem.

[jasong]

Okay, sorry about all the posts in a row. I'm not going to add anything after this unless it's after work tomorrow, minimum 13hrs45min from now, or I feel the need to respond to someone.

I'm thinking that until an iteration reaches a value of 4, each value, starting with the 5th to the last value, has to be done so that the previous x has to be of the form 2a+1 with 'a' even. So, for many iterations, I think we would get the more specific form of (3(2a+1)+1)/2=(another odd value).

One would have to go through the ns sequentially, keeping track of the best of these in order to find better and better combinations. Not sure if it's possible to accomplish. Shortcuts would be necessary for the problem to be solved within our lifetime.