Print the Super Collatz numbers

Question

The Collatz Sequence (also called the 3x + 1 problem) is where you start with any positive integer, for this example we will use 10, and apply this set of steps to it:

if n is even:
    Divide it by 2
if n is odd:
    Multiply it by 3 and add 1
repeat until n = 1

10 is even, so we divide by 2 to get 5. 5 is odd, so we multiply by 3 and add 1 to get 16. 16 is even, so cut it in half to get 8. Half of 8 is 4, half of 4 is 2, and half of 2 is 1. Since this took us 6 steps, we say that 10 has a stopping distance of 6.

A Super Collatz number is a number whose stopping distance is greater then the stopping distance of every number smaller than it. For example, 6 is a Super Collatz number since 6 has a stopping distance of 8, 5 has a stopping distance of 5, 4 has 2, 3 has 7, 2 has 1 and 1 has 0. (A006877 in the OEIS) You must take a number n as input, and output out all the Super Collatz numbers up to n.

Rules

• Full Program or function is acceptable.

• You can not precompute or hard-code the Super Collatz sequence.

• You can take input in any reasonable format.

• Output can be returned as a list from the function, or printed to STDOUT or a file. Whichever is most convenient.

• Invalid inputs (non-numbers, decimals, negative numbers, etc.) result in undefined behavior.

Sample ungolfed python

def collatzDist(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + collatzDist(n / 2)
    return 1 + collatzDist((n * 3) + 1)

n = input()

max = -1
superCollatz = []
for i in range(1, n + 1):
    dist = collatzDist(i)
    if dist > max:
        superCollatz.append(i)
        max = dist 

print superCollatz

Sample IO:

#in       #out
 4     --> 1, 2, 3
 50    --> 1, 2, 3, 6, 7, 9, 18, 25, 27
 0     --> invalid
 10000 --> 1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171

Also here are the first 44 Super Collatz numbers:

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799

Answer 1

Pyth, 23 bytes

q#eol.u@,/N2h*N3NN)STSQ

Demonstration

This works by taking the max of the range up to each number by their Collatz stopping distance, and checking whether that max is the number in question.

Answer 2

Python 2, 104 bytes

c=lambda x:x>1and 1+c([x/2,x*3+1][x%2])
lambda n:[1]+[x for x in range(2,n)if c(x)>max(map(c,range(x)))]

c is a helper function that calculates the Collatz distance for a given integer. The unnamed lambda is the main function, which computes the super Collatz numbers up to (but not including) the input.

Answer 3

Dyalog APL, 41 bytes

(∪⊢⍳⌈\)≢∘{1=⍵:⍬⋄2|⊃⌽⍵:⍵,∇1+3×⍵⋄⍵,∇⍵÷2}¨∘⍳

An unnamed function. Name or parenthesize to apply.

Test cases:

       ((∪⊢⍳⌈\)≢∘{1=⍵:⍬ ⋄ 2|⊃⌽⍵:⍵,∇ 1+3×⍵ ⋄ ⍵,∇ ⍵÷2}¨∘⍳)¨4 50 10000
┌─────┬────────────────────┬───────────────────────────────────────────────────────────────────────────────────────────┐
│1 2 3│1 2 3 6 7 9 18 25 27│1 2 3 6 7 9 18 25 27 54 73 97 129 171 231 313 327 649 703 871 1161 2223 2463 2919 3711 6171│
└─────┴────────────────────┴───────────────────────────────────────────────────────────────────────────────────────────┘

0 results in undefined behaviour.

Answer 4

Haskell, 84 bytes

c 1=0;c x|odd x=1+c(3*x+1)|0<1=1+c(div x 2)
f x=[n|n<-[1..x],all(c n>)$c<$>[1..n-1]]

This is massively slow, of course, but it works!

Answer 5

ES6, 86 83 bytes

n=>(i=m=0,c=n=>n<3?n:c(n&1?n*3+1:n/2)+1,[for(x of Array(n))if(c(++i)>m&&(m=c(i)))i])

Edit: Saved 3 bytes by switching from filter to an array comprehension.

Answer 6

Oracle SQL 11.2, 329 bytes

WITH q(s,i)AS(SELECT LEVEL s,LEVEL i FROM DUAL CONNECT BY LEVEL<=:1 UNION ALL SELECT s,DECODE(MOD(i,2),0,i/2,i*3+1)i FROM q WHERE i<>1),v AS(SELECT s,COUNT(*)-1 d FROM q GROUP BY s),m AS(SELECT s,d,MAX(d)OVER(ORDER BY s ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING)m FROM v)SELECT s FROM m WHERE(d>m OR s=1)AND:1>0ORDER BY 1;

Un-golfed version

WITH q(s,i) AS 
  (
    SELECT LEVEL s, LEVEL i 
    FROM DUAL CONNECT BY LEVEL <= :1
    UNION ALL 
    SELECT q.s, DECODE(MOD(i,2),0,i/2,i*3+1)i FROM q WHERE q.i <> 1
  )
, v AS (SELECT s, COUNT(*)-1 d FROM q GROUP BY s)
, m AS (SELECT s, d, MAX(d)OVER(ORDER BY s ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) m FROM v)
SELECT * FROM m WHERE (d>m OR s=1) AND :1>0
ORDER BY 1;

The q view is a true recursive view (not a hierarchical query with CONNECT BY) that compute all steps toward 1 for every integer between 1 and :1.

The v view compute the stopping distances.

The m view use the analytical version of MAX to apply it to every rows preceding, excluding the current row. That way for each integer we know it's stopping distance and the current greatest stopping distance.

The final query check if the stopping distance is greater than the greatest stopping distance. And adds a few tricks to handle 1 and the special case of :1 having a value of 0.

Answer 7

Jelly, 17 bytes

×3‘µHḂ?µÐĿL$€<Ṫ$Ạ

Try it online!

Maybe surprisingly, this is only 3 links! They're ×3‘µHḂ?µÐĿL$€, <Ṫ$ and Ạ.

Answer 8

MATL, 37 bytes

:"@tqX`t0)t2\?3*Q}2/]ht0)q]n]N$htY>=f

Try it online!

:         % vector [1,2,...N], where N is implicit input
"         % for each number in that range
  @       %   push that number, k
  tq      %   truthy iff k is not 1
  X`      %   while...do loop
    t0)   %     pick first number of array
    t2\   %     is it odd?
    ?     %     if so:
      3*Q %       multiply by 3 and add 1
    }     %     else
      2/  %       divide by 2
    ]     %     end if
    h     %     concatenate into array with previous numbers
    t0)q  %     duplicate, pick last number, is it 1? Leave that as while condition
  ]       %   end while
  n       %   number of elements of array. This is the stopping distance for k
]         % end for
N$h       % concatenate all stopping distances into an array
tY>       % duplicate and compute cumulative maximum
=f        % indices of matching elements. Implicitly display

Answer 9

, 30 chars / 38 bytes

⩥ïⓜМȬ⧺$,a=[])⋎⟮aꝈ-1⟯>ɐ⅋(ɐ=Ⅰ,ᵖ$

Try it here (Firefox only).

The only reason I didn't post this earlier was because I wasn't clear on the specs. Uses a custom encoding that encodes 10-bit chars.

Explanation

⩥ïⓜ creates a range [0,input) to map over. МȬ⧺$,a=[]) generates Collatz numbers in an empty array, and ⋎⟮aꝈ-1⟯>ɐ uses the array of Collatz numbers to get the stopping distance and check if that's greater than the previous maximum stopping distance. If so, ⅋(ɐ=Ⅰ,ᵖ$ makes the current stopping distance the maximum stopping distance and pushes the current item in the range to the stack. After, the stack's items are implicitly printed.