wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Devide by 2 or mulltiply with 3 (+1)
        
(Message started by: EZ_Lonny on Nov 8^th, 2004, 4:23am)

Title: Devide by 2 or mulltiply with 3 (+1)
Post by EZ_Lonny on Nov 8^th, 2004, 4:23am

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?

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by EZ_Lonny on Nov 8^th, 2004, 4:25am

Example:

Take 5:

(5 x 3) + 1 = 16

16 / 2 = 8

8 / 2 = 4 etc.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by Barukh on Nov 8^th, 2004, 4:52am

on 11/08/04 at 04:23:54, EZ_Lonny wrote:

Can anyone find the proof?

Good question! ;D

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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_general;action=display;num=1099485211).

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by towr on Nov 8^th, 2004, 8:38am

on 11/08/04 at 04:23:54, EZ_Lonny wrote:

1 Pick any integer.

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 :P

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by John_Gaughan on Nov 8^th, 2004, 11:42am

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...

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by towr on Nov 8^th, 2004, 12:30pm

on 11/08/04 at 11:42:36, 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

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by Obob on Nov 8^th, 2004, 12:35pm

on 11/08/04 at 11:42:36, 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.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by towr on Nov 8^th, 2004, 12:38pm

on 11/08/04 at 11:42:36, 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

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by Obob on Nov 8^th, 2004, 12:57pm

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.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by John_Gaughan on Nov 8^th, 2004, 1:36pm

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.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by John_Gaughan on Nov 8^th, 2004, 2:00pm

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.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by towr on Nov 8^th, 2004, 2:45pm

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⁽ⁱ⁾(n) ; where f(n)=3n+1 for odd n and f(n)=n/2 otherwise
is equivalent to
-g⁽ⁱ⁾(-n) ; where g(n)=3n-1 for odd n and g(n)=n/2 otherwise
So obviously negative numbers behave quite differently.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by John_Gaughan on Nov 8^th, 2004, 8:54pm

on 11/08/04 at 14:45:55, towr wrote:

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.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by THUDandBLUNDER on Nov 9^th, 2004, 12:35am

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 (http://www.math.buffalo.edu/mad/special/3X+1.html). What's odds would you give that it's OK?

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by EZ_Lonny on Nov 9^th, 2004, 1:57am

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

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by towr on Nov 9^th, 2004, 2:56am

on 11/09/04 at 01:57:59, 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.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by EZ_Lonny on Nov 9^th, 2004, 3:47am

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.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by John_Gaughan on Nov 9^th, 2004, 6:09am

on 11/09/04 at 03:47:54, 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.

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by EZ_Lonny on Nov 9^th, 2004, 6:38am

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]

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by EZ_Lonny on Nov 9^th, 2004, 6:56am

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) ???

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by John_Gaughan on Nov 9^th, 2004, 7:08am

on 11/09/04 at 06:38:26, EZ_Lonny wrote:

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 (http://en.wikipedia.org/wiki/Mathematical_induction)

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by Sir Col on Nov 9^th, 2004, 9:30am

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).

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by EZ_Lonny on Nov 10^th, 2004, 3:30am

on 11/09/04 at 09:30:25, 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?

Title: Re: Devide by 2 or mulltiply with 3 (+1)
Post by Sir Col on Nov 10^th, 2004, 11:44am

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?