22
\$\begingroup\$

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
\$\endgroup\$
  • 6
    \$\begingroup\$ 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 \$\endgroup\$ – DJMcMayhem Feb 4 '16 at 1:09
  • 1
    \$\begingroup\$ So will many mathematicians... :P \$\endgroup\$ – Rɪᴋᴇʀ Feb 4 '16 at 1:11
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/12177/3808 \$\endgroup\$ – Doorknob Feb 4 '16 at 1:12
  • 5
    \$\begingroup\$ This is only conjecture, but I suspect that rule 2 is a mathematical fact rather than just a challenge restriction. \$\endgroup\$ – trichoplax Feb 4 '16 at 1:14
  • 1
    \$\begingroup\$ "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. \$\endgroup\$ – Fatalize Feb 4 '16 at 7:52
1
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

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

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
\$\endgroup\$
0
\$\begingroup\$

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

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

Jelly, 17 bytes

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

Try it online!

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

\$\endgroup\$

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.