Testwiki:Reference desk/Archives/Mathematics/2018 August 23

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < August 22 ! width="25%" align="center"|<< Jul | August | Sep >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 23

2 Collatz Conjecture (3x+1) question.

Hello! I was recommended by Jasper Deng to ask my questions here. :) This question is in regards to the Collatz Conjecture or 3x + 1 problem (https://en.wikipedia.org/wiki/Collatz_conjecture). I have done my best to watch all of the videos and read a lot of websites, but my question isn't answered anywhere there. There is something that goes by a few names; Steps or Total Stopping Distance (are they the same thing?) and I was wondering if there existed a simple linear function f(S) that returns any number N that is S Steps from 1? So for example f(111) could return 27, since 27 is 111 steps from 1. Is there a function that can give f(100000) to f(200000) or something?

24.78.157.241 (talk) 03:40, 23 August 2018 (UTC)

f(s) will have to output a set of numbers as there can be more than one number that is s steps away from 1. For example, both 5 and 32 are 6 steps away from 1. f(s) can be defined recursively as follows:

$f(4)=\{8\}$

$f(s)=\{2x|x\in f(s-1)\}\cup \{\frac{x-1}{3}|x\in f(s-1)\wedge x\equiv 4mod6\}s>4$

In effect, this is just running the Collatz rule in reverse. Applying this recursively gives:

$f(5)=\{16\}$

$f(6)=\{5,32\}$

$f(7)=\{10,64\}$

$f(8)=\{3,20,21,128\}$

etc.

and you could eventually find the set f(111). Gandalf61 (talk) 08:14, 23 August 2018 (UTC)

Hmm your algorithm does 2 things than what I am after: It returns a set; more than one result; and it, as you said "runs the algorithm backwards". I was wondering if you had a simple calculation that provided a small (but not smallest) non-trivial number N that is S steps away from 1? IE: No summations, no loops, no recursion, no look-ups, etc.. Does that type of thing exist? Or is the 3x + 1 system too complicated for such a thing? If such an algorithm could be found, do you think it might help out the people trying to prove the conjecture over-all?

24.78.157.241 (talk) 16:46, 23 August 2018 (UTC)

The only easy to implement function that returns a number n steps away from 1 is $f(n)=2^n$, but that returns the largest number for each n. Iffy★Chat -- 18:37, 23 August 2018 (UTC)

FYI, this is Template:OEIS el. –Deacon Vorbis (carbon • videos) 19:17, 23 August 2018 (UTC)

You might like the graph in this xkcd: https://www.xkcd.com/710/ 2607:FCD0:100:8303:5D:0:0:B7D4 (talk) 23:51, 24 August 2018 (UTC)

The short answer is "no", it is too irregular. Bubba73 ^{You talkin' to me?} 00:22, 25 August 2018 (UTC)

Thank you everyone for your feedback and responses! 24.78.157.241 (talk) 17:17, 26 August 2018 (UTC)