Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The 3x+1 Problem [video]

youtube.com

Post reply on HN
Print view View original

21–30 of 102 posts

Re: The 3x+1 Problem [video]

#21

Post by mcphage »

hashmash wrote: post #5

After watching this video, how many of us wrote a program to see if we could just randomly find a case which didn't converge? I wrote one, but of course, the program didn't prove the 3x+1 problem wrong.

There’s a problem that’s simple to state: find positive integers A, B, and C such that:

A/(B+C) + B/(A+C) + C/(A+B) = 4

It seems simple, like you could try a few examples and figure it out. And there is a solution. But for the smallest solution, A, B, and C each have 80 digits. Way too big to brute force.

Re: The 3x+1 Problem [video]

#23

Post by AnotherGoodName »

sillypuddy wrote: post #11

Presumably it's impossible to state what the big-o of a checking algorithm is since it's not proven to halt?

The video stated that on average the number is multiplied by 3/4 on each step.

Solve

initial_value * (3/4)^x = 1 for x

to get the number of steps.

That'll give a logarithm. So yes it's O(logn) on average

Re: The 3x+1 Problem [video]

#25

Post by soheil »

It sometimes amazes me how utterly random problems like this end up being their own fields in mathematics. This ended up being a pretty fascinating problem, but coming up with an arbitrary equation like this and then checking to see if it satisfies yet another arbitrary requirement doesn't seem very difficult to do. Am I completely missing something here?

Re: The 3x+1 Problem [video]

#27

Post by yes_man »

kilroy123 wrote: post #20

I watched this the other day. I was left wondering one big question. Why does this need to be solved? Would that even change anything?

Key is early on in the video with the ”mathematics isn’t ripe enough yet”. Since brute forcing the problem seems unlikely, could be that a solution to this problem takes mathematics a step to a new direction. Many useful things like modern cryptography are ultimately based on mathematical research eons ago that were once ridiculed to be useless and unnecessary by some

Re: The 3x+1 Problem [video]

#28

Post by Jyaif »

hashmash wrote: post #5

After watching this video, how many of us wrote a program to see if we could just randomly find a case which didn't converge? I wrote one, but of course, the program didn't prove the 3x+1 problem wrong.

the video addresses this: you are very unlikely of finding a case that does not converge by chance.

Re: The 3x+1 Problem [video]

#30

Post by romwell »

My biggest take-away from this was FRACTRAN[1], The Bestest Ever™ programming language designed by the (sadly, late) John Conway.

To run a FRACTRAN program, you lookup its catalogue number, and repeatedly evaluate a certain simple function on it (which has the same spirit as the 3x + 1 one in the video).

As in 3x+1, all operations are integer operations.

FRACTRAN is Turing-complete, of course, so you can rewrite any program in FRACTRAN, and the paper provides quite a few examples!

Written as a sales pitch, this is both the most hilarious paper I've read in a long time - and one of the most mind-blowing ones.

It's pretty accessible (as far as math/CS papers go), too!

[1]http://www.cs.cmu.edu/~15455/resources/Conway87.pdf

PS: The real mind-blowing part is thinking about whether 3x+1 is, too, a programming language. We simply don't know, and possibly never will.

Post reply on HN