Jumlah kemurnian

27

Hari ini kita akan melihat urutan a , terkait dengan fungsi Collatz f :

masukkan deskripsi gambar di sini

Kami menyebutnya urutan bentuk z, f (z), f (f (z)), ... suatu urutan Collatz .

Angka pertama dalam urutan kami , a (1) , adalah 0 . Di bawah aplikasi berulang f , ia jatuh ke dalam siklus 0 → 0 →…

Angka terkecil yang belum kita lihat adalah 1, menghasilkan (2) = 1 . Di bawah penerapan berulang f , ia jatuh ke dalam siklus 1 → 4 → 2 → 1 →…

Sekarang kita telah melihat angka 2 dalam siklus di atas, sehingga angka terkecil berikutnya adalah a (3) = 3 , termasuk dalam siklus 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → ...

Dalam semua siklus di atas kita telah melihat 4 dan 5 sudah, jadi angka selanjutnya adalah (4) = 6 .

Sekarang Anda harus mendapatkan ide. a (n) adalah angka terkecil yang bukan bagian dari urutan Collatz untuk semua (1), ..., a (n - 1) .

Tulis program atau fungsi yang, dengan bilangan bulat positif n , mengembalikan a (n) . Kode terpendek dalam byte menang.


Testcases:

1  -> 0
2  -> 1
3  -> 3
4  -> 6
5  -> 7
6  -> 9
7  -> 12
8  -> 15
9  -> 18
10 -> 19
50 -> 114

(Ini adalah urutan OEIS A061641 .)

orlp
sumber
1
OEIS
FryAmTheEggman
3
Bisakah input nberbasiskan 0?
Luis Mendo
a(n+1) = a(n) odd: 3*a(n)+1, or a(n) even: a(n)/2
Karl Napf
@LuisMendo Maaf, saya entah bagaimana melewatkan pesan Anda. Tidak, mereproduksi urutan yang tepat seperti dalam tantangan.
orlp
Jika atidak berbasis 0, saya tidak mengerti mengapa Anda tampaknya "berbicara berbasis 0" di sini:a(n) is the smallest number that was not part of any Collatz sequences for all a(0), …, a(n − 1).
daniero

Jawaban:

5

Jelly , 20 19 byte

ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ
Ç¡Ṫ

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

Ç¡Ṫ              Main link. No explicit arguments. Default argument: 0
 ¡               Read an integer n from STDIN and do the following n times.
Ç                  Call the helper link.
  Ṫ              Tail; extract the last element of the resulting array.


ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ  Helper link. Argument: A (array)

  J              Yield all 1-based indices of A, i.e., [1, ..., len(A)]. Since 0
                 belongs to A, there is at least one index that does belong to A.
ḟ@               Filter-false swapped; remove all indices that belong to A.
   Ḣ             Head; extract the first index (i) that hasn't been removed.
           ÐĿ    Call the quicklink to the left on i, then until the results are no
                 longer unique. Collect all unique results in an array.
         Ḃ?      If the last bit of the return value (r) is 1:
       $           Apply the monadic 3-link chain to the left to r.
    ×3‘              Yield 3r + 1.
        H        Else, halve r.
              Ṛ  Yield A, reversed.
             ;   Concatenate the results array with reversed A.

Setelah n iterasi, nilai a (n + 1) akan berada di awal array. Karena kita menggabungkan array baru dengan salinan yang lama, ini berarti bahwa (n) akan berada di akhir.

Dennis
sumber
9

Haskell, 93 92 byte

c x|x<2=[[0,2]!!x]|odd x=x:c(3*x+1)|1<2=x:c(div x 2)
([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!)

Contoh penggunaan: ([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!) 10-> 19.

c xadalah siklus Collatz xdengan sedikit kecurangan x == 1. Fungsi utama loop melalui semua bilangan bulat dan membuat orang-orang yang tidak c xuntuk xdi [0..y-1]. Cukup banyak implementasi langsung dari definisi tersebut. Karena operator indeks Haskell !!berbasis 0, saya mulai -1untuk menambahkan nomor (jika tidak berguna) untuk memperbaiki indeks.

nimi
sumber
4

MATL , 46 40 byte

Oiq:"tX>Q:yX-X<`t0)to?3*Q}2/]h5M1>]Pv]0)

Cobalah online!

Penjelasan

Kode memiliki forloop luar yang menghasilkan nurutan Collatz, satu di setiap iterasi. Setiap urutan dihasilkan oleh do...whileloop dalam yang menghitung nilai baru dan menyimpannya dalam vektor urutan hingga 1atau 0diperoleh. Ketika kita selesai dengan urutan, vektor dibalik dan digabungkan ke vektor global yang berisi nilai-nilai dari semua urutan sebelumnya. Vektor ini dapat berisi nilai berulang. Pembalikan vektor urutan memastikan bahwa pada akhir loop luar hasil yang diinginkan (nilai awal dari urutan terakhir) akan berada di akhir vektor global.

Kode semu :

1  Initiallization
2  Generate n sequences (for loop):
3    Compute initial value for the k-th sequence
4    Generate the k-th sequence (do...while loop)
5      Starting from latest value so far, apply the Collatz algorithm to get next value
6      Update sequence with new value 
7      Check if we are done. If so, exit loop. We have the k-th sequence
8    Update vector of seen values
9  We now have the n sequences. Get final result

Kode yang dikomentari :

O           % Push 0                                                          1
iq:         % Input n. Generate [1 2 ... n-1]                                 ·
"           % For loop: repeat n-1 times. Let k denote each iteration         2
  t         %   Duplicate vector of all seen values                           · 3
  X>Q       %   Take maximum, add 1                                           · ·
  :         %   Range from 1 to that: these are potential initial values      · ·
  y         %   Duplicate vector of all seen values                           · ·
  X-X<      %   Set difference, minimum: first value not seen                 · ·
  `         %   Do...while: this generates the k-th Collatz sequence          · 4
    t0)     %     Duplicate, push last value of the sequence so far           · · 5
    to      %     Duplicate, parity: 1 if odd, 0 if even                      · · ·
    ?       %     If odd                                                      · · ·
      3*Q   %       Times 3, plus 1                                           · · ·
    }       %     Else                                                        · · ·
      2/    %       Half                                                      · · ·
    ]       %     End if                                                      · · ·
    h       %     Concatenate new value of the sequence                       · · 6
    5M      %     Push the new value again                                    · · 7
    1>      %     Does it exceed 1? This is the loop condition                · · ·
  ]         %   End do...while. The loops ends when we have reached 0 or 1    · ·
  P         %   Reverse the k-th Collatz sequence                             · 8
  v         %   Concatenate with vector of previously seen values             · ·
]           % End for                                                         ·
0)          % Take last value. Implicitly display.                            9
Luis Mendo
sumber
3

Brachylog , 70 67 65 63 62 byte

,[]:?:1ih.
,0<=X=,?'eXg{t{:2/.*?|:3*+.}gB,(?.sB;?:Bc:2&.)}:?c.

Cobalah online!

Biarawati Bocor
sumber
3

Python 2, 97 96 byte

r,=s={-1}
exec'n=r=min({r+1,r+2,r+3}-s)\nwhile{n}-s:s|={n};n=(n/2,3*n+1)[n%2]\n'*input()
print r

Mengambil keuntungan dari kenyataan bahwa semua kelipatan 3 adalah murni. Uji di Ideone .

Bagaimana itu bekerja

Pada baris pertama, r,=s={-1}set s = {-1} (set) dan r = -1 .

Selanjutnya kita membaca integer dari STDIN, ulangi string tertentu yang berkali-kali, kemudian jalankan. Ini sama dengan kode Python berikut.

for _ in range(input())
    n=r=min({r+1,r+2,r+3}-s)
    while{n}-s:
        s|={n}
        n=(n/2,3*n+1)[n%2]

Dalam setiap iterasi, kita mulai dengan mencari anggota terkecil dari {r + 1, r + 2, r + 3} yang bukan milik s . Dalam iterasi pertama, ini menginisialisasi r sebagai 0 .

Dalam semua proses selanjutnya, s mungkin (dan akan) berisi beberapa r + 1 , r + 2 dan r + 3 , tetapi tidak semuanya, karena semua kelipatan 3 adalah murni. Untuk memverifikasi pernyataan ini, perhatikan bahwa tidak ada kelipatan m dari 3 dalam bentuk 3k +1 . Yang menjadikan 2m sebagai satu-satunya pra-gambar yang mungkin, yang juga merupakan kelipatan dari 3 . Dengan demikian, m tidak dapat muncul dalam urutan Collatz dari angka apa pun yang kurang dari m , dan karenanya murni.

Setelah mengidentifikasi r dan menginisialisasi n , kita menerapkan fungsi Collatz dengan n=(n/2,3*n+1)[n%2]menambahkan setiap nilai menengah n ke set s dengan s|={n}. Setelah kita menemukan angka n yang sudah dalam s , {n}-sakan menghasilkan set kosong, dan iterasi berhenti.

Nilai terakhir r adalah elemen urutan yang diinginkan.

Dennis
sumber
1
Untuk menambah ini, bukti bahwa semua kelipatan 3 adalah murni. Lihatlah modulo urutan Collatz apa pun 3. Setelah penerapan aturan 3x + 1, modulo adalah 1. Setelah penerapan aturan x / 2, mod 1 menjadi 2, dan mod 2 menjadi 1. Tidak ada aturan yang dapat menghasilkan banyak dari 3, kecuali nilai awal sudah kelipatan lebih besar dari 3 yang dibelah dua. Tetapi itu adalah nilai yang lebih besar yang belum dihasilkan, jadi n = 0 (mod 3) => n adalah murni.
orlp
1

Pyth , 32 byte

VtQ=+Y.u?%N2h*3N/N2Z)=Zf!}TYhZ)Z

Suite uji.

Biarawati Bocor
sumber
1

Java, 148 byte

int a(int n){if(n<2)return 0;int f=a(n-1),b,i,c;do{f++;for(b=1,i=1;i<n;i++)for(c=i==2?4:a(i);c>1;c=c%2>0?c*3+1:c/2)b=c==f?0:b;}while(b<1);return f;}

Ide itu! (Peringatan: kompleksitas eksponensial karena nol optimasi.)

Mengubahnya dari satu do...whileloop ke forloop akan menjadi golfier, tetapi saya mengalami kesulitan melakukannya.

Saran bermain golf disambut seperti biasa.

Biarawati Bocor
sumber
Tidak banyak, tetapi Anda dapat bermain golf 1 byte dengan mengubah for(b=1,i=1;i<n;i++)ke for(b=1,i=0;++i<n;). Btw, saya mengerti mengapa ideone Anda kehilangan test case untuk 50, tetapi mengapa juga melewatkan 10? Itu bisa menanganinya tanpa masalah.
Kevin Cruijssen
@KevinCruijssen Karena pemformatan akan menjadi buruk.
Leaky Nun
Bukan peningkatan terbaik tapi saya tidak menghabiskan terlalu banyak waktu ... (147 byte)int a(int n){if(n<2)return 0;int f=a(n-1),b=0,i,c;for(;b<1;){f++;for(b=1,i=1;i<n;i++)for(c=i==2?4:a(i);c>1;c=c%2>0?c*3+1:c/2)b=c==f?0:b;}return f;}
Poke
1

Perl6, 96

my @s;my $a=0;map {while ($a=@s[$a]=$a%2??3*$a+1!!$a/2)>1 {};while @s[++$a] {}},2..slurp;$a.say;

Berdasarkan jawaban Perl 5 . Sedikit lebih lama sejak sintaks Perl6 kurang memaafkan daripada sintaksis Perl5, tapi saya akan puas dengan ini untuk saat ini.

bb94
sumber
0

PHP, 233 124 byte

<?$n=$argv[1];for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}echo$v;

+4 untuk fungsi:

function a($n){for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}return$v;}
Titus
sumber
0

Perl 5 - 74 byte

map{0 while 1<($a=$c[$a]=$a%2?$a*3+1:$a/2);0 while$c[++$a]}2..<>;print$a+0

Ini adalah solusi yang cukup mudah. Itu berulang kali menerapkan fungsi Collatz ke variabel $adan menyimpan dalam array @cbahwa nilainya telah terlihat, kemudian setelah mencapai 0 atau 1 itu bertambah $asampai itu angka yang belum terlihat. Ini diulangi beberapa kali sama dengan input minus 2, dan akhirnya nilai $ayang dikeluarkan.

faubi
sumber
0

Mathematica, 134 byte

f=If[EvenQ@#,#/2,3#+1]&;a@n_:=(b={i=c=0};While[i++<n-1,c=First[Range@Max[#+1]~Complement~#&@b];b=b~Union~NestWhileList[f,c,f@#>c&]];c)

Format yang lebih mudah dibaca:

f = If[EvenQ@#, #/2, 3#+1] &;                        Collatz function
a@n_ := (                                            defines a(n)
  b = {i = c = 0};                                   initializations
                                                       b is the growing sequence
                                                       of cycles already completed
  While[i++ < n - 1,                                 computes a(n) recursively
    c = First[Range@Max[# + 1]~Complement~# & @b];   smallest number not in b
    b = b~Union~NestWhileList[f, c, f@# > c &]       apply f to c repeatedly
                                                       until the answer is smaller
                                                       than c, then add this new
                                                       cycle to b
    ]
  ; c)                                                 output final value of c
Greg Martin
sumber