# Thread: Help me with problem.

1. ## Help me with problem.

Define a function, $f:\mathbb{Z}^+\to \mathbb{Z}^+$
as,
$f(n)=\left\{ \begin{array}{c}n/2 \mbox{ if even}\\ 3n+1 \mbox{ if odd}$
Prove that there for any $n$ there exists an $m\in \mathbb{Z}^+$ such as,
$\underbrace{(f\circ f\circ f\circ .... \circ f)}_m (n)=1$

Tried to prove it, seems extremely complicated.

2. Originally Posted by ThePerfectHacker
Define a function, $f:\mathbb{Z}^+\to \mathbb{Z}^+$
as,
$f(n)=\left\{ \begin{array}{c}n/2 \mbox{ if even}\\ 3n+1 \mbox{ if odd}$
Prove that there for any $n$ there exists an $m\in \mathbb{Z}^+$ such as,
$\underbrace{(f\circ f\circ f\circ .... \circ f)}_m (n)=1$

Tried to prove it, seems extremely complicated.
See page 400 of "Gödel Escher Bach" by Douglas Hofstadter.

A number for which such a $m$ exists is called Wondrous Number.

The conjecture that all numbers are Wondrous is I believe still open.

RonL

3. what does $\mathbb{Z}^+$ mean? are there any books where I can learn about proofs, but are at a high school level? I can write a simple computer program to determine if a number is wondrous or not (at least is sounds simple). I will post the code sometime, when i have a chance to write the program.

4. Originally Posted by c_323_h
what does $\mathbb{Z}^+$ mean?
$\mathbb{Z}$ denotes the set of all integers $\{\dots,-2,\ -1,\ 0,\ 1,\ 2,\ \dots\}$,
(from Zahlen - German for number?).

$\mathbb{Z^+}$ denotes the set of all positive integers $\{1,\ 2,\ \dots\}$, (also $\mathbb{Z_+}$)

Are there any books where I can learn about proofs, but are at a high school level?
I quite like (meaning I like it a lot):

"Mathematics: A Very Short Introduction"
Tim Gowers
ISBN-10: 0-19-285361-9

I can write a simple computer program to determine if a number is wondrous or not (at least is sounds simple). I will post the code sometime, when i have a chance to write the program.
You will have no guarantee that for any particular number that it will
ever terminate.

RonL

5. Originally Posted by CaptainBlack

You will have no guarantee that for any particular number that it will
ever terminate.

RonL
yeah, i intend i using a loop and it could iterate forever (theoretically). but the largest number my programs can go up to is 2 billion, which is disappointing. as soon as it reaches this number it terminates (i code using c++). i may have to write a new class with arrays to hold more digits, but even with this there is no guarantee

6. Originally Posted by c_323_h
yeah, i intend i using a loop and it could iterate forever (theoretically). but the largest number my programs can go up to is 2 billion, which is disappointing. as soon as it reaches this number it terminates (i code using c++). i may have to write a new class with arrays to hold more digits, but even with this there is no guarantee
You should be able to down-load a class for arbitary precission arithmetic
of of the Web. Google should yurn up a number of them.

RonL

7. Originally Posted by ThePerfectHacker
Define a function, $f:\mathbb{Z}^+\to \mathbb{Z}^+$
as,
$f(n)=\left\{ \begin{array}{c}n/2 \mbox{ if even}\\ 3n+1 \mbox{ if odd}$
Prove that there for any $n$ there exists an $m\in \mathbb{Z}^+$ such as,
$\underbrace{(f\circ f\circ f\circ .... \circ f)}_m (n)=1$

Tried to prove it, seems extremely complicated.

It might be interesting to define an $M$-wondrous numberto be
one for which the itteration teminates in exactly $M$-steps.

The you could ask what proportion $P(N,M)$ of numbers less
than of equal to $N$ are $M$-wondrous.

RonL

8. Originally Posted by CaptainBlack
$\mathbb{Z^+}$ denotes the set of all positive integers $\{1,\ 2,\ \dots\}$, (also $\mathbb{Z_+}$)
Just curious how long ago was the very first time you were not satisfied with this definition becuase it was not mathematically strict and sought to find an elegant definition for "natural"?

9. Originally Posted by CaptainBlack
It might be interesting to define an $M$-wondrous numberto be
one for which the itteration teminates in exactly $M$-steps.

The you could ask what proportion $P(N,M)$ of numbers less
than of equal to $N$ are $M$-wondrous.

RonL
Prove their infinitude.

10. Originally Posted by ThePerfectHacker
Prove their infinitude.
Let's assume you are asking for a proof to the infinitude of Wondrous
numbers.

Consider $2^m$, this is obviously $m$-wondrous.
So there is at least one Wondrous number for every $m \in \mathbb{Z}_+$.
Hence there are an infinite number of Wondrous numbers.

RonL

11. Before you spend a lot of time on this famous problem, you should probably look at some of the resources listed in the ODP.

12. Originally Posted by ThePerfectHacker
Define a function, $f:\mathbb{Z}^+\to \mathbb{Z}^+$
as,
$f(n)=\left\{ \begin{array}{c}n/2 \mbox{ if even}\\ 3n+1 \mbox{ if odd}$
Prove that there for any $n$ there exists an $m\in \mathbb{Z}^+$ such as,
$\underbrace{(f\circ f\circ f\circ .... \circ f)}_m (n)=1$

Tried to prove it, seems extremely complicated.
I have got an elegant solution to your problem, it use discontinued fraction (a variety of continued fraction) and takes only eleven pages. I hope i have not made a mistake because apparently your not very qwick to find mistakes on this site even when they are elementary!

13. Originally Posted by SkyWatcher
I have got an elegant solution to your problem, it use discontinued fraction (a variety of continued fraction) and takes only eleven pages. I hope i have not made a mistake because apparently your not very qwick to find mistakes on this site even when they are elementary!
Do you have a demonstration that Feinstein's proof that there can be no
proof of Collatz's, conjecture is wrong? (this is the first link on the page given
in rgep's post - I must say that on a cursory examination it looks wrong)

RonL

14. Originally Posted by SkyWatcher
I have got an elegant solution to your problem, it use discontinued fraction (a variety of continued fraction) and takes only eleven pages. I hope i have not made a mistake because apparently your not very qwick to find mistakes on this site even when they are elementary!
Ha ha ha,
For anybody else, who does not understand the joke it is private. I once answered a lot of questions all of which where solved with continued fractions. SkyWatcher was obsessed with them ever since. Now he made that remark as if to tease me to solve this problem with continued fractions too.

15. Originally Posted by CaptainBlack
Let's assume you are asking for a proof to the infinitude of Wondrous
numbers.

Consider $2^m$, this is obviously $m$-wondrous.
So there is at least one Wondrous number for every $m \in \mathbb{Z}_+$.
Hence there are an infinite number of Wondrous numbers.

RonL
I guess I misunderstood the definition of wondrous number. I assumed it means that that many iterations for that integral number. I see now what you means by wondrous.