Mathematics desk
< August 22	<< Jul \| August \| Sep >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an 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[edit]

2 Collatz Conjecture (3x+1) question.[edit]

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)[reply]

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)\land x\equiv 4\mod 6\}\quad 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)[reply]

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)[reply]

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)[reply]

FYI, this is OEIS sequence A033491. –Deacon Vorbis (carbon • videos) 19:17, 23 August 2018 (UTC)[reply]

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)[reply]

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

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