Unsolved Puzzles

It's quite amazing how some math problems are apparently so simple, and yet nobody managed to solve them.
Here is an example:
Let N be a positive integer.
If N if even, divide by 2; if odd, multiply by 3 and add 1. Prove that you end up with the series 1, 4, 2, 1, 4, 2,....

Originally posted by smaia
It's quite amazing how some math problems are apparently so simple, and yet nobody managed to solve them.
Here is an example:
Let N be a positive integer.
If N if even, divide by 2; if odd, multiply by 3 and add 1. Prove that you end up with the series 1, 4, 2, 1, 4, 2,....

If you take an odd number, say 7, then *3=21+ 1 = 22, an even #, but /2 and you have 11* 3=33+1=34/2=17 times 3 etc. Any odd # times 3 plus 1 will = an even #. But dividing by 2 does not always lead to another even #, that only works with POWERS of 2. So a number like 100 as a starting point would go, 50, 25, oops, its an odd # so *3=75+1 =76,another even #, /2=38/2=19, oops, another odd # *3 = 57 +1 = 58, that could bounce around forever!
So you would have to prove it integer by integer and the sequence could lead to infinities, therefore unprovable.
Here is a link to a discussion of this:http:

http://www.physicsforums.com/archive/index.php/t-160998.html

No, you do not necessarily have to prove it for every integer! Maybe it is possible to prove it for different sets of numbers, which the union of is N. E.g. every power of 2 definitely ends in 1.

Why hasn't it been done? Well, that is not because it can't be done, it is because no one is smart enough!

Originally posted by Dejection
No, you do not necessarily have to prove it for every integer! Maybe it is possible to prove it for different sets of numbers, which the union of is N. E.g. every power of 2 definitely ends in 1.

Why hasn't it been done? Well, that is not because it can't be done, it is because no one is smart enough!

Agree. an IQ issue.
But think about this - There are problems that remained unsolved for years or centuries because the math required to solve them did not exist yet. Example - for centuries, mathmaticians struggled with the fact that they could find a general formula for the roots of equations degree 5 or higher. Galois created an entire new branch in math - group theory, and it was with this new tool that the puzzle was finally resolved.
Do you believe the 3N+1 conjecture may fall in the same category?

Couldn't you map odd number to odd number on this, starting with 3 and moving out?

For positive odd integer N, f(N) = (3N+1) / k (where k is the highest power of 2 that 3N+1 is divisible by; essentially I'm stripping all the 2's out)

F(N) -> 3N+1 -> 3N+1 with all 2's factored out
F(1) -> 4 -> 1
F(3) -> 10 -> 5
F(5) -> 16 -> 1
F(7) -> 22 -> 11
F(9) -> 28 -> 7
F(11) -> 34 -> 17
F(13) -> 40 -> 5
F(15) -> 46 -> 23
F(17) -> 52 -> 13

If you analyze these mappings, there might be some patterns which emerge to prove (or disprove) the original hypothesis for all values of N. It does look as if you'll have to analyze it from a perspective of grouping odd numbers together by how many 2's get removed in F(N), particularly those numbers which have a base 4 modulo of 3 (the only ones for which F(N) > N...)

Simplicity, Watson!

N = 2

N is now even. Divide by 2.

N = 1

N is now odd. Multiply by 3 and add 1.

N = 4

N is now even. Divide by 2.

N = 2

Repeat. 🙂

Originally posted by geepamoogle
Couldn't you map odd number to odd number on this, starting with 3 and moving out?

For positive odd integer N, f(N) = (3N+1) / k (where k is the highest power of 2 that 3N+1 is divisible by; essentially I'm stripping all the 2's out)

F(N) -> 3N+1 -> 3N+1 with all 2's factored out
F(1) -> 4 -> 1
F(3) -> 10 -> 5
F(5) -> 16 -> 1
F(7) -> 22 those numbers which have a base 4 modulo of 3 (the only ones for which F(N) > N...)

Using this function F(N):
For the first 1000 odd numbers, the average difference N-F(N) = -.7871
This means that for the smallest 1000 odd numbers, the result of that calculation is on average larger than the initial value.

For the next 1000 odd numbers, however, the average difference is 0.5762, which means that the average result is SMALLER than the initial value.

For the first 1000 integers including the even numbers, the average difference is 166.86

For the integers from 10000-10099, the average difference is 3501.2


Assuming these trends hold, this would indicate that atleast MOST of the positive integers would approach the 1,4,2 pattern

The remaining portion of the proof is proving there are no other loops.

MOST integers approach 1, 4, 2. Then suppose that it was proved that there are no loops. Why can't a number just keep going up and up?

Originally posted by Dejection
MOST integers approach 1, 4, 2. Then suppose that it was proved that there are no loops. Why can't a number just keep going up and up?

If you could prove that every number n eventually reached a number

That's exactly the same thing as proving that all numbers get to 1, which was the original problem anyway.

Originally posted by Swlabr
If you could prove that every number n eventually reached a number

Hmm - I thought there was more to that post when I posted it...

"If you could prove that every number n eventually reached a number less than itself you would have an inductive argument." or something.

Ah that's interesting. A proof could start as follows:
Suppose that there was a number that didn't reach 1. Now look at the sequence generated by this number. There must be a lowest number, say x. {Proof that one can find a lower number in the sequence}. This contradicts the minimality of x, contradiction. Every number must reach 1.

{Proof that one can find a lower number in the sequence} could be something that includes {Proof that each number leads to a lower number eventually}

Or something like that. I was more thinking about expressing each number in binary, as repeated division by 2 in binary is just taking all the 0's off the end. Multiplication by 3 is like multiplication by 11 in decimal. A pattern in the sum of digits in binary maybe, or something?

Originally posted by Swlabr
Hmm - I thought there was more to that post when I posted it...

"If you could prove that every number n eventually reached a number less than itself you would have an inductive argument." or something.

Also, there was more to the post than just that. I think i said something about they must then be of the form 2m+1, but then I think it turns out that m must be a product of a bunch (possibly infinitly many) of such numbers, and so we have a contradiction. However, I think that was just me musing but I can't quite remember - it was c few days ago now...

Originally posted by Dejection
Ah that's interesting. A proof could start as follows:
Suppose that there was a number that didn't reach 1. Now look at the sequence generated by this number. There must be a lowest number, say x. {Proof that one can find a lower number in the sequence}. This contradicts the minimality of x, contradiction. Every number must reach 1.

The tricky part of that is showing that eventually all numbers greater than 1 will eventually reach a lower number.

You give me an arbitrary number of times an odd number leads to a higher odd number in 2 iterations consecutively, and I can find you one which will do it that many times in a row, which could lead to a small percentage of cases where the number gets much, much bigger before it gets much smaller.

03 -> 10 -> 05
07 -> 22 -> 11 -> 34 -> 17
15 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53
etc, etc, etc

It would seem these numbers take the form of k*(2^m) - 1, for m-1 consecutive pairs iterations which ends up greater and greater in value.

I am convinced, however, that once that cycle ends, that the numbers tend to drop rather quickly afterwards.

In order to disprove the thesis, you would need to find an example where a certain number loops into itself and would therefore repeat in a manner similar to 1, 4, 2, 1, 4, 2...

No, a loop is not required to disprove your conjecture. After a number goes up to some sort of peak, it could well turn back down quickly. But what's to say that it won't bounce back up, then down, then up, however going up overall?