# Print the Super Collatz numbers

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

• Also, if anyone can find a number with a stopping distance of infinity (never reaches 1) I will give them the biggest bounty I can offer. =D – DJMcMayhem Feb 4 '16 at 1:09
• So will many mathematicians... :P – Rɪᴋᴇʀ Feb 4 '16 at 1:11
• – Doorknob Feb 4 '16 at 1:12
• This is only conjecture, but I suspect that rule 2 is a mathematical fact rather than just a challenge restriction. – trichoplax Feb 4 '16 at 1:14
• "You must take a number n as input, and output out all the Super Collatz numbers up to n" So if I understand this correctly you do NOT ask to output the first n super collatz number? Because that's what the Pyth answer does for example, so I think it's not clear enough. – Fatalize Feb 4 '16 at 7:52

# 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.

## 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.

# 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.

## 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.

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!

# 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.

# 𝔼𝕊𝕄𝕚𝕟, 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.

# Jelly, 17 bytes

×3‘$HḂ?ƬL$€<Ṫ$PµƇ  Try it online! I reckon there's still a couple of bytes that can be removed. ## How it works ×3‘$HḂ?ƬL$€<Ṫ$PµƇ - Main link. Takes n on the left
µƇ - Generate the list [1, 2, ..., n] and filter each i based on the following:
$€ - Over each j [1, 2, ..., i]: Ƭ - Do the following until reaching a fixed point: ? - If statement: Ḃ - Condition: i is odd$              -         If so:
×3                -           Multiply by 3
‘               -           Increment
H             -         Else: Halve
L         -      Take the length
Call this list of lengths l
\$    -   Group the previous two links and run over l
Ṫ     -     Remove the last value of l
<      -     Is this greater than each value in l?
P   -   Is this true for all values?