The Collatz Urutan (juga disebut 3x + 1 masalah) adalah di mana Anda mulai dengan bilangan bulat positif, untuk contoh ini kita akan menggunakan 10, dan menerapkan set ini langkah-langkah untuk itu:

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

10 adalah genap, jadi kami membaginya dengan 2 untuk mendapatkan 5. 5 adalah ganjil, jadi kami mengalikannya dengan 3 dan menambahkan 1 untuk mendapatkan 16. 16 genap, jadi potong menjadi dua untuk mendapatkan 8. Setengah dari 8 adalah 4, setengah dari 4 adalah 2, dan setengah dari 2 adalah 1. Karena ini membawa kita 6 langkah, kita katakan bahwa 10 memiliki jarak berhenti 6.

Angka Super Collatz adalah angka yang jarak hentinya lebih besar daripada jarak hentinya setiap angka lebih kecil dari itu. Misalnya, 6 adalah nomor Super Collatz karena 6 memiliki jarak berhenti 8, 5 memiliki jarak berhenti 5, 4 memiliki 2, 3 memiliki 7, 2 memiliki 1 dan 1 memiliki 0. ( A006877 di OEIS) Anda harus ambil angka n sebagai input, dan keluarkan semua nomor Super Collatz hingga n .

Aturan

• Program atau fungsi penuh dapat diterima.

• Anda tidak dapat melakukan precompute atau melakukan hard-code urutan Super Collatz.

• Anda dapat mengambil input dalam format apa pun yang masuk akal.

• Output dapat dikembalikan sebagai daftar dari fungsi, atau dicetak ke STDOUT atau file. Mana yang paling nyaman.

• Input yang tidak valid (bukan angka, desimal, angka negatif, dll.) Menghasilkan perilaku yang tidak jelas.

Contoh python yang tidak dikerami

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

Sampel 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

Juga di sini adalah 44 nomor Super Collatz pertama:

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

Pyth, 23 byte

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

Demonstrasi

Ini berfungsi dengan mengambil maks rentang hingga setiap angka dengan jarak berhenti Collatz mereka, dan memeriksa apakah maks itu adalah angka yang dimaksud.

Python 2, 104 byte

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)))]

cadalah fungsi pembantu yang menghitung jarak Collatz untuk bilangan bulat yang diberikan. Lambda yang tidak disebutkan namanya adalah fungsi utama, yang menghitung angka-angka super Collatz hingga (tetapi tidak termasuk) input.

Dyalog APL , 41 byte

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

Fungsi yang tidak disebutkan namanya. Nama atau tanda kurung untuk diterapkan.

Kasus uji:

       ((∪⊢⍳⌈\)≢∘{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 menghasilkan perilaku yang tidak terdefinisi.

ES6, 86 83 byte

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])

Sunting: Disimpan 3 byte dengan beralih dari filterpemahaman array.

Haskell, 84 byte

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]]

Ini sangat lambat, tentu saja, tetapi berhasil!

Oracle SQL 11.2, 329 byte

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;

Versi tidak golf

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;

Tampilan q adalah tampilan rekursif sejati (bukan kueri hierarkis dengan CONNECT BY) yang menghitung semua langkah menuju 1 untuk setiap integer antara 1 dan: 1.

Tampilan v menghitung jarak berhenti.

Tampilan m menggunakan versi analitik MAX untuk menerapkannya pada setiap baris sebelumnya, tidak termasuk baris saat ini. Dengan begitu untuk setiap bilangan bulat kita tahu itu jarak berhenti dan jarak berhenti terbesar saat ini.

Permintaan akhir memeriksa apakah jarak berhenti lebih besar dari jarak berhenti terbesar. Dan menambahkan beberapa trik untuk menangani 1 dan kasus khusus: 1 memiliki nilai 0.

MATL , 37 byte

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

Cobalah 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

𝔼𝕊𝕄𝕚𝕟, 30 karakter / 38 byte

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

Try it here (Firefox only).

Satu-satunya alasan saya tidak memposting ini sebelumnya adalah karena saya tidak jelas tentang spesifikasinya. Menggunakan penyandian khusus yang menyandikan karakter 10-bit.

Penjelasan

⩥ïⓜmembuat rentang [0,input)untuk dipetakan. МȬ⧺$,a=[])menghasilkan nomor Collatz dalam array kosong, dan ⋎⟮aꝈ-1⟯>ɐmenggunakan array nomor Collatz untuk mendapatkan jarak berhenti dan memeriksa apakah itu lebih besar dari jarak berhenti maksimum sebelumnya. Jika demikian, ⅋(ɐ=Ⅰ,ᵖ$jadikan jarak pemberhentian saat ini sebagai jarak pemberhentian maksimum dan dorong item saat ini dalam kisaran ke tumpukan. Setelah itu, item tumpukan dicetak secara implisit.

Jelly , 17 byte

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

Cobalah online!

Mungkin mengejutkan, ini hanya 3 tautan! Mereka ×3‘µHḂ?µÐĿL$€, <Ṫ$dan Ạ.