21
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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" \$\endgroup\$ – JPMC May 29 '15 at 2:46
  • 1
    \$\begingroup\$ @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." \$\endgroup\$ – DLosc May 29 '15 at 2:56
  • \$\begingroup\$ 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. \$\endgroup\$ – JPMC May 29 '15 at 3:13
  • 1
    \$\begingroup\$ @DLosc Pyth, of course. \$\endgroup\$ – isaacg May 29 '15 at 7:52
  • 1
    \$\begingroup\$ Related, but not golfed: math.stackexchange.com/q/470782/20792 and math.stackexchange.com/q/1243841/20792 \$\endgroup\$ – Pureferret May 29 '15 at 7:54
7
\$\begingroup\$

Pyth, 26 24 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
                   ]1   start with G = [1]
 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
\$\endgroup\$
  • \$\begingroup\$ That's a beautiful use of -F. \$\endgroup\$ – isaacg May 28 '15 at 23:05
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – isaacg May 28 '15 at 23:16
  • \$\begingroup\$ @isaacg Thanks. I actually had this in a previous version, but removed it during debugging an error. \$\endgroup\$ – Jakube May 28 '15 at 23:29
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Dennis May 29 '15 at 5:59
  • \$\begingroup\$ @Jakube q4%d6 is equivalent to !%hhd6, but 1 character shorter. \$\endgroup\$ – isaacg May 29 '15 at 6:32
8
\$\begingroup\$

Mathematica, 98 92 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
) &
\$\endgroup\$
5
\$\begingroup\$

Python 2, 86 83 75 73 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))
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – DLosc May 29 '15 at 2:00
  • 1
    \$\begingroup\$ @DLosc I liked your idea and made it one better :) \$\endgroup\$ – Sp3000 May 29 '15 at 2:30
  • \$\begingroup\$ 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)) \$\endgroup\$ – DLosc May 29 '15 at 4:35
  • \$\begingroup\$ @DLosc Ahaha thanks. I still swear there's got to be a better short-circuiting way though... \$\endgroup\$ – Sp3000 May 29 '15 at 4:47
  • \$\begingroup\$ I think the ~- is unnecessary because you're using integer division. \$\endgroup\$ – isaacg May 29 '15 at 6:42
5
\$\begingroup\$

CJam, 29 26 bytes

Xari{{2*_Cmd8=*2*)}%1-}*$p

Credit goes to @isaacg for his idea to remove 1's after each iteration, which saved me two bytes directly and another one indirectly.

Try it online in the CJam interpreter (should finish in less than a second).

How it works

Xa       e# Push A := [1].
ri{      e# Read an integer from STDIN and do the following that many times:
  {      e# For each N in A:
    2*   e#     Push I := (N * 2) twice.
    _Cmd e#     Push (I / 12) and (I % 12).
     8=  e#     Push K := (I % 12 == 8).

         e#     (K == 1) if and only if the division ((N - 1) / 3) is exact and
         e#     yields an odd integer. In this case we can compute the quotient 
         e#     as (I / 12) * 2 + 1.

    *2*) e#     Push J := (I / 12) * K * 2 + 1.

         e#     This yields ((N - 1) / 3) when appropriate and 1 otherwise.
  }%     e# Replace N with I and J.
  1-     e# Remove all 1's from A.

         e# This serves three purposes:

         e# 1. Ones have been added as dummy values for inappropriate quotients.

         e# 2. Not allowing 1's in A avoids integers that have already stopped
         e#    from beginning a new cycle. Since looping around has been prevented,
         e#    A now contains all integers of a fixed stopping time.

         e# 3. If A does not contain duplicates, since the maps N -> I and N -> J
         e#      are inyective (exluding image 1) and yield integers of different
         e#      parities, the updated A won't contain duplicates either.

}*       e#
$p       e# print(sort(C))
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ How long will this take for the larger inputs? It should finish in seconds or minutes, not hours or days. \$\endgroup\$ – DLosc May 28 '15 at 18:28
  • \$\begingroup\$ Ah, I see. The Python version I wrote looked to take about 5 hours for N = 30. \$\endgroup\$ – DLosc May 28 '15 at 18:39
  • \$\begingroup\$ Latest version runs almost instantly. \$\endgroup\$ – Optimizer May 28 '15 at 20:32
  • 6
    \$\begingroup\$ There's a bug in your code. The test-case S=15 doesn't work. \$\endgroup\$ – Jakube May 28 '15 at 21:33
3
\$\begingroup\$

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)));
    }
}
\$\endgroup\$
  • \$\begingroup\$ Just curious, how long does this take for S=30? \$\endgroup\$ – Geobits May 28 '15 at 19:56
  • \$\begingroup\$ This only works in Java 8, correct? Using javac 1.7.0_79 on Ubuntu gave me lots of syntax errors. \$\endgroup\$ – DLosc May 28 '15 at 20:10
  • \$\begingroup\$ @DLosc Correct; I'll mention that in the post. \$\endgroup\$ – Ypnypn May 28 '15 at 20:13
  • \$\begingroup\$ 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... \$\endgroup\$ – h.j.k. May 29 '15 at 5:42
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Sp3000 May 29 '15 at 5:50
  • \$\begingroup\$ @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. \$\endgroup\$ – Reto Koradi May 29 '15 at 6:21
  • \$\begingroup\$ Instead of a for loop, since you don't use the input in any other way you can probably do exec"..."*input() instead :) \$\endgroup\$ – Sp3000 May 29 '15 at 6:43
1
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

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);
}
\$\endgroup\$
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – Alex A. May 29 '15 at 2:48
  • \$\begingroup\$ 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! \$\endgroup\$ – Sp3000 May 29 '15 at 2:49
  • \$\begingroup\$ @Sp3000 thanks for helping format the code \$\endgroup\$ – windy May 29 '15 at 3:00
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis May 29 '15 at 6:17
  • \$\begingroup\$ @Dennis thanks:) it should be return (r==s); \$\endgroup\$ – windy May 29 '15 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.