Author |
Topic: Devide by 2 or mulltiply with 3 (+1) (Read 1572 times) |
|
EZ_Lonny
Full Member
Real anarchists play chess without the king
Gender: 
Posts: 168
|
 |
Devide by 2 or mulltiply with 3 (+1)
« on: Nov 8th, 2004, 4:23am » |
 Quote  Modify
|
Recently I heard of a number game.
1 Pick any integer.
2 If it's even: devide it by 2; If it's odd : multiply with 3 and add 1
With the outcome take it further (repeat 2)
In the end you'll always get to 1
I've not yet found out if it's true or false.
Can anyone find the proof?
|
|
 IP Logged |
There is much pleasure to be gained from useless knowledge - Bertrand Russel
|
|
|
EZ_Lonny
Full Member
Real anarchists play chess without the king
Gender:
Posts: 168
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #1 on: Nov 8th, 2004, 4:25am » |
Quote Modify
|
Example:
Take 5:
(5 x 3) + 1 = 16
16 / 2 = 8
8 / 2 = 4 etc.
|
|
IP Logged |
There is much pleasure to be gained from useless knowledge - Bertrand Russel
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #2 on: Nov 8th, 2004, 4:52am » |
Quote Modify
|
on Nov 8th, 2004, 4:23am, EZ_Lonny wrote:| Can anyone find the proof? |
|
Good question! 
I am not sure anybody knows the answer. It is still considered a conjecture (known under a number of names).
You may want to check this thread.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #3 on: Nov 8th, 2004, 8:38am » |
Quote Modify
|
on Nov 8th, 2004, 4:23am, EZ_Lonny wrote:Ok, I'll pick -1
-1 is odd, so -1*3+1=-2
-2 is even, so -2/2 = -1
and we're back to where we've started, proving it won't reduce to 1 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender:
Posts: 767
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #4 on: Nov 8th, 2004, 11:42am » |
Quote Modify
|
Zero will always be zero. Negative and positive numbers should reduce to -1 and 1 respectively.
Constraining to the positive integers: given a number n, if it is even it reduces by half. It might become an odd number. If it is odd, it increases, but becomes an even number (odd x odd + odd must be even).
So, we have an even number that can become either odd or even, or an odd number that will become even, approximately 1.5 times what it is now, which will then be divided by two, approximately 0.75 what we started with (it becomes smaller).
Even without a mathematical proof, inspection shows clearly that this sequence must converge on 1. Negative numbers are the same, they just converge on -1.
Actually it becomes 1, then 4, then 2, then 1, then 4...
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #5 on: Nov 8th, 2004, 12:30pm » |
Quote Modify
|
on Nov 8th, 2004, 11:42am, John_Gaughan wrote:| Zero will always be zero. Negative and positive numbers should reduce to -1 and 1 respectively. |
|
-5 [to] -14 [to] -7 [to] -20 [to] -10 [to] -5
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Obob
Guest
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #6 on: Nov 8th, 2004, 12:35pm » |
Quote Modify
 Remove
|
on Nov 8th, 2004, 11:42am, John_Gaughan wrote:
Even without a mathematical proof, inspection shows clearly that this sequence must converge on 1. Negative numbers are the same, they just converge on -1.
|
|
Mathematical proof exists because "inspection" is often times wrong. If you can take your inspection and turn it into mathematical proof, I gurantee you will have job offers to be a professor at many top caliber universities; this problem is really that hard.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #7 on: Nov 8th, 2004, 12:38pm » |
Quote Modify
|
on Nov 8th, 2004, 11:42am, John_Gaughan wrote:So, we have an even number that can become either odd or even, or an odd number that will become even, approximately 1.5 3 times what it is now, which will then be divided by two, approximately 0.75 1.5 what we started with (it becomes smaller). |
|
I conjecture there are sequences with an arbitrarily long increasing prefix
|
| « Last Edit: Nov 8th, 2004, 1:10pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Obob
Guest
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #8 on: Nov 8th, 2004, 12:57pm » |
Quote Modify
Remove
|
In fact, the great Paul Erdos said that "mathematics is not yet ready for such problems." And if Erdos thinks its too hard to be solved, it must be really hard.
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #9 on: Nov 8th, 2004, 1:36pm » |
Quote Modify
|
Ah crap, you are right about the 3x and 1.5x bit. I guess I already divided by 2 in my head 
Anyway, negative numbers would behave the same (just with the sign) except for the adding 1 part. That has a different meaning in terms of absolute value (e.g. abs(x+1) != abs (-x+1)), so we cannot just ignore the sign, which is what I meant in my previous post.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #10 on: Nov 8th, 2004, 2:00pm » |
Quote Modify
|
I put together a short program that tests numbers entered by the user. It is not allowed as a file type so I will just paste the code here:
Code:#include <iostream>
#include <limits>
#include <cstdlib>
using namespace std;
int main (int argc, char **argv)
{
if (argc < 2)
{
cout << "Please supply a numerical argument." << endl;
return EXIT_FAILURE;
}
long long x = atoll (argv[1]);
bool positive = (x > 0);
cout << "Range of input: " << numeric_limits<long long>::min ()
<< " to " << numeric_limits<long long>::max ()
<< "\nInput: " << x << endl;
while (x != 1)
{
if (x % 2) x = 3 * x + 1;
else x /= 2;
cout << x << endl;
if (positive != (x > 0))
{
cout << "Overflow" << endl;
break;
}
}
return EXIT_SUCCESS;
} |
|
I see a few interesting patterns. First, negative numbers sometimes give -1, but usually degenerate into a cycle of numbers, some of which are quite long. For example, the number -92233720368547758 gives a sequence 18 long.
Anyway, I tried a few positive numbers too. I tried some large primes but that does not seem to matter. Usually the numbers increase for a bit, level off, then slowly but surely decrease to 1.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #11 on: Nov 8th, 2004, 2:45pm » |
Quote Modify
|
If you go to the thread Barukh linked to you can find that an incredible number of positive integers have already been checked, far more than your computer will be able to do in several weeks, or years maybe..
As for negative numbers,
f(i)(n) ; where f(n)=3n+1 for odd n and f(n)=n/2 otherwise
is equivalent to
-g(i)(-n) ; where g(n)=3n-1 for odd n and g(n)=n/2 otherwise
So obviously negative numbers behave quite differently.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #12 on: Nov 8th, 2004, 8:54pm » |
Quote Modify
|
on Nov 8th, 2004, 2:45pm, towr wrote:| If you go to the thread Barukh linked to you can find that an incredible number of positive integers have already been checked, far more than your computer will be able to do in several weeks, or years maybe. |
|
Yes, I see that now. But still, it is nice to check a few myself. I like testing the waters even if it proves nothing.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #13 on: Nov 9th, 2004, 12:35am » |
Quote Modify
|
Quote:| If you go to the thread Barukh linked to... |
|
Curiously, this thread (begun yesterday on Nov 8th) has already received more hits than Barukh's thread about the same topic (begun on Nov 3rd), even though this thread links to it. Perhaps it has something to do with Barukh's rather crankish-sounding title, 'The 3n+1 Conjecture is Unprovable?!'
Quote:| If you can take your inspection and turn it into mathematical proof, I gurantee you will have job offers to be a professor at many top caliber universities; |
|
I doubt if an amateur would get any such offers, given the intellectual elitism that often still prevails in academia. Anyway, a non-amateur has quite recently claimed to have derived such a proof, an outline of which can be found here. What's odds would you give that it's OK?
|
| « Last Edit: Nov 9th, 2004, 2:10am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
EZ_Lonny
Full Member
Real anarchists play chess without the king
Gender:
Posts: 168
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #14 on: Nov 9th, 2004, 1:57am » |
Quote Modify
|
I just read this forum back and looked at my first post and saw I forgot to mention positive.
Nice that there's a somewhat similar sequence on negative integers
|
|
IP Logged |
There is much pleasure to be gained from useless knowledge - Bertrand Russel
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #15 on: Nov 9th, 2004, 2:56am » |
Quote Modify
|
on Nov 9th, 2004, 1:57am, EZ_Lonny wrote:| Nice that there's a somewhat similar sequence on negative integers |
|
It's more than 'somewhat similar'
g(n)=3n-1 for odd n and g(n)=n/2 for even
gives identical results safe for the minus sign.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
EZ_Lonny
Full Member
Real anarchists play chess without the king
Gender:
Posts: 168
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #16 on: Nov 9th, 2004, 3:47am » |
Quote Modify
|
I was thinking about a proof:
proof that it's correct for n;
then proof it's true for n+1.
somehow thats seems impossible.
Althought I tried, I could not.
|
|
IP Logged |
There is much pleasure to be gained from useless knowledge - Bertrand Russel
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #17 on: Nov 9th, 2004, 6:09am » |
Quote Modify
|
on Nov 9th, 2004, 3:47am, EZ_Lonny wrote:I was thinking about a proof:
proof that it's correct for n;
then proof it's true for n+1.
somehow thats seems impossible.
Althought I tried, I could not. |
|
Induction will not work on this problem because there are multiple ways to get to most numbers. For example, given a number 100 in the middle of a sequence, both 33 and 200 give that as the next number. Starting with 1 as a base case does not work.
Reversing it, you might be able to use a proof similar to induction by starting with another number. However, generalizing it to all positive integers will prove to be difficult. While you can define the sequence easily enough, it is showing that it converges using a single inductive step that is difficult.
I think if anything the proof will involve advanced algebra ideas like fields or groups. While I grasp the basics of these, I am not a math major and cannot begin to derive a proof using them.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
EZ_Lonny
Full Member
Real anarchists play chess without the king
Gender:
Posts: 168
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #18 on: Nov 9th, 2004, 6:38am » |
Quote Modify
|
With induction you don t necesarily have to proof the statement for n=1. If it's true for n>1. You still need to proof it for n+1.
I know it's true for n [smiley=in.gif](1,100), n[smiley=in.gif] [smiley=bbn.gif]
|
| « Last Edit: Nov 9th, 2004, 6:40am by EZ_Lonny » |
IP Logged |
There is much pleasure to be gained from useless knowledge - Bertrand Russel
|
|
|
EZ_Lonny
Full Member
Real anarchists play chess without the king
Gender:
Posts: 168
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #19 on: Nov 9th, 2004, 6:56am » |
Quote Modify
|
Just a thought:
We only need to prove that any given n reduces to an integer in the group (1,100) and add the integers that are in the created sequence to that group. And then prove that n+1 ends up in that same group, still adding the sequence to the group.
Me too, I am not en expert on groupthinking (math-wise) 
|
|
IP Logged |
There is much pleasure to be gained from useless knowledge - Bertrand Russel
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #20 on: Nov 9th, 2004, 7:08am » |
Quote Modify
|
on Nov 9th, 2004, 6:38am, EZ_Lonny wrote:With induction you don t necesarily have to proof the statement for n=1. If it's true for n>1. You still need to proof it for n+1.
I know it's true for n [smiley=in.gif](1,100), n[smiley=in.gif] [smiley=bbn.gif] |
|
Proof by mathematical induction uses two steps: base case and inductive step. Proving an inductive step does nothing if you do not have a base case.
Wikipedia article on induction
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
This is commonly referred to as the Collatz problem, when Lothar Collatz conjectured in 1937 that all natural numbers would eventually return to 1.
For those who haven't seen it before, it is quite fun working initially with the simplified algorithm: n->n/2 (even), n->n+1 (odd). It is not difficult to see why this particular process must finish at 1. The starting value, below a given upper limit, that produces the longest chain is an interesting question to ask. For example, starting at 65 produces the longest chain with a starting number below 100. This is easily demonstrated by working backwards.
This is thought to be an alternative approach to proving the Collatz problem. That is, consider the process from 1 up and work backwards, forming a tree. The conjecture implies that the tree contains every natural number.
For those unable to write a programme to do the hard work, and are interested, I've attached an Excel spreadsheet that gives, for each starting number from 1 to 1000, the length of the chain (before it reaches 1), and the maximum value it reaches, using the process n->3n+1 (odd).
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
EZ_Lonny
Full Member
Real anarchists play chess without the king
Gender:
Posts: 168
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #22 on: Nov 10th, 2004, 3:30am » |
Quote Modify
|
on Nov 9th, 2004, 9:30am, Sir Col wrote:| For those unable to write a programme to do the hard work, and are interested, I've attached an Excel spreadsheet that gives, for each starting number from 1 to 1000, the length of the chain (before it reaches 1), and the maximum value it reaches, using the process n->3n+1 (odd). |
|
Reading the excel file I noticed something interesting:
9232 seems to be a magical number in many sequences.
Is that coincidence?
|
| « Last Edit: Nov 10th, 2004, 3:30am by EZ_Lonny » |
IP Logged |
There is much pleasure to be gained from useless knowledge - Bertrand Russel
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Devide by 2 or mulltiply with 3 (+1)
« Reply #23 on: Nov 10th, 2004, 11:44am » |
Quote Modify
|
That is a good question, and one to which number theorists have no answer.
From 9323, the sequence continues:
..., 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
Interestingly, there are 16 number below 100 that arrive at 9232, but after this there are 368 below 1000, 4011 below 10000, 38989 below 100000, and 394059 below 1000000. It seems that nearly 40% of starting numbers will follow the 9232 to 1 sequence. Does this continue?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
collatz.xls