# A Can this proposition be proved in the Collatz conjecture?

#### intervoxel

Summary
lemma in collatz conjecture proof.
Can this proposition be proved and become a lemma in the proof of Collatz conjecture?

$$collatz(n) \geq \lfloor \frac{log(n)}{log(2)} \rfloor.$$

#### mathman

Looks strange: Collatz conjecture has sequence ending as 1.

#### SSequence

Looks strange: Collatz conjecture has sequence ending as 1.
I think the symbol "collatz(n)" is supposed to mean:
"the number of steps it takes to reach the value 1, if we are given the starting number n"

So, if we assume that, then the given inequality (or something very close) should be true (in an elementary way) ........ but one of the following must be true for that to hold:
(1) We either assume the conjecture to be true (all numbers starting from any "n" go back to 1).
(2) We declare/mention that our inequality is only supposed to hold for those value of "n" for which the calculation stops (goes back to 1) eventually.

Last edited:

Staff Emeritus
You can't tell if something is a lemma without having a proof.

If this isn't obvious, you don't know if something is true or not until you have a proof, so how could you know whether something is a lemma or not?

#### fresh_42

Mentor
2018 Award
You can't tell if something is a lemma without having a proof.
And the need for guesswork doesn't help either.
I think the symbol "collatz(n)" is supposed to mean:
"the number of steps it takes to reach the value 1, if we are given the starting number n"

#### intervoxel

You can't tell if something is a lemma without having a proof.

If this isn't obvious, you don't know if something is true or not until you have a proof, so how could you know whether something is a lemma or not?
I'm not claiming this is a lemma, my friend. I'm asking whether it can be proven, since my attempts to prove it were of no avail. That's why I launched the challenge.

By the way, the formula was deduced by picking the lowest stop times from 1 to 10000 and checking the peculiar power of two sequence that regression fit against $$a\thinspace log(x)+b$$ led to the shown formula.
1,0
2,1
4,2
8,3
16,4
32,5
64,6
128,7
256,8
512,9
1024,10
2048,11
4096,12
8192,13

Obs.: a and b are interchanged in the site. A small bug.

Staff Emeritus
Summary: lemma in collatz conjecture proof.

Can this proposition be proved and become a lemma
I'm not claiming this is a lemma, my friend. I'm asking whether it can be proven,
What ever.

#### TeethWhitener

Gold Member
Powers of two have the quickest stopping time under the Collatz map (this is straightforward to prove). Assuming $Collatz(n)$ is the time to reach 1 for positive integer $2^x<n<2^{x+1}$, then we have that $Collatz(2^x)=x$, or, to put it another way, $x+1\leq Collatz(n)$. Taking the logarithm of the first inequality and rearranging gives us:
$$\frac{\log n}{\log 2} < x+1\leq Collatz(n)$$
which is the result you gave in the OP.

#### fresh_42

Mentor
2018 Award
I don't think it is true. Given a sample of bigger size, it looks as if there is no such tendency apparent:

"Can this proposition be proved in the Collatz conjecture?"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving