Menghitung Sepupu Collatz

21

Tentukan fungsi f (n) untuk bilangan bulat positif n sebagai berikut:

  • n / 2 , jika n genap
  • 3 * n + 1 , jika n ganjil

Jika Anda berulang kali menerapkan fungsi ini ke n lebih besar dari 0, hasilnya selalu konvergen ke 1 (meskipun belum ada yang bisa membuktikannya). Properti ini dikenal sebagai Dugaan Collatz .

Tentukan waktu berhenti integer sebagai berapa kali Anda harus melewati fungsi Collatz f sebelum mencapai 1. Berikut adalah waktu berhenti dari 15 integer pertama:

1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17

Mari kita sebut set angka dengan sepupu Collatz waktu berhenti yang sama . Misalnya, 5 dan 32 adalah sepupu Collatz, dengan waktu berhenti 5.

Tugas Anda: menulis sebuah program atau fungsi yang mengambil integer nonnegatif dan menghasilkan set sepupu Collatz yang waktu berhentinya sama dengan integer itu.

Memasukkan

Integer non negatif, diberikan melalui argumen STDIN, ARGV, atau fungsi.

Keluaran

Daftar semua angka yang waktu berhentinya adalah S, diurutkan dalam urutan menaik . Daftar tersebut dapat berupa output oleh program Anda, atau dikembalikan atau dihasilkan oleh fungsi Anda. Format output fleksibel: dipisahkan oleh spasi, dipisahkan oleh baris, atau format daftar standar bahasa Anda baik-baik saja, asalkan jumlahnya mudah dibedakan satu sama lain.

Persyaratan

Kiriman Anda harus memberikan hasil yang benar untuk setiap S ≤ 30. Itu harus selesai dalam hitungan detik atau menit, bukan jam atau hari.

Contohnya

0  -> 1
1  -> 2
5  -> 5, 32
9  -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768

Berikut adalah inti dari output untuk S = 30 .

Ini adalah : program terpendek dalam byte yang menang. Semoga berhasil!

DLosc
sumber
Bagaimana dengan siklus? Saya tidak melihat penyebutan siklus. Karena untuk S = 5, ada 3 nilai [4, 5, 32] karena Anda dapat memilih "1 - 2 - 4 - 1 - 2- 4"
JPMC
1
@JPMC Penghindaran siklus tersirat oleh definisi waktu berhenti. Waktu berhenti dari 4 adalah 2, bukan 5, karena 2 adalah "berapa kali Anda harus melewati fungsi Collatz sebelum mencapai 1."
DLosc
Ah, maafkan aku. Saya berpikir bahwa angka dapat memiliki beberapa kali berhenti, karena beberapa jalur dapat mengarah ke sana. Tapi itu sehubungan dengan membangun dari 1, tidak bekerja dari N. Maaf tentang itu.
JPMC
1
@Dlosc Pyth, tentu saja.
isaacg

Jawaban:

7

Pyth, 26 24 21 byte

Su+yMG-/R3fq4%T6G1Q]1

Kode ini berjalan seketika untuk S=30. Cobalah sendiri: Peragaan

Terima kasih kepada @isaacg untuk menghemat 5 byte.

Penjelasan

Kode saya mulai dengan 1dan membatalkan fungsi Collatz. Ini peta semua nomor ddari S-1langkah untuk 2*ddan (d-1)/3. Yang terakhir tidak selalu valid.

                        implicit: Q = input number
                   ]1   start with G = [1]
 u                Q     apply the following function Q-times to G:
                          update G by
   yMG                      each number in G doubled
  +                       +
          fq4%T6G           filter G for numbers T, which satisfy 4==T%6
       /R3                  and divide them by 3
      -          1          and remove 1, if it is in the list
                            (to avoid jumping from 4 to 1)
S                       sort the result and print
Jakube
sumber
Itu penggunaan yang indah -F.
isaacg
1
Jika Anda memasukkan - ... 1sekitar jumlah ke dalam pengurangan, Anda tidak perlu mengurangi menjadi .u, atau -Fluar. Menghemat 2 karakter.
isaacg
@isaacg Terima kasih. Saya sebenarnya memiliki ini di versi sebelumnya, tetapi menghapusnya saat men-debug kesalahan.
Jakube
3
Saya sudah meminjam @ isaacg untuk jawaban saya sendiri. Saya telah menghabiskan berjam-jam mencoba menemukan kode terpendek untuk menghapus duplikat, tetapi sejauh ini ini adalah solusi yang paling elegan. Juga, saya sangat suka menggunakan tuple untuk membuang negosiasi yang tidak valid. Sedihnya, CJam tidak memiliki tupel, tetapi saya berhasil memetakan negosiasi yang tidak valid menjadi 1.
Dennis
@Jakube q4%d6setara dengan !%hhd6, tetapi 1 karakter lebih pendek.
isaacg
8

Mathematica, 98 92 89 byte

Solusi ini S = 30langsung terpecahkan :

(p={0};l={1};Do[l=Complement[##&@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&/@l,p=p⋃l],{#}];l)&

Ini adalah fungsi tanpa nama yang mengambil Sparameter dan mengembalikan daftar sepupu Collatz.

Algoritma ini adalah pencarian pertama yang sederhana. Sepupu Collatz untuk diberikan Sadalah semua bilangan bulat yang dapat dihubungi dari sepupu Collatz untuk S-1melalui 2*natau angka ganjil yang dapat dihubungi melalui (n-1)/3. Kita juga perlu memastikan bahwa kita hanya menghasilkan bilangan bulat yang dicapai untuk pertama kali setelah Slangkah, jadi kita melacak semua sepupu sebelumnya pdan menghapusnya dari hasil. Karena kita tetap melakukan itu, kita dapat menyimpan beberapa byte dengan menghitung langkah-langkah dari semua sepupu sebelumnya (bukan hanya yang dari S-1) untuk menyimpan beberapa byte (yang membuatnya sedikit lebih lambat, tetapi tidak terasa diperlukan S).

Ini adalah versi yang sedikit lebih mudah dibaca:

(
  p = {0};
  l = {1};
  Do[
    l = Complement[
      ## & @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} & /@ l,
      p = p ⋃ l
    ]~Cases~_Integer,
    {#}
  ];
  l
) &
Martin Ender
sumber
5

Python 2, 86 83 75 73 71 byte

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,k/3)or[])+f(n-1,k*2))

Sebut seperti f(30). n = 30cukup instan.

(Terima kasih kepada @DLosc untuk gagasan pengulangan dengan kmenjadi nomor daripada daftar sepupu, dan beberapa byte. Terima kasih kepada @isaacg karena telah menjatuhkan ~-.)

Varian ini jauh lebih pendek, tetapi sayangnya terlalu lama karena percabangan eksponensial:

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6)*f(n-1,k/3)+f(n-1,k*2))
Sp3000
sumber
Menarik - solusi asli saya sangat mirip, tetapi (mengambil beberapa optimasi dari Anda) keluar 2 byte pendek: f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n]. Ini kurang efisien dengan pemanggilan fungsi tetapi masih dilakukan n = 30di bawah satu detik.
DLosc
1
@Dosc. Saya menyukai ide Anda dan menjadikannya lebih baik :)
Sp3000
Bagus! Berikut 2 byte lagi:f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2))
DLosc
@Dosc Ahaha terima kasih. Saya masih bersumpah pasti ada cara hubungan arus pendek yang lebih baik ...
Sp3000
Saya pikir ~-itu tidak perlu karena Anda menggunakan divisi integer.
isaacg
5

CJam, 29 26 byte

Xari{{2*_Cmd8=*2*)}%1-}*$p

Kredit pergi ke @isaacg untuk idenya untuk menghapus 1 setelah setiap iterasi, yang menyelamatkan saya dua byte secara langsung dan satu lagi secara tidak langsung.

Cobalah online di juru bahasa CJam (harus selesai dalam waktu kurang dari satu detik).

Bagaimana itu bekerja

Xa       e# Push A := [1].
ri{      e# Read an integer from STDIN and do the following that many times:
  {      e# For each N in A:
    2*   e#     Push I := (N * 2) twice.
    _Cmd e#     Push (I / 12) and (I % 12).
     8=  e#     Push K := (I % 12 == 8).

         e#     (K == 1) if and only if the division ((N - 1) / 3) is exact and
         e#     yields an odd integer. In this case we can compute the quotient 
         e#     as (I / 12) * 2 + 1.

    *2*) e#     Push J := (I / 12) * K * 2 + 1.

         e#     This yields ((N - 1) / 3) when appropriate and 1 otherwise.
  }%     e# Replace N with I and J.
  1-     e# Remove all 1's from A.

         e# This serves three purposes:

         e# 1. Ones have been added as dummy values for inappropriate quotients.

         e# 2. Not allowing 1's in A avoids integers that have already stopped
         e#    from beginning a new cycle. Since looping around has been prevented,
         e#    A now contains all integers of a fixed stopping time.

         e# 3. If A does not contain duplicates, since the maps N -> I and N -> J
         e#      are inyective (exluding image 1) and yield integers of different
         e#      parities, the updated A won't contain duplicates either.

}*       e#
$p       e# print(sort(C))
Dennis
sumber
4

CJam, 35 byte

1]ri{_"(Z/Y*"3/m*:s:~\L+:L-_&0-}*$p

Penjelasan segera hadir. Ini adalah versi yang jauh lebih cepat daripada pendekatan "cukup lurus ke depan" (lihat di edit history).

Cobalah online di sini untuk N = 30yang berjalan di detik pada versi online dan langsung di Compiler Java

Pengoptimal
sumber
Berapa lama ini akan membutuhkan input yang lebih besar? It should finish in seconds or minutes, not hours or days.
DLosc
Ah, begitu. Versi Python yang saya tulis terlihat membutuhkan waktu sekitar 5 jam untuk N = 30.
DLosc
Versi terbaru berjalan hampir secara instan.
Pengoptimal
6
Ada bug dalam kode Anda. Kasing uji S=15tidak berfungsi.
Jakube
3

Java 8, 123

x->java.util.stream.LongStream.range(1,(1<<x)+1).filter(i->{int n=0;for(;i>1;n++)i=i%2<1?i/2:3*i+1;return n==x;}).toArray()

Kapan x30, program ini memakan waktu 15 menit dan 29 detik.

Diperluas

class Collatz {
    static IntFunction<long[]> f =
            x -> java.util.stream.LongStream.range(1, (1 << x) + 1).filter(i -> {
                int n = 0;
                for (; i > 1; n++)
                    i = i % 2 < 1 ? i / 2 : 3 * i + 1;
                return n == x;
            }).toArray();

    public static void main(String[] args) {
        System.out.println(Arrays.toString(f.apply(15)));
    }
}
Ypnypn
sumber
Hanya ingin tahu, berapa lama untuk S = 30?
Geobits
Ini hanya berfungsi di Java 8, benar? Menggunakan javac 1.7.0_79di Ubuntu memberi saya banyak kesalahan sintaks.
DLosc
@Dosc tepat; Saya akan menyebutkannya di pos.
Ypnypn
Membatasi kondisi terminal loop menjadi i > 1 && ++n <= x(Anda dapat drop n++juga) tampaknya bahkan lebih cepat untuk hanya 5 karakter ... sekitar 3 menit untuk S = 30 untuk saya. Itu akan dicukur dengan aman di bawah satu menit jika saya termasuk .parallel()juga, tetapi karena ini adalah kode-golf ...
hjk
1

Python 2, 118 byte

Yah, saya pikir saya tidak akan mencapai skor Python terbaik setelah melihat solusi @ Sp3000. Tapi itu tampak seperti masalah kecil yang menyenangkan, jadi saya ingin mencoba solusi independen:

s={1}
for k in range(input()):
 p,s=s,set()
 for t in p:s.add(2*t);t>4and(t-1)%6==3and s.add((t-1)/3)
print sorted(s)

Hal yang sama sebelum membuka spasi:

s={1}
for k in range(input()):
    p,s=s,set()
    for t in p:
        s.add(2 * t)
        t > 4 and (t - 1) % 6 == 3 and s.add((t - 1) / 3)
print sorted(s)

Ini adalah implementasi yang sangat langsung dari pencarian pertama yang luas. Di setiap langkah, kami memiliki set dengan waktu berhenti k, dan menurunkan set dengan waktu berhenti k + 1dengan menambahkan kemungkinan pendahulu dari setiap nilai tdalam set dari langkah k:

  • 2 * t selalu merupakan pendahulu yang mungkin.
  • Jika tdapat ditulis sebagai 3 * u + 1, di mana uangka ganjil yang bukan 1, maka umerupakan pendahulu juga.

Diperlukan waktu sekitar 0,02 detik untuk dijalankan N = 30di MacBook Pro saya.

Reto Koradi
sumber
Secara umum, s.add(x)tidak perlu bermain golf karena biasanya Anda bisa melakukannya s|={x}. Juga, menggunakan ~-xbukannya (x+1)menyimpan di kurung. Tetapi sebaliknya, kerja bagus :)
Sp3000
@ Sp3000 Terima kasih. Saya tidak bisa dengan mudah mengganti yang kedua s.add()karena itu menjadi tugas, dan tidak bisa menjadi bagian dari ekspresi lagi. Ini berhasil untuk yang pertama. The forloop berdasarkan counter selalu jenis verbose juga. Saya pikir saya bisa memperpendeknya dengan menggunakan whileloop, tetapi ternyata persis sama dengan panjang yang sama.
Reto Koradi
Alih-alih forloop, karena Anda tidak menggunakan input dengan cara lain yang mungkin bisa Anda lakukan exec"..."*input()sebagai gantinya :)
Sp3000
1

PHP 5.4+, 178 byte

Fungsinya

function c($s,$v=1,$p=[],&$r=[]){$p[]=$v;if(!$s--){return$r[$v][]=$p;}c($s,$v*2,$p,$r);is_int($b=($v-1)/3)&!in_array($b,$p)&$b%2?c($s,$b,$p,$r):0;ksort($r);return array_keys($r);}

Uji & Keluaran

echo "0 - ".implode(',',c(0)).PHP_EOL;
// 0 - 1
echo "1 - ".implode(',',c(1)).PHP_EOL;
// 1 - 2
echo "5 - ".implode(',',c(5)).PHP_EOL;
// 5 - 5,32
echo "9 - ".implode(',',c(9)).PHP_EOL;
// 9 - 12,13,80,84,85,512
echo "15 - ".implode(',',c(15)).PHP_EOL;
// 15 - 22,23,136,138,140,141,150,151,768,832,848,852,853,904,906,908,909,5120,5376,5440,5456,5460,5461,32768

S (30) berjalan dalam 0,24 detik * , mengembalikan 732 elemen. Pasangan adalah

86,87,89,520,522,524,525,528, [ ... ] ,178956928,178956960,178956968,178956970,1073741824

* Untuk menghemat byte, saya harus menambahkan ksortdan array_keysdi setiap langkah. Satu-satunya pilihan lain yang saya miliki adalah membuat fungsi pembungkus kecil yang memanggil c()dan kemudian memanggil array_keysdan ksorthasilnya sekali. Tetapi karena waktu masih cukup tajam, saya memutuskan untuk mengambil hit kinerja untuk jumlah byte yang rendah. Tanpa penyortiran & pemrosesan yang tepat, waktunya rata-rata 0,07 detik untuk S (30).

Jika ada yang punya cara cerdik untuk mendapatkan pemrosesan yang tepat hanya sekali tanpa terlalu banyak byte tambahan, beri tahu saya! (Saya menyimpan nomor saya sebagai kunci array, maka penggunaan array_keysdan ksort)

JPMC
sumber
0

Bahasa C

#include <stdio.h>
#include <limits.h>    
const int s = 30;

bool f(long i)
{
    int r = 0;
    for(;;)
        if (i < 0 || r > s) return false;
        else if (i == 1) break;
        else{r ++;i = i % 2 ? 3*i + 1 : i/2;}
    return (r==s);
}

void main(){
    for(long i = 1; i < LONG_MAX; i++) if (f(i)) printf("%ld ", i);
}
berangin
sumber
5
Halo dan selamat datang di PPCG! Karena ini adalah kompetisi kode-golf , Anda harus membuat kode sesingkat mungkin. Juga, harap sertakan nama bahasa dalam posting Anda.
Alex A.
Anda dapat menekan {}tombol untuk memformat kode Anda, yang telah saya lakukan untuk Anda. Tapi seperti kata Alex, tolong tambahkan nama bahasa (C?) Dan coba mainkan :) Tapi selamat datang!
Sp3000
@ Sp3000 terima kasih telah membantu memformat kode
berangin
Fungsi ftidak berlaku dengan benar. Dengan s=5, saya mendapatkan banyak hasil yang salah. if (r == s)return true;seharusnya return (r==s), karena ftidak akan mengembalikan apa pun saat bermakna (r < s). Juga, saya pikir Anda harus menyatakan idalam fseperti long, karena akan meluap cukup cepat untuk beberapa nilai.
Dennis
@Dennis terima kasih :) mestinyareturn (r==s);
berangin