A Can this proposition be proved in the Collatz conjecture?

  • Thread starter intervoxel
  • Start date
190
1
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

Science Advisor
7,669
383
Looks strange: Collatz conjecture has sequence ending as 1.
 
337
38
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:

Vanadium 50

Staff Emeritus
Science Advisor
Education Advisor
23,098
5,385
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
Insights Author
2018 Award
11,425
7,849
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"
 
190
1
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
regression.jpg

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

TeethWhitener

Science Advisor
Gold Member
1,396
769
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.
 

Want to reply to this thread?

"Can this proposition be proved in the Collatz conjecture?" You must log in or register to reply here.

Related Threads for: Can this proposition be proved in the Collatz conjecture?

Replies
3
Views
991
Replies
1
Views
1K
Replies
5
Views
2K
  • Posted
Replies
6
Views
1K
  • Posted
Replies
1
Views
2K
  • Posted
Replies
1
Views
1K
  • Posted
Replies
10
Views
2K
Replies
26
Views
1K

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

Hot Threads

Top