# Calculating Collatz Cousins

Define the function f(n) for a positive integer n as follows:

• n / 2, if n is even
• 3 * n + 1, if n is odd

If you repeatedly apply this function to any n greater than 0, the result always seems to converge to 1 (though nobody's been able to prove that yet). This property is known as the Collatz Conjecture.

Define an integer's stopping time as the number of times you have to pass it through the Collatz function f before it reaches 1. Here are the stopping times of the first 15 integers:

1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17

Let's call any set of numbers with the same stopping time Collatz cousins. For example, 5 and 32 are Collatz cousins, with a stopping time of 5.

Your task: write a program or function that takes a nonnegative integer and generates the set of Collatz cousins whose stopping time is equal to that integer.

## Input

A nonnegative integer S, given via STDIN, ARGV, or function argument.

## Output

A list of all numbers whose stopping time is S, sorted in ascending order. The list may be output by your program, or returned or output by your function. Output format is flexible: space-separated, newline-separated, or any standard list format of your language is fine, as long as the numbers are easily distinguishable from one another.

## Requirements

Your submission must give correct results for any S ≤ 30. It should finish in seconds or minutes, not hours or days.

## Examples

0  -> 1
1  -> 2
5  -> 5, 32
9  -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768

Here is a Gist of the output for S = 30.

This is : shortest program in bytes wins. Good luck!

• What of cycles? I did not see a mention of cycle avoidance. Because for S=5, there are 3 values [4, 5, 32] because you can go "1 - 2 - 4 - 1 - 2- 4"
– JPMC
Commented May 29, 2015 at 2:46
• @JPMC Cycle avoidance is implied by the definition of stopping time. The stopping time of 4 is 2, not 5, because 2 is "the number of times you have to pass it through the Collatz function before it reaches 1." Commented May 29, 2015 at 2:56
• Ah, forgive me. I was thinking that a number could have multiple stopping times, since multiple paths can lead to it. But that was with respect to building up from 1, not working from N. Sorry about that.
– JPMC
Commented May 29, 2015 at 3:13
• @DLosc Pyth, of course. Commented May 29, 2015 at 7:52
• Related, but not golfed: math.stackexchange.com/q/470782/20792 and math.stackexchange.com/q/1243841/20792 Commented May 29, 2015 at 7:54

# Mathematica, 9892 89 bytes

This solution solves S = 30 immediately:

(p={0};l={1};Do[l=Complement[##&@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&/@l,p=p⋃l],{#}];l)&

This is an unnamed function taking S as its only parameter and returning a list of the Collatz cousins.

The algorithm is a simple breadth-first search. The Collatz cousins for a given S are all the integers that can be reached from the Collatz cousins for S-1 via 2*n or odd numbers that can be reached via (n-1)/3. We also need to ensure that we only produce those integers which were reached for the first time after S steps, so we keep track of all previous cousins in p and remove those from the result. Since we're doing that anyway, we can save a few bytes by computing the steps from all previous cousins (not just those from S-1) to save a few bytes (that makes it slightly slower, but not noticeably for the required S).

Here is a slightly more readable version:

(
p = {0};
l = {1};
Do[
l = Complement[
## & @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} & /@ l,
p = p ⋃ l
]~Cases~_Integer,
{#}
];
l
) &

# Pyth, 2624 21 bytes

Su+yMG-/R3fq4%T6G1Q]1

This code runs instantly for S=30. Try it out yourself: Demonstration

Thanks to @isaacg for saving 5 bytes.

### Explanation

My code starts with 1 and undos the Collatz function. It maps all numbers d of the S-1 step to 2*d and (d-1)/3. The last one in not always valid though.

implicit: Q = input number
u                Q     apply the following function Q-times to G:
update G by
yMG                      each number in G doubled
+                       +
fq4%T6G           filter G for numbers T, which satisfy 4==T%6
/R3                  and divide them by 3
-          1          and remove 1, if it is in the list
(to avoid jumping from 4 to 1)
S                       sort the result and print
• That's a beautiful use of -F. Commented May 28, 2015 at 23:05
• If you put a - ... 1 around the sum inside the reduce, you don't need the reduce to be a .u, nor the -F outside. Saves 2 characters. Commented May 28, 2015 at 23:16
• @isaacg Thanks. I actually had this in a previous version, but removed it during debugging an error. Commented May 28, 2015 at 23:29
• I've borrowed @isaacg's for my own answer. I've spent hours trying to find the shortest code for removing duplicates, but this is by far the most elegant solution. Also, I really like the youe use of a tuple to discard invalid quotients. Sadly, CJam doesn't have tuples, but I did manage to map invalid quotients to 1. Commented May 29, 2015 at 5:59
• @Jakube q4%d6 is equivalent to !%hhd6, but 1 character shorter. Commented May 29, 2015 at 6:32

# Python 2, 86837573 71 bytes

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,k/3)or[])+f(n-1,k*2))

Call like f(30). n = 30 is pretty much instant.

(Thanks to @DLosc for the idea of recursing by k being a number rather than a list of cousins, and a few bytes. Thank to @isaacg for dropping ~-.)

This variant is much shorter, but unfortunately takes too long due to exponential branching:

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6)*f(n-1,k/3)+f(n-1,k*2))
• Interesting--my original solution is very similar, but (taking a couple optimizations from yours) comes out 2 bytes shorter: f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n]. It's less efficient with the function calls but still does n = 30 in under a second. Commented May 29, 2015 at 2:00
• @DLosc I liked your idea and made it one better :) Commented May 29, 2015 at 2:30
• Nice! Here's 2 more bytes off: f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2)) Commented May 29, 2015 at 4:35
• @DLosc Ahaha thanks. I still swear there's got to be a better short-circuiting way though... Commented May 29, 2015 at 4:47
• I think the ~- is unnecessary because you're using integer division. Commented May 29, 2015 at 6:42

# CJam, 35 bytes

1]ri{_"(Z/Y*"3/m*:s:~\L+:L-_&0-}*$p Explanation coming soon. This is a much faster version than the "pretty straight forward" approach (see it in edit history). Try it online here for N = 30 which runs in seconds on the online version and instantly in the Java Compiler • How long will this take for the larger inputs? It should finish in seconds or minutes, not hours or days. Commented May 28, 2015 at 18:28 • Ah, I see. The Python version I wrote looked to take about 5 hours for N = 30. Commented May 28, 2015 at 18:39 • Latest version runs almost instantly. Commented May 28, 2015 at 20:32 • There's a bug in your code. The test-case S=15 doesn't work. Commented May 28, 2015 at 21:33 # Java 8, 123 x->java.util.stream.LongStream.range(1,(1<<x)+1).filter(i->{int n=0;for(;i>1;n++)i=i%2<1?i/2:3*i+1;return n==x;}).toArray() When x is 30, the program takes 15 minutes and 29 seconds. ## Expanded class Collatz { static IntFunction<long[]> f = x -> java.util.stream.LongStream.range(1, (1 << x) + 1).filter(i -> { int n = 0; for (; i > 1; n++) i = i % 2 < 1 ? i / 2 : 3 * i + 1; return n == x; }).toArray(); public static void main(String[] args) { System.out.println(Arrays.toString(f.apply(15))); } } • Just curious, how long does this take for S=30? Commented May 28, 2015 at 19:56 • This only works in Java 8, correct? Using javac 1.7.0_79 on Ubuntu gave me lots of syntax errors. Commented May 28, 2015 at 20:10 • @DLosc Correct; I'll mention that in the post. Commented May 28, 2015 at 20:13 • Restricting the loop terminal condition to i > 1 && ++n <= x (you can drop n++ too) seems to be even faster for just 5 more characters... about 3 minutes for S=30 for me. That gets shaved to safely under a minute if I include .parallel() too, but since this is code-golf... Commented May 29, 2015 at 5:42 # Python 2, 118 bytes Well, I figured that I wouldn't reach the best Python score after seeing @Sp3000's solution. But it looked like a fun little problem, so I wanted to try an independent solution anyway: s={1} for k in range(input()): p,s=s,set() for t in p:s.add(2*t);t>4and(t-1)%6==3and s.add((t-1)/3) print sorted(s) Same thing before stripping whitespace: s={1} for k in range(input()): p,s=s,set() for t in p: s.add(2 * t) t > 4 and (t - 1) % 6 == 3 and s.add((t - 1) / 3) print sorted(s) This is a very direct implementation of a breadth first search. In each step, we have the set with stopping time k, and derive the set with stopping time k + 1 by adding the possible predecessors of each value t in the set from step k: • 2 * t is always a possible predecessor. • If t can be written as 3 * u + 1, where u is an odd number that is not 1, then u is a predecessor as well. Takes about 0.02 seconds to run for N = 30 on my MacBook Pro. • In general, s.add(x) is unnecessary in a golf since you can usually do s|={x} instead. Also, using ~-x instead of (x+1) saves on brackets. But otherwise, good job :) Commented May 29, 2015 at 5:50 • @Sp3000 Thanks. I can't easily replace the second s.add() because it becomes an assignment, and can't be part of the expression anymore. It does work for the first one. The for loops based on counters are always kind of verbose as well. I thought I could shorten it by using a while loop, but it turned out to be exactly the same the same length. Commented May 29, 2015 at 6:21 • Instead of a for loop, since you don't use the input in any other way you can probably do exec"..."*input() instead :) Commented May 29, 2015 at 6:43 # PHP 5.4+, 178 bytes The function function c($s,$v=1,$p=[],&$r=[]){$p[]=$v;if(!$s--){return$r[$v][]=$p;}c($s,$v*2,$p,$r);is_int($b=($v-1)/3)&!in_array($b,$p)&$b%2?c($s,$b,$p,$r):0;ksort($r);return array_keys($r);}

Test & Output

echo "0 - ".implode(',',c(0)).PHP_EOL;
// 0 - 1
echo "1 - ".implode(',',c(1)).PHP_EOL;
// 1 - 2
echo "5 - ".implode(',',c(5)).PHP_EOL;
// 5 - 5,32
echo "9 - ".implode(',',c(9)).PHP_EOL;
// 9 - 12,13,80,84,85,512
echo "15 - ".implode(',',c(15)).PHP_EOL;
// 15 - 22,23,136,138,140,141,150,151,768,832,848,852,853,904,906,908,909,5120,5376,5440,5456,5460,5461,32768

S(30) runs in 0.24 seconds*, returns 732 elements. A couple are

86,87,89,520,522,524,525,528, [ ... ] ,178956928,178956960,178956968,178956970,1073741824

*To save on bytes, I had to add ksort and array_keys at every step. The only other choice I had was to make a small wrapper function that calls c() and then calls array_keys and ksort on the result once. But due to the time still being decently snappy, I decided to take the performance hit for low byte count. Without the proper sorting & processing, the time is 0.07 seconds on average for S(30).

If anyone has any clever ways of getting the proper processing only once without too many additional bytes, please let me know! (I store my numbers as array keys, hence the use of array_keys and ksort)

# C Language

#include <stdio.h>
#include <limits.h>
const int s = 30;

bool f(long i)
{
int r = 0;
for(;;)
if (i < 0 || r > s) return false;
else if (i == 1) break;
else{r ++;i = i % 2 ? 3*i + 1 : i/2;}
return (r==s);
}

void main(){
for(long i = 1; i < LONG_MAX; i++) if (f(i)) printf("%ld ", i);
}
• Hello and welcome to PPCG! Since this is a code-golf competition, you'll want to make your code as short as possible. Also, please include the name of the language in your post. Commented May 29, 2015 at 2:48
• You can hit the {} button to format your code, which I've done for you. But as Alex says, please add the language name (C?) and try golfing it :) But welcome! Commented May 29, 2015 at 2:49
• @Sp3000 thanks for helping format the code Commented May 29, 2015 at 3:00
• Function f is not behaving properly. With s=5, I get a bunch of incorrect results. if (r == s)return true; should be return (r==s), since f won't return anytging meaninful when (r < s). Also, I think you should declare i in f as long, since it will overflow pretty quickly for some values. Commented May 29, 2015 at 6:17
• @Dennis thanks:) it should be return (r==s); Commented May 29, 2015 at 9:43