Hacker News Reader

Comment by kretaceous | Hacker News Reader

Take a positive integer. If it's odd, multiply it by 3 and add 1. If it's even, divide it by 2.

Example:

7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1-4-2-1-4-2-1...

Any positive integer you take, you end up in a 1-4-2-1 loop.

It's not proved yet but there's no number found yet that satisfies otherwise. That's the Collatz Conjecture or the 3n+1 problem.

Probably the easiest conjecture to explain to someone.

Good day/night!

View on HN

Presumably there's a reason why it's hard to prove either true or false, right?

Depends what you mean by a good reason I guess. A lot of very capable mathematicians have put time in to the problem and it's proven to be pretty resistant to a solution. I think problems like this often feel a little incongruous because they are so simple to state but so hard to solve.

It is easy, we can spit it into two parts: Proving that all even numbers end up in that loop and proving that all odd numbers do.

I'll take the even ones. Who works on the odd ones?

I'll take a stab.

An odd number is a number that ends in 1, 3, 5, 7, or 9.

- ends in a 1: times 3 + 1: it now ends in a 4, which is even, and thus reduces to the even case.

- ends in a 3: tomes 3 is 9, + 1: ends in a 0; even again.

- ends in a 5: ×3 ends in a 5 again, +1: ends in a 6; again even!

- ends in 7: x3: now ends in a 1, +1: ends in a 2; even yet again!

- ends in a 9: ×3 then eens in a 7, +1 thus eens in an 8: even again!!

So all that's left is the cases for @someweirdperson ;-) @someweirdperson

I think this is getting at a pretty good point. Half of all numbers (all evens) will scale by .5 to the subsequent number. The other half (odds) will effectively scale by approximately 3/2, as you have shown here. Obviously over a large amount of iterations this should cause the calculations to trend lower and lower.

One difficulty with this approach is that it doesn't help disproving the existence of cycles, it only makes it less likely that the sequence diverges to infinity.

Another approach would be using the "inverse" of the formula and then trying to prove that you can build all natural numbers starting from 1.

This approach, like every other approaches, did not yield any significant result.

The funny thing is that it fits right in the P=NP problem: easy to verify, hard to solve :)

Cool video from Veritasium about this https://www.youtube.com/watch?v=094y1Z2wpJg

Very interesting. whats the use case of this?

Well, no particular use case I can think of. The OP asked for anything that you find interesting so here we are. =)

I'm sure there is a use for it, that pattern may be representative of some other phenomenon in the universe that we haven't correlated it to as of yet.

Well there is this famous paper by Volovich [1] where he argues that space is basically pixelized and p-adic numbers might best describe their geometry. But of course this has no connection with the reality we have access to. p-adic numbers are also used in various areas of number theory (not my expertise). I see them like the lesser known sibling of real numbers.

[1] https://empslocal.ex.ac.uk/~mwatkins/zeta/volovich1.pdf

Impressing ladies at the bar with your 'deep connection'.

If it's proven then we can add a new pointless compiler optimization (some of them are already allowed to assume some things never terminate, even)

What's the most pointless compiler optimization you're aware of?

(Obviously a subjective question in practice, so chances are you might need to add a bit of qualification)

Infinite loops are considered undefined behaviour in C++.

Infinite loops are undefined (actually, undecidable) behaviour in any Turing machine.

https://en.wikipedia.org/wiki/Halting_problem

That's not what undefined behavior means.

llvm skips it entirely.

https://twitter.com/badamczewski01/status/142826257042792857...

It can easily be proven for all valid values of int (of a specific limited size).

Surely it's true for every unsigned 64-bit integer.

Reply on news.ycombinator.com