The Collatz conjecture is pretty cool
And number theory is entertaining
Though I won't be famous like George Boole
The conjecture does need explaining.
There once was a student named Rae, Wouldn't let background get in the way. Although never a Boole, Yet nobody's fool, About Collatz she'll have something to say.
Haha I love it! Are you the Mensanator of Mensanator.com? Because if so, I penned that poem within perhaps half an hour of stumbling onto your site for the first time, looking for information on efficient cycle detection. Quite odd!
Yes, I own the domain Mensanator.com. Your poem turned up in a Google search I did on "collatz" which I do once in a while to see if anything new gets posted to the web. Usually, the "new" things I find are too old to reply to. Odd indeed.
Did you see my comic book "Quest for the Ultimate Cycle"? Obviously, you can store every number you encounter in a set or dictionary or a binary tree and detect a duplicate fairly easily. I was specifically looking at Brent's cycle detection algorithm, not for it's efficiency but for cases where there's not enough memory to hold a binary tree. I'm up to a loop cycle of 7.9 billion iterations (and that only counts the odd numbers).
Sorry, I didn't mean to mislead you. That's NOT using the traditional 3n+1. It's for the extension 3n+C, where C is a positive odd integer not a power of 3. The extention ALWAYS fails and I'm keen to know why. Anyway, a true counterexample would have a huge loop cycle and the question is: could I identify it if I encountered it? That's why I use 3n+C, it gives me something to practice on. The comic book doesn't make any headway in proving 3n+1, but it answers the question "How can I come up with a 3n+C system that has an arbitrarily large loop cycle?"
Very interesting...I will definitely have to look that that. It fails for every C?
I've put together a program (it isn't exactly finished, thanks to the time-eater that is real schoolwork, but it's essentially functional) that allows the user to choose a range of that value to test, as well as the value of the 3 and the value of the 2 (in the n/2). One can also, of course, choose a range of n to test. I'm going to look for patterns etc, sort of go for the generalizing thing, and hope something comes from it!
No, not every C. As I said, only odd integers not a power of 3 (C=1 is also a power of 3, namely 3^0).
Because if C is even, you immediately fall into parity lock (the successor of an odd number is an odd number) and your sequence runs off to infinity. Even C are trivially false.
Not so trivial is when C is a power of 3. Now, I can no more prove 3n+3 is true any more than I can prove 3n+1, but I CAN prove that 3n+3 has exactly the same loop structures as 3n+1. So, if 3n+1 is true, so is 3n+3, 3n+9, 3n+27, 3n+81, etc.
As for the rest, we start by noting every 3n+C has a Trivial Loop cycle of 4C-2C-C-4C (Collatz basically asserts that the Trivial Loop cycle is the only loop cycle in the positive domain). This means that every node on the Trivial graph is a multiple of C. The seed 1 is never a multiple of C, so the sequence starting at 1 cannot reach the Trivial Loop cycle. Therefore, every 3n+C must have at least two loop cycles. QED
They may have many more than two, but two suffice to demonstrate failure.
I have not experimented with the things you describe in your program (my hands are full just trying to nail down 3n+C). I expect you'll also encounter parity lock or something and I wouldn't be surprised if you have to restrict the choices like I had to do above.
But that's your project. Good luck. Hopefully, you'll find something useful in the patterns.
Well, I meant every valid C. I have already discovered that what I am calling A (that is, the 3 in the traditional conjecture) can't be even if N is odd (which I think it needs to be, to be valid?), because it will never become even.
I'm hoping for something useful as well, certainly!
Yes, you must avoid parity lock when applying the AN+1 rule. Since 1 and N are odd (or you wouldn't be using this rule), that forces A to be odd also. That results in odd*odd+odd which equals even and you get the hailstoning effect you need.
So in AN+C, both A and C must be odd, we can't let either be even. But what if BOTH were even? Hmm, I haven't considered that.
If A and C are both even, and therefore both divisible by two, I believe you get an issue similar to the reason for keeping C from being a multiple of 3 when A is 3. Looking at sequences where C and A share a common factor, the sequences are often quite similar, if not the same; for instance, 6n+6 ends in the same cycle as 3n+3.
It provoked a flurry of activity on the Wikipedia Collatz article, as well as activity on the discussion page (of which I am a regular contributor), some of which seemed applicable to your project.
Someone mentioned a 5n+1 sequence running off to infinity and it occurred to me that the same probabilistic heuristic that shows 3n+1 sequences converge also demonstrates that 5n+1 sequences diverge (due to the even numbers having a Geometric Distribution and thus, there always are a mean of two evens between two odds regardless of what A is in AN+1).
More interesting stuff about 5n+1 (once I get started, it's hard to stop).
In addition to sequences that run off to infinity, there are at least three loop cycles (I didn't do an exhaustive search, just those with at most 10 odd numbers with up to 20 evens).
Interestingly, none are Trivial (X-Y would have to be a unit). Although there is a Trivial loop in the negative domain: -1 -4 -2 -1.
This kind of surprised me (because I hadn't previously thought it through). I've been so used to working with 3n+C that I considered it a law that all 3n+C systems have a Trivial loop.
Which is true, but it's obviously not a universal law that applies to all multipliers. You would get a Trivial loop in 7n+1 because there is a power of 2 that differs from a power of 7 by a positive unit.
It's just that I've been using 3n+C in a project to factor large numbers using Collatz. It's nowhere near being able to factor arbitrary large numbers, but I've got a neat feasibility study that sequentially factors a series of composites (each exactly two factors) all the way up to 800 digits (and that's not the limit, just where I stopped it).
It uses two axioms: - Collatz is true for 3n+1 - the Trivial graph of ALL 3n+C are the same shape
Obviously, I would be hard pressed to exploit 5n+C to factor since positive Trivial loops don't exist. Of course, I can always use 3n+C since the axioms seem to always hold.
I now think your project is a lot more interesting than I did at first.
That is interesting...and I like that you just can't quit thinking about Collatz!
I must admit, I initially thought my project was a bit silly, but I'm starting to see more and more connections to the traditional conjecture, and some cool number theory stuff in general.
I don't know if you're interested, but I updated my comic book "Quest for the Ultimate Cycle" at Mensanator.com.
Seems the author of Seed7 got upset about my previous update where I referred to Seed7 as "worthless" and said "I apologize for ever having mentioned it".
Turns out there were some problems he's fixed and some of my variables needed to be recast as bigIntegers. He said such comments are now unfair since the issues have been addressed.
Unfortunately, his fixes didn't take into account that I'm now using a Mac Airbook and his code doesn't work with my compiler anymore. We're working on fixing that (after all, he's keen on platform independence and 64-bit systems have been around for awhile, so it's in his interest to work with me as he does not have a Mac available for testing). So I took out the snide remarks about Seed7, especially after HE found a bigger Ultimate Cycle!
To be fair, I WOULD have found it if Seed7 had worked properly from the start, but oh well.
Anyway, if for no other reason, check out the xkcd cartoon I added appropriate to the idea of debugging a C program by e-mail.
Oh, and there's actually a bit of new stuff about Collatz. Specifically, a second method to construct a loop of arbitrary length.
19 comments:
There once was a student named Rae,
Wouldn't let background get in the way.
Although never a Boole,
Yet nobody's fool,
About Collatz she'll have something to say.
Haha I love it! Are you the Mensanator of Mensanator.com? Because if so, I penned that poem within perhaps half an hour of stumbling onto your site for the first time, looking for information on efficient cycle detection. Quite odd!
Yes, I own the domain Mensanator.com. Your poem turned up in a Google search I did on "collatz" which I do once in a while to see if anything new gets posted to the web. Usually, the "new" things I find are too old to reply to. Odd indeed.
Did you see my comic book "Quest for the Ultimate Cycle"? Obviously, you can store every number you encounter in a set or dictionary or a binary tree and detect a duplicate fairly easily. I was specifically looking at Brent's cycle detection algorithm, not for it's efficiency but for cases where there's not enough memory to hold a binary tree. I'm up to a loop cycle of 7.9 billion iterations (and that only counts the odd numbers).
I haven't seen that comic book yet, but I'll have to check it out!
7.9 billion odd iterations, for the traditional Collatz conjecture? It's incredible to me that there is no accepted proof of it yet.
Sorry, I didn't mean to mislead you. That's NOT using the traditional 3n+1. It's for the extension 3n+C, where C is a positive odd integer not a power of 3. The extention ALWAYS fails and I'm keen to know why. Anyway, a true counterexample would have a huge loop cycle and the question is: could I identify it if I encountered it? That's why I use 3n+C, it gives me something to practice on. The comic book doesn't make any headway in proving 3n+1, but it answers the question "How can I come up with a 3n+C system that has an arbitrarily large loop cycle?"
Very interesting...I will definitely have to look that that. It fails for every C?
I've put together a program (it isn't exactly finished, thanks to the time-eater that is real schoolwork, but it's essentially functional) that allows the user to choose a range of that value to test, as well as the value of the 3 and the value of the 2 (in the n/2). One can also, of course, choose a range of n to test. I'm going to look for patterns etc, sort of go for the generalizing thing, and hope something comes from it!
No, not every C. As I said, only odd integers not a power of 3 (C=1 is also a power of 3, namely 3^0).
Because if C is even, you immediately fall into parity lock (the successor of an odd number is an odd number) and your sequence runs off to infinity. Even C are trivially false.
Not so trivial is when C is a power of 3. Now, I can no more prove 3n+3 is true any more than I can prove 3n+1, but I CAN prove that 3n+3 has exactly the same loop structures as 3n+1. So, if 3n+1 is true, so is 3n+3, 3n+9, 3n+27, 3n+81, etc.
As for the rest, we start by noting every 3n+C has a Trivial Loop cycle of 4C-2C-C-4C (Collatz basically asserts that the Trivial Loop cycle is the only loop cycle in the positive domain). This means that every node on the Trivial graph is a multiple of C. The seed 1 is never a multiple of C, so the sequence starting at 1 cannot reach the Trivial Loop cycle. Therefore, every 3n+C must have at least two loop cycles. QED
They may have many more than two, but two suffice to demonstrate failure.
I have not experimented with the things you describe in your program (my hands are full just trying to nail down 3n+C). I expect you'll also encounter parity lock or something and I wouldn't be surprised if you have to restrict the choices like I had to do above.
But that's your project. Good luck. Hopefully, you'll find something useful in the patterns.
Well, I meant every valid C. I have already discovered that what I am calling A (that is, the 3 in the traditional conjecture) can't be even if N is odd (which I think it needs to be, to be valid?), because it will never become even.
I'm hoping for something useful as well, certainly!
Yes, you must avoid parity lock when applying the AN+1 rule. Since 1 and N are odd (or you wouldn't be using this rule), that forces A to be odd also. That results in odd*odd+odd which equals even and you get the hailstoning effect you need.
So in AN+C, both A and C must be odd, we can't let either be even. But what if BOTH were even? Hmm, I haven't considered that.
If A and C are both even, and therefore both divisible by two, I believe you get an issue similar to the reason for keeping C from being a multiple of 3 when A is 3. Looking at sequences where C and A share a common factor, the sequences are often quite similar, if not the same; for instance, 6n+6 ends in the same cycle as 3n+3.
Ah, very astute of me for having ignored it. :-)
Yes indeed :)
Did you see this?
http://xkcd,com/710
It provoked a flurry of activity on the Wikipedia Collatz article, as well as activity on the discussion page (of which I am a regular contributor), some of which seemed applicable to your project.
Someone mentioned a 5n+1 sequence running off to infinity and it occurred to me that the same probabilistic heuristic that shows 3n+1 sequences converge also demonstrates that 5n+1 sequences diverge (due to the even numbers having a Geometric Distribution and thus, there always are a mean of two evens between two odds regardless of what A is in AN+1).
Anyway, it was a good cartoon.
I did see that comic! I cracked up. Quite amusing.
That information definitely sounds interesting; could you provide a link to the discussion? Thank you!
You can find it here:
http://en.wikipedia.org/wiki/Talk:Collatz_conjecture
It's towards the bottom.
Excellent, thanks!
More interesting stuff about 5n+1 (once I get started, it's hard
to stop).
In addition to sequences that run off to infinity, there are
at least three loop cycles (I didn't do an exhaustive search,
just those with at most 10 odd numbers with up to 20 evens).
(X-Y) SequenceVector Sequence
7 [1, 4] 1 6 3 16 8 4 2 1
3 [1, 1, 5] 13 66 33 166 83 416 208 104 52 26 13
3 [1, 3, 3] 17 86 43 216 108 54 27 136 68 34 17
Interestingly, none are Trivial (X-Y would have to be a unit).
Although there is a Trivial loop in the negative domain: -1 -4 -2 -1.
This kind of surprised me (because I hadn't previously thought
it through). I've been so used to working with 3n+C that I
considered it a law that all 3n+C systems have a Trivial loop.
Which is true, but it's obviously not a universal law that
applies to all multipliers. You would get a Trivial loop in
7n+1 because there is a power of 2 that differs from a power of 7
by a positive unit.
It's just that I've been using 3n+C in a project to factor large
numbers using Collatz. It's nowhere near being able to factor
arbitrary large numbers, but I've got a neat feasibility study
that sequentially factors a series of composites (each exactly
two factors) all the way up to 800 digits (and that's not the limit,
just where I stopped it).
It uses two axioms:
- Collatz is true for 3n+1
- the Trivial graph of ALL 3n+C are the same shape
Obviously, I would be hard pressed to exploit 5n+C to factor since
positive Trivial loops don't exist. Of course, I can always use
3n+C since the axioms seem to always hold.
I now think your project is a lot more interesting than I did at first.
That is interesting...and I like that you just can't quit thinking about Collatz!
I must admit, I initially thought my project was a bit silly, but I'm starting to see more and more connections to the traditional conjecture, and some cool number theory stuff in general.
I don't know if you're interested, but I updated my comic book "Quest for the Ultimate Cycle" at Mensanator.com.
Seems the author of Seed7 got upset about my previous update where I referred to Seed7 as "worthless" and said "I apologize for ever having mentioned it".
Turns out there were some problems he's fixed and some of my variables needed to be recast as bigIntegers. He said such comments are now unfair since the issues have been addressed.
Unfortunately, his fixes didn't take into account that I'm now using a Mac Airbook and his code doesn't work with my compiler anymore. We're working on fixing that (after all, he's keen on platform independence and 64-bit systems have been around for awhile, so it's in his interest to work with me as he does not have a Mac available for testing). So I took out the snide remarks about Seed7, especially after HE found a bigger Ultimate Cycle!
To be fair, I WOULD have found it if Seed7 had worked properly from the start, but oh well.
Anyway, if for no other reason, check out the xkcd
cartoon I added appropriate to the idea of debugging a C program by e-mail.
Oh, and there's actually a bit of new stuff about Collatz. Specifically, a second method to construct a loop of arbitrary length.
Post a Comment