Foolproof?
This challange has been presented as hard and so far unsolved. Prove or disprove that the while loop terminates for a given value of x, where x is initially > 1.
int x = ...;
while (x > 1){
if (x % 2 == 0)// x is even
x = x / 2;
else
x = 3 * x + 1;
}
Do you recognize this as an unsolved problem from somewhere? I'm asking because I gave it a shot and came up with this quite simple proof.
--
You have two expressions,
1. x = x/2 (when x even)
and
2. x = 3*x + 1 (when x odd)
If both expressions were evaluated equally often the second expression would 'win out' in the long run. X would always increase and never terminate. But are they evaluated equally often? The second expression will only be avaluated once in a row because it always produces an even result. The first expression though will be evaluated as long as x stays even (is evenly divisible with 2). How often does this happen? If you look at the rightmost three bits of x after it has been evaluated in the second expression you find these bitpatterns equally often,
....000, divisible with 8
....010, divisible with 2
....100, divisible with 4
....110, divisible with 2
This means that when x enters the first expression it's not only always divisible with 2 but it's divisible with 4 on average (0.25*8 + 0.25*2 + 0.25*4 + 0.25*2). (if you take more bits into account the 4 will increase somewhat).
And this means that the first expression actually performs x = x/4 on average each time it gets a shot and this will 'beat' the second expression in the long run. So x always terminates!
--
Is there a mistake somewhere? Does it hold up formally you think?
[1995 byte] By [
UlrikaJa] at [2007-9-29 18:24:03]
I think your logic that one expression is evaluated more than the other seems correct. However, I don't think you have addressed the possibility of a cycle. In other words, how does your proof prove there is no cycle, or does it?
I can't offer anything formal here, just of hunch
x=x/4 on avg. for the first block, vs. 3x+1 always for the second, yes? The thing is the x=x/4 on avg. came out of the question, "Will they be evaluated equally often?"
It seems you've determined what the comparative average effects are, but not the relative frequencies of the blocks. We know that the second one is evaluated at most once in a row... hmmm.. wait, train of thought suddenly thrown to diferent track...
okay, so 3x+1 is always even, so after block #2 runs once, block #1 must execute at least once, so #2 executes <= the number of times that #1 does.
Okay, nevermind.
I gotta go look at that "divisible by 4" probability again.
jverda at 2007-7-15 17:55:20 >
> okay, so 3x+1 is always even, so after block #2 runs
> once, block #1 must execute at least once, so #2
> executes <= the number of times that #1 does.
Yes, when #2 has been evaluated once, #1 is evaluated twice on average. That's why #1 basically is equivalent to x/4 (x/2/2). So there's a tendency for x to decrease. But that cycle thing, hmm.
What's the exact challenge? General proof that it always or never terminates, or that you can determine it based on x? Or just pick an x and prove for that x? Not sure of terms.
Anway.
If x is ever 2:
2%2 == 0
so x = 2/2 --> x =1
1%2 != 0
so x = 3 * 1 + 1 --> x = 4
which leads to 2 which leads to 4...
So if x is ever 2, you'll have a cycle.
If x is ever 4, x will become 2, and you'll have a cycle.
I think if x is ever a power of 2, you'll /2 down to x = 1, which pushes you to 4, which puts you to 2 which ends up lasting nearly as long as an argument with daFfy.
So, can one determine whether it does or does not become a power of 2 for a given or any or whatever the terms of the proof are number?
Can 3x + 1 be a power of 2? Well, if x=5, sure. So, if x can get to 5, we'll never terminate. Likewise 21.
jverda at 2007-7-15 17:55:20 >
> x =1when x == 1 the loop terminates: while (x > 1) { ...
> > x =1> > when x == 1 the loop terminates: while (x > 1) { ...> OP: "...were x is initially > 1"
jverda at 2007-7-15 17:55:20 >
> Can 3x + 1 be a power of 2? Well, if x=5, sure. So, if
> x can get to 5, we'll never terminate. Likewise 21.
Also if x is ever a power-of-two multiple of 5 or 21, we end up nonterminating.
For what other numbers is 3x+1 a power of 2? For those numbers any power-of-2 multiple of those, nonterminating.
So, if x is ever a power of 2, or a number N s.t. 3N + 1 is power of two, or a power of 2 multiple of one of those Ns or... etc. recursively to describe all numbers that can lead to this state.
No clue what this tells us--if anything--about the general case.
jverda at 2007-7-15 17:55:20 >
5 -> 3 * 5 + 1 = 16 -> 8 -> 4 -> 2 -> 1 (termination)What are you smoking!?
public class ThreeXPlusOne {
public static void main(String[] args) {
int x = Integer.parseInt(args[0]);
while (x > 1) {
if (x % 2 == 0) // x is even
x = x / 2;
else
x = 3 * x + 1;
System.out.println(x);
}
}
}
> If you
> look at the rightmost three bits of x after it has
> been evaluated in the second expression you find these
> bitpatterns equally often,
>
> ....000, divisible with 8
> ....010, divisible with 2
> ....100, divisible with 4
> ....110, divisible with 2
>
Why do those bit patterns occur with equal frequency?
> This means that when x enters the first expression
> it's not only always divisible with 2 but it's
> divisible with 4 on average (0.25*8 + 0.25*2 + 0.25*4
> + 0.25*2).
Huh? I don't think you can get to "/4 on average" from that.
.25 you get 3 turns when you enter exp 1 (8)
.25 you get 1 turn (2)
.25 you get 2 turns (4)
.25 you get 1 turn (2)
.25 * (3 + 1 + 2 + 1) = .25 * 7 = 1.75
On average, you get 1.75 trips through the first one. So, on average, the first one does "x/2" 1.75 times. What does that mean though? Whats "One and three quarters of a division by 2"? Do you divide by 2 and then divide that by 3/4 of 2 --> x=x/2/1.5? Is it a logarithmic thing?
I suppose you could say that after entering the loop 100 times, you will have divided by 2 175 times. I don't see where that gets you though.
jverda at 2007-7-15 17:55:20 >
> 5 -> 3 * 5 + 1 = 16 -> 8 -> 4 -> 2 -> 1 (termination)
>
> What are you smoking!?
Oh, jeez.
Okay, I finally got the point of your "while (x>1)" post.
@!&*@^!!#!
Man, it's gonna be hard to stay arrogant after this one.
Okay, slight attempt to save face: All those rules I derived still hold, it's just that you replace "loops forever" with "terminates". They all came down to looking for cases where x becomes 1. I just applied the wrong consequence to that. Er... right?
Now bring me my pipe.
jverda at 2007-7-15 17:55:20 >
So can it be determined under what circumstances a number can or cannot lead to either:
1) a power of 2
2) a number N s.t. 3N + 1 is a power of 2
3) a number that is a power-of-2 multiple of a number that matches #2
4) a number M s.t. 3M + 1 matches #3
... and so on recursively. Wish I knew how to express it without recursion.
We know these terminate, and I think these are the only ones that terminate, since x has to become 1, and the only way for that to happen is to be right shifted from a power of 2. Erm, yes? Or am I still smoking?
jverda at 2007-7-15 17:55:21 >
Just playing around a bit.
public class ThreeXPlusOne {
public static void main(String[] args) {
int min = Integer.parseInt(args[0]);
int max = Integer.parseInt(args[1]);
for (int ix = min; ix <= max ; ix++) {
int x = ix;
int numPasses = 0;
System.out.print("" + ix + ": ");
while (x > 1) {
if (x % 2 == 0) // x is even
x = x / 2;
else
x = 3 * x + 1;
numPasses++;
System.out.print("" + x + " ");
}
System.out.println();
System.out.println("" + ix + " took " + numPasses + " passes.");
System.out.println();
}
}
}
Numbers up to 100000 all converge. The five slowest were
91463 took 332 passes.
60975 took 334 passes.
78791 took 337 passes.
52527 took 339 passes.
77031 took 350 passes.
jverda at 2007-7-15 17:55:21 >
> I suppose you could say that after entering the loop
> 100 times, you will have divided by 2 175 times. I
> don't see where that gets you though.
The way I came up with 4 was wrong. So how many times are #1 executed on average for each execution of #2. If the last 3 bits of x are taken into account it's 1.75 (7/4) as you say. But if 4 bits are included it becomes 1.875 (15/8). I would guess this number approaches 2 when all bits are included.
This will get me to the point where I can say that #1 is run twice on average for each execution of #2. And two x = x/2 equals one x = x/4. That would tip the balance in favour of the part of the algoritm that decreases x, so x would approach 1 and the loop would terminate.
Unfortunately, even though the algoritm shows a tendency to terminate, this doesn't take possible cycles into account that would keep it going for ever (as rkippen has pointed out). Back to the drawing board -:)
> > If you
> > look at the rightmost three bits of x after it has
> > been evaluated in the second expression you find these
> > bitpatterns equally often,
> >
> > ....000, divisible with 8
> > ....010, divisible with 2
> > ....100, divisible with 4
> > ....110, divisible with 2
> >
>
> Why do those bit patterns occur with equal frequency?
It's because x is any even number.
> > > If you
> > > look at the rightmost three bits of x after it
> has
> > > been evaluated in the second expression you find
> these
> > > bitpatterns equally often,
> > >
> > > ....000, divisible with 8
> > > ....010, divisible with 2
> > > ....100, divisible with 4
> > > ....110, divisible with 2
> > >
> >
> > Why do those bit patterns occur with equal
> frequency?
>
> It's because x is any even number.
But that doesn't mean we get every even number with same probability, for a given x.
For example if x is a power of two we don't get numbers greater then x
and we only get one number of the third type, one of the second, none of the fourth and if x is large enough a arbitrary number of type 1 numbers.
Anyway, any probabilistic aproach at most show that it is likely to converge or not to converge, but not that it actually does converge.
regards
Spieler
> Do you recognize this as an unsolved problem from
> somewhere? I'm asking because I gave it a shot and
> came up with this quite simple proof.
I think I've read this in the book 'Gdel, Escher, Bach' by Hoffstaetter,
and I think he considered it unsolved.
regards
Spieler
this is an extremely famous open problem in mathmatics/computer science http://www.google.com/search?sourceid=navclient&q=collatzasjf
asjfa at 2007-7-19 16:49:38 >
> > > Why do those bit patterns occur with equal frequency?
> >
> > It's because x is any even number.
>
> But that doesn't mean we get every even number with
> same probability, for a given x.
> For example if x is a power of two we don't get
> numbers greater then x
> and we only get one number of the third type, one of
> the second, none of the fourth and if x is large
> enough a arbitrary number of type 1 numbers.
Okay, but x can't be a power of 2 when it enters #2. It's always an odd number ending with one of these three bit patterns,
.001
.011
.101
.111
Binary calculation of x = 3x + 1 (as x + x<<1 + 1) gives
.001 // x
.010 // x<<1
.001 // +1
-
.100
.011
.110
.001
-
.010
.101
.010
.001
-
.000
.111
.110
.001
-
.110
Thus when x enters #1 again it ends with one of these,
.100
.010
.000
.110
And these are exactly the bit patterns I've proposed are equally probable (if x is arbitrarily choosen to begin with).
> Anyway, any probabilistic aproach at most show that it
> is likely to converge or not to converge, but not that
> it actually does converge.
Yes I know, I've come to realize that (in reply 14). Even if you can prove a tendency to convergence you must show that there are no cycles. Anyway it's good to see that it's an open problem now that my 'proof' is falling apart. A fools proof indeed -:)
> this is an extremely famous open problem in> mathmatics/computer scienceCool, if we solve it this forum could claim the 1000 pounds collectively!
> > this is an extremely famous open problem in
> > mathmatics/computer science
>
> Cool, if we solve it this forum could claim the 1000
> pounds collectively!
that would go down well, although i think the academic recognition would be pretty **** good on its own..
now back to finding that proof.. :)
btw. the mathematician paul erdos (who was important enough to spawn erdos numbers http://www.oakland.edu/~grossman/erdoshp.html) said of this that "mathematics isn't ready for such problems"
anyhow, heres some code is related - was interested in trying to visualise the problem but didn't get too far..import java.math.*;
import java.util.*;
import java.io.*;
public class Collatz {
public static final BigInteger ZERO = BigInteger.ZERO;
public static final BigInteger ONE = BigInteger.ONE;
public static final BigInteger TWO = ONE.add(ONE);
public static final BigInteger THREE = ONE.add(TWO);
public static final Comparator collatzStringComparator = new Comparator() {
public int compare(Object o1, Object o2) {
String s1 = (String) o1, s2 = (String) o2;
return s1.length() == s2.length() ? s1.compareTo(s2) : s1.length()-s2.length();
}
public boolean equals(Object o){return o==this;}
};
public static List collatz(BigInteger i) {
List result = new LinkedList();
while(i.compareTo(ONE)>0) {
result.add(i);
if(i.mod(TWO).equals(ZERO))
i = i.divide(TWO);
else
i = i.multiply(THREE).add(ONE);
}
return result;
}
public static String toCollatzString(BigInteger i) {
StringBuffer result = new StringBuffer();
while(i.compareTo(ONE)>0) {
if(i.mod(TWO).equals(ZERO)) {
i = i.divide(TWO);
result.append(".");
}
else {
i = i.multiply(THREE).add(ONE);
result.append("@");
}
}
return result.toString();
}
public static BigInteger parseCollatzString(String s) {
BigInteger result = new BigInteger("1");
for(int i=s.length(); i>0; i--) {
switch(s.charAt(i-1)) {
case '.': result = result.multiply(TWO); break;
case '@': result = result.subtract(ONE).divide(THREE); break;
default: throw new IllegalArgumentException("Bad string format");
}
}
return result;
}
public static void main(String [] arg) throws Exception {
BigInteger LIMIT = new BigInteger("1000");
List ss = new LinkedList();
for(BigInteger i = TWO; i.compareTo(LIMIT)<0; i=i.add(ONE))
ss.add(toCollatzString(i));
Collections.sort(ss,collatzStringComparator);
for(Iterator i = ss.iterator(); i.hasNext(); )
System.out.println(i.next());
}
}
and
import javax.swing.*;
import java.awt.*;
import java.awt.image.*;
import java.math.*;
import java.util.*;
import java.util.List;
public class CollatzBase2 extends JComponent {
Dimension mySize, mySize2;
GraphicsConfiguration defaultConfiguration;
Graphics2D offGraphics;
BufferedImage offScreen;
List ss;
public CollatzBase2(BigInteger LIMIT) {
Set s = new HashSet();
ss = new ArrayList();
s.add(".");
Set toProcess = s;
int maxlength=30;
for(int j=0; j<maxlength-1; j++) {
Set newSet = new HashSet();
for(Iterator i = toProcess.iterator(); i.hasNext(); ) {
String cs = (String) i.next();
String csdot = "."+cs;
String csat = "@"+cs;
BigInteger v = Collatz.parseCollatzString(cs);
newSet.add(csdot);
if(v.subtract(Collatz.ONE).mod(Collatz.THREE).equals(Collatz.ZERO)) {
BigInteger v2 = Collatz.parseCollatzString(csat);
if(!v2.equals(Collatz.ZERO) && !v2.equals(Collatz.ONE))
newSet.add(csat);
}
}
//System.out.println(newSet);
toProcess = newSet;
ss.addAll(newSet);
}
mySize = new Dimension(maxlength,ss.size());
mySize2 = new Dimension(maxlength, 100);
}
private void initGraphics() {
defaultConfiguration = getGraphicsConfiguration();
offScreen = defaultConfiguration.createCompatibleImage((int)mySize.getWidth(), (int) mySize.getHeight());
offGraphics = offScreen.createGraphics();
Collections.sort(ss,Collatz.collatzStringComparator);
Color c;
for(int y=0; y><ss.size(); y++) {
String s = (String) ss.get(y);
s = new StringBuffer(s).reverse().toString();
for(int x=0; x><mySize.getWidth(); x++) {
switch(x><s.length() ? s.charAt(x) : 'p') {
case '.': c = Color.BLACK; break;
case '@': c = Color.WHITE; break;
default : c = Color.RED;
}
offGraphics.setColor(c);
offGraphics.drawRect(x,y,0,1);
}
}
}
public static void main(String [] arg) {
JFrame frame = new JFrame("CollatzBase2");
CollatzBase2 cb = new CollatzBase2(new BigInteger("50000"));
//frame.setResizable(false);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.getContentPane().add(new JScrollPane(cb));
frame.pack();
frame.show();
frame.setEnabled(true);
}
public void paintComponent(Graphics g) {
if(offScreen!=null)
g.drawImage(offScreen,0,0,null);
else {
initGraphics();
}
}
public Dimension getPreferredSize() {return mySize;}
public Dimension getMaximumSize() {return mySize;}
public Dimension getMinimumSize() {return mySize2;}
}
asjf>
asjfa at 2007-7-19 16:49:38 >
> anyhow, heres some code is related - was interested in
> trying to visualise the problem but didn't get too
> far..
I've been talking to Baron Trenck about it. (As a matter of fact a whole six-pack of it -:) And I think I've come up with a whole new approach. If it sticks until tomorrow I've a solution to this problem. See you.
2 options:Control+Cpull plug
> 2 options:> > Control+C> > pull plugSo what kind of ***-hole are you?
> What's the exact challenge? General proof that it
> always or never terminates, or that you can determine
> it based on x? Or just pick an x and prove for that x?
> Not sure of terms.
>
> Anway.
>
> If x is ever 2:
> 2%2 == 0
> so x = 2/2 --> x =1
> 1%2 != 0
> so x = 3 * 1 + 1 --> x = 4
>
> which leads to 2 which leads to 4...
It does? Seems to me:
if x is 2 then...
2%2 = 0, so x = 2/2 --> x = 1;
did if, so skip else, loop back, while x > 1 is false, terminate loop
or did I miss something?
Any other number > 2 would get stuck.
> > 2 options:> > > > Control+C> > > > pull plug> > So what kind of ***-hole are you?the arrogant kind? What? Does it not cause the loop to exit or does it?
> > > 2 options:
> > >
> > > Control+C
> > >
> > > pull plug
> >
> > So what kind of ***-hole are you?
>
> the arrogant kind? What? Does it not cause the loop
> to exit or does it?
Well, run the method and find out for yourself! This is not a newbie thread.
> Well, run the method and find out for yourself! This
> is not a newbie thread.
> Well, run the method and find out for yourself! This is not a newbie thread.
Well, I wouldn't call myself a newbie, but I'm certainly not a mathematition either. Don't get so **** huffy. Post your proof and let's move on.
int x = 27;
while (x > 1) {
if (x % 2 == 0) // x is even
x = x / 2;
else
x = 181 * x + 1;
}
Note the minor modification from "3" to "181".
This loop never terminates, so any proof of when such kN+1 loops terminate must not prove that they always do.
Let me blow your original proof out of the water:
You said "(if you take more bits into account the 4 will increase somewhat)". Yes, somewhat. You took 3 bits into account and got 4. If you take n bits into account the result is always n+1. (Proof left as an exercise.)
You said "And this means that the first expression actually performs x = x/4 on average each time it gets a shot..." Since the "4" has been replaced by any number at all, this doesn't apply.
> Note the minor modification from "3" to
> "181".
How did you get those numbers. You didn't do it by trial and error.
> This loop never terminates, so any proof of when such
> kN+1 loops terminate must not prove that they always
> do.
I'm not convinced that the original version always terminates either.
> Let me blow your original proof out of the water:
The 'proof' was built on the faulty assumption that if the division by 2 occurs more often than the multiplication that the loop must terminate. Your example is a perfect counter example showing the incorrectness of the assumption.
> > Note the minor modification from "3" to
> > "181".
>
> How did you get those numbers. You didn't do it by
> trial and error.
No, not by trial and error. Here's how:
Start with an initial value V. Multiply by k and add 1; divide by 2^a; multiply by k and add 1; divide by 2^b; and you end up with V. If you solve this for V you get V = (k + 1) / (2^c - k^2).
I don't think there's a general solution for this, but since V is an integer then 2^c - k^2 must be small. Apart from the trivial solutions, the only non-trivial solution I could find was k=181 and V=27, since 32768 - 181^2 = 7.
I did this a long time ago, so I didn't write a program to look for more values. That wouldn't be hard at all and I invite you to do it. Also I only looked at the case where the sequence alternated between V and something else; there are more complicated possibilities.
> I did this a long time ago, so I didn't write a
> program to look for more values. That wouldn't be hard
> at all and I invite you to do it. Also I only looked
> at the case where the sequence alternated between V
> and something else; there are more complicated
> possibilities.
I was trying to think of way to disprove that the loop must terminate for all values > 1 or come upon a proof by contradiction in the process (though, I'm not that deluded that I think I'd find the answer to something like this in my spare time.)
I came up with this much:
The mst simple way that this process could get caught in a loop is described by these equations:
y = b * 3 + 1
b = y / 2^n
where y is an even number and b is a odd number.
a little magic and you get:
(2^n * y) - (3 * y) = 2^n
if you start solving with some values of n it becomes pretty obvious that y starts at less than 2 and goes to 1 as n goes to infinity.
So if I haven't made a mistake here, that means there is no simple loop there would have to be a loop of multiple steps.
> So if I haven't made a mistake here, that means there> is no simple loop there would have to be a loop of> multiple steps.If there is a loop, there is.
arrg. If there is a loop, that is.
Okay, I was thinking this thru a little, and I know I said I'm not a math guy, but this is what I came up with...
From what was posted, the only constraints are these:
- x must be greater then 1 to start.
- To break the loop, x must become less than or equal to 1.
- If x is even (x % 2 == 0), then x will be divided by 2 (and loop again).
- Else if x is odd, x will be multiplied by 3 and one added to the result (and loop again).
And the goal is to prove that, given any value for x where x > 1, it will break out of the loop (eventually), or not, correct? So I say yes it will always because:
- The only even int value > 1 that will result in 1 (and thus break the loop) would be 2 (2/2 == 1). Anything higher will be still be greater than 1. But any power of 2, when divided by 2 enough times will end up being 2, and then 1, so any power of 2 will work.
- Any other even int when divided by 2 value will result in an odd or even number.
- Any odd number will go thru the else part, the result of which can be odd or even. This may or may not be a power of 2, but if it is, it'll fall thru quickly.
So the real proof is whether or not any other int that is not a power of 2 will end up becoming a power of 2 via that formula, and thus ultimately 1 to break the loop.
However, I think due to any other lack of constraints (particularly, the allowed number of bits used to define the number), it sounds vaguely like a trick question.
Any odd number value that calculates (via: 3 * x + 1, since dividing by 2 will be a smaller result) to be higher then Integer.MAX_VALUE will roll over to a negative value, thus being <= 1, thus breaking the loop.
So any value of x will break the loop. It'll either:
A) Degrade via the provided formulas to 1 or
B) Roll over the max value that fits in the given number of bits to be negative (or zero). (And this should apply no matter how many bits are used, eventually.)
Case in point:
Starting with x = 99999999
x = 299999998
x = 149999999
x = 449999998
x = 224999999
x = 674999998
x = 337499999
x = 1012499998
x = 506249999
x = 1518749998
x = 759374999
x = -2016842298
done
Let the snide remarks begin...
Unless, of course, we are assuming an infinite number of bits to represent any possible number value.
> Any odd number value that calculates (via: 3 * x + 1,
> since dividing by 2 will be a smaller result) to be
> higher then Integer.MAX_VALUE will roll over to a
> negative value, thus being <= 1, thus breaking the
> loop.
We'll that's a technicality that isn't part of the real equation. Also you are ignoring the possiblity that the loop falls into a regular pattern like the one in DrClaps modified version.
> > Any odd number value that calculates (via: 3 * x +
> 1,
> > since dividing by 2 will be a smaller result) to be
> > higher then Integer.MAX_VALUE will roll over to a
> > negative value, thus being <= 1, thus breaking the
> > loop.
>
> We'll that's a technicality that isn't part of the
> real equation. Also you are ignoring the possiblity
> that the loop falls into a regular pattern like the
> one in DrClaps modified version.
That's true, it's not as part of the equation as such, but I'm not sure where this originally came from and what the exact constraints are (the OP didn't include that info). If there no constraint of limiting the number of bits to define the value of x, then it'll never roll over.
DrClap did find that, but as you said, on a modified version, which is not the particular equation being discused. Or is there no constraint in what the constant values (2 and 3 and 1) being used in the formula are either?
Given a bit limit, one could pretty easily run thru all possible values and find out if it ever stops printing. It might take a long time for larger numbers of bits, of course.
Anyway, part of my point is that without really defining clearly what the proper constraints or allowances are, I'm not sure it's valid to say you could provide a proof one way or another.
i think a more interesting way to solve it is to consider what
properties does some number have that all numbers that pass do
not have ...
considering it gets very high, (all numbers < 4mil pass, at least)
then it would be interesting to wonder what those properties could
be, wouldn't it ?
> DrClap did find that, but as you said, on a modified
> version, which is not the particular equation being
> discused. Or is there no constraint in what the
> constant values (2 and 3 and 1) being used in the
> formula are either?
The point is that it's entirely possible there is such a loop in the given equation. Can you show that there isn't?
> Given a bit limit, one could pretty easily run thru
> all possible values and find out if it ever stops
> printing. It might take a long time for larger
> numbers of bits, of course.
You'd have to check for a pattern otherwise you can't know if it 'never' stops. It could also take a really really long time, like longer than the universe will exist.
> Anyway, part of my point is that without really
> defining clearly what the proper constraints or
> allowances are, I'm not sure it's valid to say you
> could provide a proof one way or another.
There are plenty of links in this thread about the general problem. Regardless of whether there is a limit or not, you haven't shown there are not looping patterns for certain values of x (actually there need be only one.)
> > Given a bit limit, one could pretty easily run thru
> > all possible values and find out if it ever stops
> > printing. It might take a long time for larger
> > numbers of bits, of course.
>
> You'd have to check for a pattern otherwise you can't
> know if it 'never' stops. It could also take a really
> really long time, like longer than the universe will
> exist.
Right. Given an infinite number of bits to represent x (or a fairly large amount), for that formula, you'd have to find a pattern, otherwise you couldn't wait that long to test it.
> There are plenty of links in this thread about the
> general problem. Regardless of whether there is a
> limit or not, you haven't shown there are not looping
> patterns for certain values of x (actually there need
> be only one.)
I know, I haven't, and I probably won't figure it out myself either, so I'll await UlrikaJ answer he said he'd post tomorrow. Except to say that if, by that looping formula, the result becomes a power of 2 for any given value of x, then it will always will break the loop. So that's what needs to be determined, yes?
> > which leads to 2 which leads to 4...
>
> It does? Seems to me:
>
> if x is 2 then...
> 2%2 = 0, so x = 2/2 --> x = 1;
> did if, so skip else, loop back, while x > 1 is false,
> terminate loop
>
> or did I miss something?
>
> Any other number > 2 would get stuck.
Yes, it leads to 1 which I thought led to 4, before you pointed out that very cleverly hidden while (x>1).
Instead, this is part of that "I was right about the analysis, but flip-flopped the conclusions." Any number which gets you to a power of two gets you to one. One terminates (obviously). I just originally thought it cycled.
jverda at 2007-7-19 16:49:43 >
> considering it gets very high, (all numbers < 4mil> pass, at least)initial x <= 500,000,000 all pass.
jverda at 2007-7-19 16:49:43 >
Just a point of curiosity (well for me at least):
For numbers up to 32000, I graphed iterations to terminate vs. initial value of x. It oscillated a lot of course, but the horizontal axis was squished enough that it was almost a filled area, rather than a bunch of dots, on the screen. The top of this area--i.e. the max iterations it took within some small range of initial values--looked like it was asymptotically--or at least very, very slowly--approaching somewhere around 300-350.
I didn't look at the max iterations for my 500,000,000 run, but I might do that tonight.
I realize this doesn't help the proof. It's just something I consider an interesting property of how the thing behaves.
jverda at 2007-7-19 16:49:43 >
> For numbers up to 32000, I graphed iterations to terminate [...]Code for it :) ?
I will give you a hint of the proof:
Suppose there is a cycle, then that cycle contains N
3x + 1 operations. Suppose N = 1, a.k.a. there is
a simple cycle. Then:
3x + 1 = x * (2^n)
x is the starting #
n is the # of divisions by 2.
In other words, starting from x, if there is a simple
cycle then 3 * x + 1 will be equal multiplying x by
2, n times. The value of n represents the number of
multiplications of 2, and can take the values:
1, 2, 3, 4, ... infinity.
Solving for x:
x = (-1) / (3 - (2^n))
Recall that we are interested in an integer solution for x > 1.
Thus, we will try different values of n:
n = 1, x = -1
Indeed, x == -1 does form a cycle (excluding the termination
condition). That is, -1 * 3 + 1 = - 2, -2 / 2 = -1, repeat.
n = 2, x = 1
Indeed, x == 1 does form a cycle (excluding the termination
condition). That is, 1 * 3 + 1 = 4, 4 / 2 = 2, 2 / 2 = 1, repeat.
n = 3, x = -1 / (3 - 8) = 1 / 5.
Indeed, x = 1 / 5 does form a cycle. However, we are interested
in an integer solution for x.
In fact, n >= 3 produces values of x that are fractions. Therefore
there is no integer value of x > 1 that forms a simple cycle.
I just printed out to a file and imported that into excel. Here's the code I'm running right now:
public class ThreeXPlusOne {
public static void main(String[] args) {
long min = Long.parseLong(args[0]);
long max = Long.parseLong(args[1]);
outer:
for (long ix = min; ix <= max ; ix++) {
long x = ix;
long numPasses = 0;
while (x != 1) {
if (x <= 0) {
System.out.println(ix + " OVERFLOW");
continue outer;
}
if (x % 2 == 0) // x is even
x = x / 2;
else
x = 3 * x + 1;
numPasses++;
}
System.out.println("" + ix + " " + numPasses);
}
}
}
jverda at 2007-7-19 16:49:48 >
i wonder, not that it is such a concern in java, if this is
much faster ... :while(n > 1){
if( (n & 1) == 0 )
n >>= 1;
else
n = n << 1 + n + 1;
}
and i wonder if there is a way to express is without
the if statement at all, i think this would do it:int t = n & 1;
n = n >> (t * 1);
n = t * ((n << 1) + n + 1);
perhaps there is a better way :)
no wait, that doesn't work :)
here we go, this works ... :int t;
int n = ...;
while(n > 1){
t = n & 1;
n = n >> (t ^ 1);
n = (t * ((n << 1) + 1)) + n;
}
Wow, that should be very fast...
throwing a bit more java at itimport java.util.*;
import java.math.*;
public class CollatzGraph1 {
public static final BigInteger ZERO = BigInteger.ZERO;
public static final BigInteger ONE = BigInteger.ONE;
public static final BigInteger TWO = ONE.add(ONE);
public static final BigInteger THREE = ONE.add(TWO);
public static final BigInteger FOUR = THREE.add(TWO);
static int id=0;
static Map bi2id = new HashMap();
static Set edgeset = new HashSet();
static StringBuffer nodes = new StringBuffer();
public static void main(String [] arg) {
List done = new LinkedList();
List todo = new LinkedList();
todo.add(TWO.multiply(TWO).multiply(TWO));
for(int i=0; i<500; i++)
process(todo,done);
System.out.println("graph [");
System.out.println(nodes);
for(Iterator i = edgeset.iterator(); i.hasNext(); )
System.out.println(i.next());
System.out.println("]");
}
public static void process(List todo, List done) {
if(todo.size()==0) return;
BigInteger i = (BigInteger) todo.remove(0);
if(i.equals(FOUR)) return;
nodes.append("node [\nid "+getID(i)+"\nlabel \""+i+"\"\n]\n");
BigInteger r = i.multiply(TWO);
if(!r.equals(FOUR)) {
todo.add(r);
edgeset.add("edge [\nsource "+getID(i)+"\ntarget "+getID(r)+"\n]\n");
}
if(i.subtract(ONE).mod(THREE).equals(ZERO)) {
BigInteger l = i.subtract(ONE).divide(THREE);
if(!l.equals(FOUR)) {
todo.add(l);
edgeset.add("edge [\nsource "+getID(i)+"\ntarget "+getID(l)+"\n]\n");
}
}
}
public static String getID(BigInteger i) {
if(!bi2id.containsKey(i)) {
bi2id.put(i,""+(id++));
}
return (String) bi2id.get(i);
}
}
this will generate a graph in GML format so you can dojava CollatzGraph1 > test.gml
and then use a graph application such a yed
http://www.yworks.com/en/products_yed_about.htm
to look at it, and it does look quite nice :)
asjf
asjfa at 2007-7-19 16:49:48 >
> here we go, this works ... :
> int t;
> int n = ...;
> while(n > 1){
> t = n & 1;
> n = n >> (t ^ 1);
> n = (t * ((n << 1) + 1)) + n;
> }
i don't understand!
btw, speed isn't an issue? the numbers get big quickly so BigInteger must be used, so i'd guess memory is more likely to be an issue. On the other hand if the above code is correct then its not far off a recurrence relation (?)
asjfa at 2007-7-19 16:49:48 >
> Let me blow your original proof out of the water:
>
> You said "(if you take more bits into account the 4
> will increase somewhat)". Yes, somewhat. You took 3
> bits into account and got 4. If you take n bits into
> account the result is always n+1. (Proof left as an
> exercise.)
>
> You said "And this means that the first expression
> actually performs x = x/4 on average each time it gets
> a shot..." Since the "4" has been replaced by any
> number at all, this doesn't apply.
I've modified this a bit (see my reply 14). I think I've proven that the x/2 statement executes on average close to 2 times as often as x = 3*x + 1.
I've taken a second shot at a proof. The first just showed (at least I think so) that statement #1 is executed twice as often on average as #2 so there's a probabilistic tendency of termination.
int x = ...;
while (x > 1) {
if (x % 2 == 0)// x is even
x = x / 2;// expression #1
else
x = 3 * x + 1; // expression #2
}
The idea this time is to transform the algoritm so it can be more easily handled. I consider one full iteration of the while loop. If X is odd to start with it's going to be odd again after one iteration.
This question is central: If I want the algoritm to land on a specific number O after one iteration what numbers can X be? I've come to the conclussion that these will,
X = (O*2^n - 1)/3, where n = 1 - ....
Let's say I want the algoritm to land on 1 (O=1), what numbers X will do that? One X number is 5 (n=4) and one is 21 (n=6). Checking with the algoritm (5*3 + 1)/2^4 = 16/16 = 1, and (21*3 + 1)/2^6 = 64/64 = 1.
I'm going to call the set of all X numbers for a given O the reduction set of O. These are the 5 first,
RS_1 = {1, 5, 21, 85, 341, 1365, 5461, 21845, 87381}
RS_3 = {}
RS_5 = {3, 13, 53, 213, 853, 3413, 13653, 54613, 218453}
RS_7 = {9, 37, 149, 597, 2389, 9557, 38229, 152917}
RS_9 = {}
(Each set is infinite so this isn't all numbers in each set).
This is how you use the reduction sets. Say you start the algoritm with X=53. Locate 53 in a reduction set. You find it in RS_5 meaning the algoritm will reduce 53 to 5 in one iteration. Now locate 5. You find it in in RS_1 meaning the algoritm will reduce 5 to 1 in one iteration.
Basically the initial algoritm has been replaced by this,
long x = 53;
while (x != 1) {
x = findMember(x); // find member in a reduction set and return it's number
}
I'm coming back proving some stuff about reduction sets. This can all be mumbo jumbo but I'm sure you'll let me know -:)
> X = (O*2^n - 1)/3, where n = 1 - ....
First a comment. X and O are always odd numbers. (O*2^n - 1) must be evenly divisible by 3.
To show that the algoritm terminates this must be proven,
1. All odd numbers are present in the RS.
2. Each number can only be present in one RS.
3. There are no cycles. You can never come back to a RS you've visited.
--
1. All odd numbers are present in the RS.
I need help with this. What must be shown is that if O is any odd number (O*2^n - 1)/3 maps to all odd numbers.
2. Each number can only be present in one RS.
We have any two reduction sets RS_O1 and RS_O2,
RS_O1 = (O1*2^n - 1)/3
RS_O2 = (O2*2^k - 1)/3
For one number to be present in both this equality should hold,
(O1*2^n - 1)/3 = (O2*2^k - 1)/3
=>
O1*2^n = O2*2^k
=>
O1*2^(n-k) = O2
If n-k is 0 then O1 = O2 which is obviously false. If n-k is >= 1 then O1*2^(n-k) is even while O2 is odd which is a contradiction. So the equality doesn't hold and the same number can't be in two different reduction sets !!!
3. There are no cycles. You can never come back to a RS you've visited.
Example,
RS_31 = {35, ......}
RS_35 = {31, ......}
Say X is 35. You locate it in RS_31. You then look for 31 and locate it in R_35. X is then back to 35 again. The algoritm will cycle back and forth forever and never terminate.
Longer loops are possible but I start with this minimal 2-cycle which can be expressed like this,
1. O2 = (O1*2^n - 1)/3
2. O1 = (O2*2^k - 1)/3
The reduction set number O2 of RS_O2 is present in the RS_1 and the other way around. I solve the equation system by insering equation 1 in 2,
O1 = ([(O1*2^n - 1)/3]*2^k - 1)/3
This can be reduced to (and I hope I got it right here),
O1 = (3 + 2^k) / (2^(k+n) - 9)
The interesting thing about this is that Q1 is alway < 1. This means for a cycle to happen Q1 must be less then 1 which it never is. So 2-cycles can't happen !!!
I've done the same for a 3-cycle,
3. O3 = (O1*2^m - 1)/3
2. O2 = (O3*2^n - 1)/3
1. O1 = (O2*2^k - 1)/3
Solved in the same manner gives,
O1 = (9 + 3*2^k + 2^(k+n)) / (2^(k+n+m) - 27)
(I may have mixed m,n,k). It's the same in this case. Q1 must be less than 1 for a cycle to happen which it never is so no 3-cycles are possible !!!
I haven't managed to do solve this for an n-cycle but there's a certain structure in the Q1 functions above so I don't think it would be impossible. If that succeeds (and 1 is resolved) it should be proven that the algoritm terminates (without cycles).
That's it, let's see how long it holds -:). I have some code I can post too.
This code,
long x = 99;
while (x != 1) {
x = findMember(x);
printReductionSet(x);
}
produces this output,
RS_149 = {99, 397, 1589, 6357, 25429, 101717}
RS_7 = {9, 37, 149, 597, 2389, 9557, 38229, 152917}
RS_11 = {7, 29, 117, 469, 1877, 7509, 30037, 120149}
RS_17 = {11, 45, 181, 725, 2901, 11605, 46421, 185685}
RS_13 = {17, 69, 277, 1109, 4437, 17749, 70997, 283989}
RS_5 = {3, 13, 53, 213, 853, 3413, 13653, 54613, 218453}
RS_1 = {1, 5, 21, 85, 341, 1365, 5461, 21845, 87381}
You locate 99 in RS_149, then 149 in RS_7, the 7 RS_11 etcetera down to 5 in RS_1.
--
// Print the reduction set with a certain number
void printReductionSet(long num) {
long max = 1000000; //(long)Integer.MAX_VALUE;
long p = 2;
long n = p*num - 1;
System.out.print("RS_" + num + " = {");
long o = -1;
while (n < max) {
if (n%3 == 0) {
if (o > -1)
System.out.print(o + ", ");
o = n/3;
}
p = p*2;
n = p*num - 1;
}
if (o > -1)
System.out.print(o);
System.out.println("}");
}
// Check if a certain number is a member of a specific reduction set
boolean isMember(long num, long member) {
long max = 1000000; //(long)Integer.MAX_VALUE;
long p = 2;
long n = p*num - 1;
while (n < max) {
if (n%3 == 0) {
if (member == n/3)
return true;
}
p = p*2;
n = p*num - 1;
}
return false;
}
// Find a certain number among all reduction sets
long findMember(long member) {
long num = 1;
while (!isMember(num,member)) {
num = num + 2;
}
return(num);
}
> I consider one full
> iteration of the while loop. If X is odd to start with
> it's going to be odd again after one iteration.
This wasn't completely true. I consider odd X numbers only that is each time the algoritm enters #2. It can take many iterations (basically as long as X is even).
int n = start;
while(n >=start){
As long as you are calling the code for an incrementing sequence of
integers (for(int start=0;start<bla;start++) then you can terminate
the loop early if n is less then start as all values up to start
will not loop :P
matfud>
> here we go, this works ... :
int t;
int n = ...;
while(n > 1){
t = n & 1;
n = n >> (t ^ 1);
n = (t * ((n << 1) + 1)) + n;
}
By the way, my previous post was in reply to this.
> > I consider one full
> > iteration of the while loop. If X is odd to start
> with
> > it's going to be odd again after one iteration.
>
> This wasn't completely true. I consider odd X numbers
> only that is each time the algoritm enters #2. It can
> take many iterations (basically as long as X is
> even).
not completely?
>> odd x odd == odd
>> odd + 1 (or any odd) == even
one full iteration of the loop only includes one of either the if or the else equation. yes?
> one full iteration of the loop only includes one of
> either the if or the else equation. yes?
An even number divided by 2 can be either odd or even. So if a number is even, it won't neccesarily be odd on the next iteration. That's pretty obvious so I'm not sure why it's being pointed out in the first place.
Does that answer the question?
> As long as you are calling the code for an
> incrementing sequence of
> integers (for(int start=0;start<bla;start++) then you
> can terminate
> the loop early if n is less then start as all values
> up to start
> will not loop :P
As a corollary, one can discard all even start values, as they are immediately reduced to a value less than the start value.
> produces this output,but thats wrong ... isn't it ?are you saying for 99, you get the result as:149, 7, 11, 13, 5, 1 ... ?
> > one full iteration of the loop only includes one of
> > either the if or the else equation. yes?
>
> An even number divided by 2 can be either odd or even.
> So if a number is even, it won't neccesarily be odd
> on the next iteration. That's pretty obvious so I'm
> not sure why it's being pointed out in the first
> place.
>
> Does that answer the question?
Um, no.... I realize an even number divided by 2 could be odd or even....
The question was in regard to some vagueness (perceived on my part at least) in a previous statement about odd numbers being odd in the next iteration, and just clarifying that an iteration will only do the if or the else, but not both... I think that's a given in the code, though.
> The question was in regard to some vagueness> (perceived on my part at least) in a previous> statement about odd numbers being odd in the next> iteration,No such statement is made. I will give you that it's very vaguely and confusingly stated.
> > produces this output,
>
> but thats wrong ... isn't it ?
>
> are you saying for 99, you get the result as:
> 149, 7, 11, 13, 5, 1 ... ?
This is the sub-sequence of odd numbers.
I think, UlrikaJ made it not clear enough, that she is only looking at these sub-sequences.
The following algorithm has exactly the same termination characteristics as the original one:
int n = ...
while ((n%2)==0) n = n / 2;
while (n > 1) {
System.out.println(n);
// n is odd at this point
n = 3 * n + 1;
while ((n%2)==0) n = n / 2;
}
> This is the sub-sequence of odd numbers.
> I think, UlrikaJ made it not clear enough, that she is
> only looking at these sub-sequences.
The odd subequences are all that you need to really desribe what happens. The even values just get reduced and are not interesting.
Just adding to polytropos comment
> As long as you are calling the code for an
> incrementing sequence of
> integers (for(int start=0;start<bla;start++) then you
> can terminate
> the loop early if n is less then start as all values
> up to start
> will not loop :P
yes, that will be much faster :)
> btw, speed isn't an issue?
I was really just trying to express it without the "if" statements.
> > here we go, this works ... :
> > int t;
> > int n = ...;
> > while(n > 1){
> > t = n & 1;
> > n = n >> (t ^ 1);
> > n = (t * ((n << 1) + 1)) + n;
> > }
>
> i don't understand!
>
> [...] On the other hand if the
> above code is correct then its not far off a
> recurrence relation (?)
What do you mean ... ?
1000,000,000 and no loopsmatfud
> 1000,000,000 and no loopsI don't want to spoil your effort, but there will be no loops up to at least 2^56 http://personal.computrain.nl/eric/wondrous/ http://personal.computrain.nl/eric/wondrous/cycles.html
no effort. Its just a computer :)
The loop will to a right-shift on x to clear out the zero bits on the right.
If x is a power of 2, then the loop will terminate.
X will become a power of 2 when 3x+1 is a power of 2. That is, when 3x is a binary "111...111 etc".
So the loop will terminate if
x is a power of 2
x is of the form "1010...101" ect
X will become of the form "1010101 etc" if 3x+1 is of the form "1010101". That is, when 3x is of the form "101010....100".
By iterating (x-1)/3, we come up with a series of binary representations which will reduce down. Can *any* number be expressed as one of these forms?
See the binary numbers below. Is there some pattern in the bits for each "requires n divisions"? Is there a pattern to the patterns for all ns? Can any number be expressed as fitting into the pattern for some n?
Requires 0 divisions by 3
1
10
100
1000
10000
100000
1000000
Requires 1 divisions by 3
101
1010
10100
10101
101000
101010
1010000
1010100
1010101
Requires 2 divisions by 3
11
110
1100
1101
11000
11010
110000
110100
110101
1100000
Requires 3 divisions by 3
10001
100010
100011
1000100
1000101
1000110
1001011
Requires 4 divisions by 3
1011
10110
10111
101100
101101
101110
1011000
1011010
1011100
1011101
Requires 5 divisions by 3
111
1110
1111
11100
11101
11110
111000
111010
111100
111101
Requires 6 divisions by 3
1001
10010
10011
100100
100101
100110
1001000
1001010
1001100
1001101
1010001
Requires 7 divisions by 3
11001
110001
110010
110011
1100010
1100011
Requires 8 divisions by 3
100001
1000001
1000010
1000011
Requires 9 divisions by 3
101011
1010110
1010111
1011001
Requires 10 divisions by 3
111001
111011
Requires 11 divisions by 3
100111
1001110
1001111
Requires 33 divisions by 3
1011011
Requires 37 divisions by 3
1000111
Requires 38 divisions by 3
101111
1011110
1011111
Requires 39 divisions by 3
11111
111110
111111
Requires 40 divisions by 3
101001
1010010
1010011
Requires 41 divisions by 3
11011
110110
110111
Requires 42 divisions by 3
1001001
Requires 43 divisions by 3
1100001
> This is the sub-sequence of odd numbers.
> I think, UlrikaJ made it not clear enough, that she is
> only looking at these sub-sequences.
> The following algorithm has exactly the same
> termination characteristics as the original one:
> int n = ...
> while ((n%2)==0) n = n / 2;
> while (n > 1) {
>System.out.println(n);
>// n is odd at this point
>n = 3 * n + 1;
>while ((n%2)==0) n = n / 2;
> }
Yes exactly, this is what I mean. I wasn't clear about this in post 55 where I tried to explain the idea behind the 'proof'. I only consider the odd number sequence. And in the above version of the algoritm it becomes clear. Each time the algoritm returns to n = 3*n +1, n is an odd number.
In my first 'proof' (of probabilistic termination) I tried to show that the n = n/2 inner loop is executed two times on average for each iteration of the outer loop. The idea behind it is that n will have 2 zero rightmost bits on average (n is evenly divisible with 4) when the n = n/2 loop is entered. This tips the balance in favour of the decreasing part of the algoritm. If the 3 rightmost bit's are taken into account 1.75 (7/4) inner loops will occur (because the possible bit patterns are 000, 010, 100 and 110). If 4 bits are considered it becomes 1.875 (15/8). I feel this can be generalize to
(2^m - 1) / 2^(m-1) = 2 - 1/2^m
where m is the number of rightmost bits you consider. You see that the larger m becomes the closer to two iterations the n = n/2 loop gets.
> By iterating (x-1)/3, we come up with a series of
> binary representations which will reduce down. Can
> *any* number be expressed as one of these forms?
What you address is the first of the three parts of a full proof (my post 56),
#1. All odd numbers are present in the reduction sets.
#2. Each number is only present in one reduction set.
#3. There are no cycles. You can never come back to a reduction set you've visited.
What must be shown in #1is that (O*2^n - 1)/3 maps to all odd numbers (O is odd and n > 0). I got stuck and left it because I thought this was fairly standard, but maybe it isn't. I'll give it another try.
Anyway #2 is proven, and #3 is proven for 2- and 3-cycles. What remains is a generalization to n-cycles. I don't think it's that far away.
I think I can prove #1.
The numbers in the reduction sets are generated from all odd numbers . The question is will all odd numbers be present in the reduction sets too? The reduction set numbers are generated using the formula (O*2^n - 1)/3. Here O is any odd number and n is any number > 0. Will the numbers generated with (O*2^n - 1)/3 also represent all odd numbers?
To prove that this is in fact the case I start with this,
O1 = (O2*2^n - 1)/3
Again O2 is an odd number and n is any number > 0. Is it possible by choosing O2 and n to always come up with any odd number O1. Manipulations give,
3*O1+ 1 = O2*2^n
=>
O1 + 1 = O2*2^n - 2*O1
=>
O1 + 1 = (O2*(2^(n-1) - O1)*2
Notice that boths sides are even numbers (adding a 1 to an odd number, multiplying any number with 2). The above can be reduced to this without loss of generality,
E = O2*2^m - O1
The left side E is now any even number, m is any number >= 0 (the equality is important) and O1 and O2 are still odd. Can the right side be used to express the even number on the left side? To show that I choose m=0, O2 = 2*E +1 and O1 = E + 1. If those values are entered you get,
E = 2*E+1 - (E + 1) = E
So if this holds #1 has been proven. Pick any odd number O1, the formula (O2*2^n - 1)/3 also will produce it !!!
> O1 + 1 = (O2*(2^(n-1) - O1)*2
>
> Notice that boths sides are even numbers (adding a 1
> to an odd number, multiplying any number with 2). The
> above can be reduced to this without loss of
> generality,
>
> E = O2*2^m - O1
>
> The left side E is now any even number,
This is not true. O1+1 = (O2*2^(n-1)-O1)*2 [substituting m=n-1]
O1+1 = (O2*2^m-O1)*2 [dividing left and right by 2]
(O1+1)/2 = O2*2^m-O1
O1+1 is definitely an even number, but (O1+1)/2 needn't be.
kind regards,
Jos
> O1+1 is definitely an even number, but (O1+1)/2
> needn't be.
Okay thank you (I seldom do formal proofs -:) Back to the drawing board. This is where it broke down,
O1 + 1 = (O2*2^m - O1)*2
=>
(O1 + 1)/2 = O2*2^m - O1
Here we can see that if Q1 is the infinite series of odd positive natural numbers (1, 3, 5, 7, 9 .....) , then (O1 + 1)/2 will be the infinite series of all natural numbers (1, 2, 3, 4 ......). Lets call any of these numbers N,
N = O2*2^m - O1
Now, if N is even choose m=0, O2 = 2*N +1 and O1 = N + 1. Entered they give,
N = 2*N+1 - (N + 1) = N
And if N is odd choose m=1, O2 = O1 = N,
N = 2*N - N = N
This should do it.
> (O1 + 1)/2 = O2*2^m - O1
> N = O2*2^m - O1
>
> Now, if N is even choose m=0, O2 = 2*N +1 and O1 = N
> + 1. Entered they give,
I'm sorry, that's not correct either -- if N is even and N = (O1+1)/2, then O1= 2*N-1, i.e.
you can't just 'choose' a value for O1 anymore ...
> N = 2*N+1 - (N + 1) = N
>
> And if N is odd choose m=1, O2 = O1 = N,
>
> N = 2*N - N = N
Same reasoning applies here ...
kind regards,
Jos
> I'm sorry, that's not correct either --
Well, maybe the #1 proposition is false -:( I'll have to try again. What do you think about the proof of #2? Does it hold,
2. Each number can only be present in one reduction set.
We have any two different reduction sets RS_O1 and RS_O2 (different means that O1 != O2),
RS_O1 = (O1*2^n - 1)/3
RS_O2 = (O2*2^k - 1)/3
For one number to be present in both, this equality should hold,
(O1*2^n - 1)/3 = (O2*2^k - 1)/3
=>
O1*2^n = O2*2^k
=>
O1*2^(n-k) = O2
If n-k is 0 then O1 = O2 which is false. If n-k is >= 1 then O1*2^(n-k) is even while O2 is odd which is a contradiction. So the equality doesn't hold and the same number can't be in two different reduction sets !!!
> I'm sorry, that's not correct either -- if N is even
> and N = (O1+1)/2, then O1= 2*N-1, i.e.
> you can't just 'choose' a value for O1 anymore ...
The last desperate attempt for today. Say that O1 is locked to 2*N - 1 then I can enter it in to the equality and solve for O2,
N = O2*2^m - (2*N - 1)
=>
O2 = (3*N - 1)/2^m
3*N-1 is always even so I must choose m to the number of rightmost zeros in 3*N-1. That will make Q2 odd.
This means the equality holds for Q1 = 2*N - 1 and Q2 =(3*N - 1)/2^m with m choosen to the number of rightmost zeroes in (3*N - 1). And #1 is proven?
Hi,
Although your #2 proposition holds, there's a flaw in your notation, i.e. you're using O_i both for a set index
as well as meaning 'any odd number'. Here's a simple proof showing that #2 holds --
Let n belong to a reduction set Ri where i denotes an odd number. If n belongs to more than one set
Ri, the following should hold i= (n*3+1)/2^x and j= (n*3+1)/2^y for any x and y. Consequently,
n= (i*2^x-1) /3 = (j*2^y-1)/3 --> i*2^x = j*2^y for some odd values i and j (not equal) and any non-negative
values of x and y. No odd value has an even prime factor so the latter is trivally false, therefore the
original assumption (n belonging to more than one Ri) is false.
But this doesn't bring you much -- odd numbers may 'visit' sets Ri for increasing values of i; there's still
no proof that each odd number 'lands' in R1 in a finite number of steps. Even more -- does the union
of all sets Ri represent the set of all odd numbers? Your attempt causes just a reformulation of the
original problem.
I struggled with this mean little develish problem before and I attempted to reveal some 'deeper' truths
(mind the quotes) by representing numbers n is base 6. The following state diagram reveals some
statistical properties a bit -- 012345
0 x..x..
1 ....x.
2 .x..x.
3 ....x.
4 ..x..x
5 ....x.
This little diagram reads as follows -- if your current number n = i mod 6, look in row i, and where the
entry is crossed, your next number will equal column j mod 6. If you draw this diagram as a state machine
(little circles and arrows) you'll see that all perfect powers of two must lie on the cycle 1 --> 4 --> 2.
There doesn't exist a cycle (other than the trivial 4 <-->5 and the trivial 0 <-->0) But it's still no proof :-)
kind regards,
Jos
ps. I hope I've got that matrix a bit right, because editing such beasts using a proportional font is a mess.
> > I'm sorry, that's not correct either -- if N is
> even
> > and N = (O1+1)/2, then O1= 2*N-1, i.e.
> > you can't just 'choose' a value for O1 anymore ...
>
> The last desperate attempt for today. Say that O1 is
> locked to 2*N - 1 then I can enter it in to the
> equality and solve for O2,
>
> N = O2*2^m - (2*N - 1)
>
> =>
>
> O2 = (3*N - 1)/2^m
>
> 3*N-1 is always even so I must choose m to the number
> of rightmost zeros in 3*N-1. That will make Q2 odd.
>
> This means the equality holds for Q1 = 2*N - 1 and Q2
> =(3*N - 1)/2^m with m choosen to the number of
> rightmost zeroes in (3*N - 1). And #1 is proven?
No, I'm sorry, you're trying to solve something for N even, if N happens to be odd, O1 is 'locked' to
something else (see your previous posts). This is not the way to prove something; no need to get
desparate, let's call it a day :-)
enjoy your weekend,
Jos
Question...
Some have already run this loop thru a few million iterations from 2 up and not found an instance of where the loop does not break. Now, I understand that running this test is impossible, the numbers can grow infinitely, and as long as one runs the program, it'll never be able to truly prove that there isn't some higher number at which the loop gets stuck...
But the question I have is: is there any statistics on showing where it's been proven (or any particular formulas (or whatever the correct term would be)) that extremely large values behave differently when applied to certain formulas (like this loop) then smaller ones? I suppose this is a pointless question, so feel free to say so, but I was just curious if there are situations like I that.
Looked at this for a while. Found some interesting patterns with this code.public class Test {
public static void main(String args[]) {
for (long i=1000; i<1100; i++) {
long x=i;
System.out.print(""+i+": ");
while (x > 1) {
System.out.print((char)('a'+(x%24)));
if (x % 2 == 0) x = x / 2;
else x = 3 * x + 1;
}
System.out.println();
}
}
}
Must... sleep...
> Although your #2 proposition holds, there's a flaw in
> your notation, i.e. you're using O_i both for a set
> index
> as well as meaning 'any odd number'. Here's a simple
> proof showing that #2 holds --
Thanks for your help. I'm not trained in this so my attempts to formal proofs are just naive sketches really. But the flaws can always be worked out. What's important right now to me is that the basic propositions holds. Yoy've given a proof of #2. Do you say that #1 also holds now after my last attempt? This would mean that all odd numbers are present in the reduction sets, and that any odd number belongs to just one reduction set.
> But this doesn't bring you much -- odd numbers may
> 'visit' sets Ri for increasing values of i; there's still
> no proof that each odd number 'lands' in R1 in a
> finite number of steps. Even more -- does the union
> of all sets Ri represent the set of all odd numbers?
> Your attempt causes just a reformulation of the
> original problem.
A reformulation of the original problem is what I want to accomplish. The reduction set formulation maybe can bring the problem into new light. The strategy is to corner it little by little. This is the third proposition,
#3. There are no cycles. You can never come back to a reduction set you've visited.
I thought I'd managed to solve this for 2- and 3-cycles but I was wrong unfortunately. What I can prove is that there are no 0-cycles, meaning no odd number is part of its own reduction set. In my somewhat flawed notation this is the same as,
O = (O*2^n -1)/3
Manipulation gives,
3*O - O*2^n = -1
=>
O = 1/(2^n - 3)
The only positive odd natural number the above can produce is O=1 when n=2. This shows that no 0-cycles are possible except for 1 which is part of reduction set 1. But this doesn't matter because that's where the algoritm terminates.
> But the question I have is: is there any statistics
> on showing where it's been proven (or any particular
> formulas (or whatever the correct term would be)) that
> extremely large values behave differently when applied
> to certain formulas (like this loop) then smaller
> ones? I suppose this is a pointless question, so feel
> free to say so, but I was just curious if there are
> situations like I that.
Nothing (almost) is meaningless -:) There's are some links in this thread, reply 73, and 18 (a Goggle search for the Collatz problem)
I have a feeling that large numbers should 'fall down' faster than small numbers. This is because for large numbers (lots of bits) the x=x/2 part of the loop is executed close to 2 times on average for each x = 3*x+1. For smaller number this drops to about 1.75.
> I have a feeling that large numbers should 'fall down' faster than small numbers.
> This is because for large numbers (lots of bits) the x=x/2 part of the loop is executed
> close to 2 times on average for each x = 3*x+1. For smaller number this drops to about 1.75.
Won't it be true that for any number to finish then the "x = x / 2" part must be executed
at least 2 times (on average) ... if it isn't then the number will never be reduced.
oh well, its apparently not true ... 27, for example, fails my comment.hmmm.
Here I take a shot at proposition #3 and n-cycles.
#3. There are no cycles. You can never come back to a reduction set you've visited.
An n-cycle can be represented by this,
1. O2 = (O1*2^k1 - 1)/3
2. O3 = (O2*2^k2 - 1)/3
.
N. On = (On-1*2^kn - 1)/3
N+1. O1 = On
The algoritm works this backwards. I finds On in reduction set RS_On-1 (among all numbers produced by (On-1*2^kn - 1)/3). This means the algoritm reduces On to On-1 and start serching for On-1. It finds On-1 in RS_On-2. This procedure is repeated all the way down to O2 which it finds in RS_O1. Unfortunately O1 is the same as On so the whole thing starts all over again. An n-cycle is born.
The above equation system can be solved for O1 if equation 1 is inserted in 2 which is inserted in 3 etcetera. After some messy algebra this comes out,
O1 = A/B
A = 2^(k2+k3+k4 ... +kn) + (3)*2^(k3+k4 ... +kn) + (3^2)*2^(k4 ... +kn) + ...... + (3^(n-2))* 2^kn + 3^(n-1)
B = 2^(k1+k2+k3+k4 ... +kn) - 3^n
An n-cycle can happen if Q1 is an odd integer >= 1. I hoped to prove this wasn't the case but unfortunately I can't. Both A and B are odd so O1 must be odd. For a 2-cycle the expression becomes,
O1 = (2^k2 + 3) / (2^(k1+k2) - 9)
If k1 = 1 and k2 = 3 then O1 becomes (8+3)/(16-9) = 11/7. This is >= 1 but it's still not an integer. The question now is can O1 be an integer? Probably not because this would mean an n-cycle is possible and none has been found so far. One can see that B can become very small and that's when O1 becomes >= 1. But will it be an integer? I shouldn't but I don't know.
Well it's an unsolved hard problem so I'm not that surprised. But still I think the reduction set (re)formulation can be fruitful and I'm going to try this approach some more.
> Won't it be true that for any number to finish then
> the "x = x / 2" part must be executed
> at least 2 times (on average) ... if it isn't
> then the number will never be reduced.
The increasing part of the algoritm multiplies x with 3. To compensate the reducing part must divide with at least 3 on average. One iteration of x = x/2 wont be enougth. Two iterations is equivalent to a division by 4 and that's enougth.
yes, i realised my error shorly after posting ... :)
> 1. O2 = (O1*2^k1 - 1)/3> 2. O3 = (O2*2^k2 - 1)/3> .> N. On = (On-1*2^kn - 1)/3Shouldn't that be:"On = (O(n-1)*2^k(n-1)-1)/3"(not sure if that affects anything else you've written).
> > N. On = (On-1*2^kn - 1)/3
>
> Shouldn't that be:
>
> "On = (O(n-1)*2^k(n-1)-1)/3"
No, n-1 is an index on O, maybe I should have used an underscore to emphasize that. These are the last two equations,
N-1: O_n-1 = (O_n-2 * 2^k_n-1 - 1) / 3
N:O_n = (O_n-1 * 2^k_n - 1) / 3
> No, n-1 is an index on O, maybe I should have used an underscore to emphasize that.
Yes, i realise that, i didn't mean my brackets to imply multiplication, simply grouping, to show
that you missed the "-1" in the "kn" item in your first post. (you've put it back in, in the post
i'm replying to).
I've checked the cycle-function in reply 93 for up to 4-cycles.
Not an integer in sight except for 1. It always shows up when all k's are 2. Quite strange. You get expressions you wouldn't believe would end up a 1, like for a 3-cycle (2^4 + 3*2^2 + 9) / (2^6 - 27).
It really seems that if it can be proven that the cycle-function never becomes an odd integer then it's also proven that there can be no n-cycle among the reduction sets which is proposition #3.
I'm putting this aside now for a while. I stop with this example of how the reduction set algoritm finds it's way from 99 to 1:
*** x = 99
Found 99 in reduction set 149.
RS_149 = {99, 397, 1589, 6357, 25429, 101717}
99 = (149*2^1 - 1)/3
*** x = 149
Found 149 in reduction set 7.
RS_7 = {9, 37, 149, 597, 2389, 9557, 38229, 152917}
149 = (7*2^6 - 1)/3
*** x = 7
Found 7 in reduction set 11.
RS_11 = {7, 29, 117, 469, 1877, 7509, 30037, 120149}
7 = (11*2^1 - 1)/3
*** x = 11
Found 11 in reduction set 17.
RS_17 = {11, 45, 181, 725, 2901, 11605, 46421, 185685}
11 = (17*2^1 - 1)/3
*** x = 17
Found 17 in reduction set 13.
RS_13 = {17, 69, 277, 1109, 4437, 17749, 70997, 283989}
17 = (13*2^2 - 1)/3
*** x = 13
Found 13 in reduction set 5.
RS_5 = {3, 13, 53, 213, 853, 3413, 13653, 54613, 218453}
13 = (5*2^3 - 1)/3
*** x = 5
Found 5 in reduction set 1.
RS_1 = {1, 5, 21, 85, 341, 1365, 5461, 21845, 87381}
5 = (1*2^4 - 1)/3
*** x = 1 (exit)
