Help me with problem.

Printable View

May 9th 2006, 07:06 PM
ThePerfectHacker

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.
May 9th 2006, 09:15 PM
CaptainBlack

Quote:

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
May 10th 2006, 05:22 AM
c_323_h

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.
May 10th 2006, 05:43 AM
CaptainBlack

Quote:

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_+}$ )

Quote:

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

Quote:

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
May 10th 2006, 07:00 AM
c_323_h

Quote:

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
May 10th 2006, 08:16 AM
CaptainBlack

Quote:

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
May 10th 2006, 08:51 AM
CaptainBlack

Quote:

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
May 10th 2006, 02:25 PM
ThePerfectHacker

Quote:

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"?
May 10th 2006, 07:09 PM
ThePerfectHacker

Quote:

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.
May 12th 2006, 09:36 PM
CaptainBlack

Quote:

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
May 12th 2006, 10:49 PM
rgep

Before you spend a lot of time on this famous problem, you should probably look at some of the resources listed in the ODP.
May 13th 2006, 08:27 AM
SkyWatcher

Quote:

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!
May 13th 2006, 08:38 AM
CaptainBlack

Quote:

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
May 14th 2006, 07:06 PM
ThePerfectHacker

Quote:

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, :D
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.
May 14th 2006, 07:08 PM
ThePerfectHacker

Quote:

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.