Serangan Collatz!

8

Tantangan ini didasarkan pada beberapa temuan baru yang berkaitan dengan dugaan Collatz dan dirancang agak dalam semangat proyek polymath kolaboratif . Memecahkan dugaan penuh dianggap sangat sulit atau mungkin mustahil oleh para ahli teori matematika / bilangan, tetapi tugas yang lebih sederhana ini cukup bisa dilakukan dan ada banyak contoh kode sampel. Dalam skenario kasus terbaik, wawasan teoretis baru dapat diperoleh ke dalam masalah berdasarkan entri kontestan / kecerdikan / kreativitas.

Temuan baru adalah sebagai berikut: Bayangkan serangkaian bersebelahan bilangan bulat [ n1 ... n2 ] mengatakan m Total. Tetapkan bilangan bulat ini ke struktur daftar. Sekarang versi umum dugaan Collatz dapat dilanjutkan sebagai berikut. Ulangi salah satu bilangan bulat m (atau lebih sedikit) dalam daftar selanjutnya berdasarkan pada beberapa kriteria / algoritma pemilihan. Hapus bilangan bulat itu dari daftar jika mencapai 1. Jelas dugaan Collatz setara dengan menentukan apakah proses ini selalu berhasil untuk semua pilihan n1, n2 .

Ini adalah twist, kendala tambahan. Pada setiap langkah, tambahkan m iterate iterates dalam daftar bersama. Kemudian pertimbangkan fungsi f (i) di mana i adalah nomor iterasi dan f (i) adalah jumlah dari iterasi saat ini dalam daftar. Cari f (i) dengan properti "bagus" tertentu.

Konsep keseluruhan / keseluruhan lebih baik / lebih lengkap didokumentasikan di sini (dengan banyak contoh di ruby). Temuannya adalah bahwa strategi / heuristik / algoritma yang cukup sederhana yang mengarah ke "penurunan secara monoton" f (i) ada dan banyak contoh diberikan pada halaman itu. Berikut adalah salah satu contoh output grafis (diplot melalui gnuplot):

Jadi inilah tantangannya: Gunakan variasi pada contoh-contoh yang ada atau ide yang sama sekali baru untuk membangun algoritma seleksi yang menghasilkan f (i) "sedekat mungkin dengan penurunan monoton". Peserta harus menyertakan grafik f (i) dalam pengiriman mereka. Pemilih dapat memberikan suara berdasarkan grafik itu & ide algoritmik dalam kode.

Kontes akan didasarkan pada n1 = 200 / n2 = 400 parameter saja! (Hal yang sama pada halaman contoh.) Tapi semoga kontestan akan menjelajahi daerah lain dan juga berusaha untuk menggeneralisasi algoritma mereka.

Catatan, salah satu taktik yang mungkin sangat berguna di sini adalah algoritma tipe gradient descent, atau algoritma genetika.

Dapat mendiskusikan semua ini lebih lanjut dalam obrolan untuk peserta yang tertarik.

Untuk beberapa ref, tantangan codegolf Collatz lainnya: Collatz Conjecture (oleh Doorknob )

vzn
sumber
5
Tolong huruf kapitalisasi!
TheDoctor
1
Mengapa orang memilih untuk ditutup? Sangat menyenangkan memiliki pertanyaan non-stereotip! Saya masalah terlalu banyak berpikir / membaca yang terlibat dalam memahami pertanyaan ?!
Mau
2
iterate di sini berarti "maju ke 'iterate' berikutnya dalam urutan Collatz untuk integer itu"
vzn
1
Sepertinya contoh yang Anda
kirim
1
@vzn Saya tidak bisa menjanjikan pengajuan dalam waktu dekat, karena saya akan pergi liburan akhir pekan ini setelah sekolah berakhir, dan semuanya agak sibuk sekarang. Namun, saya pasti akan bereksperimen dengan ini - setelah semua, ini adalah pendekatan baru untuk masalah yang saya temukan sangat menarik. :)
apnorton

Jawaban:

4

Saya menulis beberapa kode dengan Python 2 untuk menjalankan algoritma untuk tantangan ini:

import matplotlib.pyplot as plt

def iterate(n):
    return n*3+1 if n%2 else n/2
def g(a):
    ##CODE GOES HERE
    return [True]*len(a)
n1=input()
n2=input()
a=range(n1,n2+1)
x=[]
y=[]
i=0
while any(j>1 for j in a):
    y.append(sum(a))
    x.append(i)
    i+=1
    b=g(a)
    for j in range(len(a)):
        if b[j]:
            a[j]=iterate(a[j])
plt.plot(x,y)
plt.show()

g(x) mengambil daftar nilai dan mengembalikan daftar bools untuk apakah masing-masing harus diubah.

Itu termasuk hal pertama yang saya coba, sebagai baris setelah komentar, yang iterating semua nilai dalam daftar. Saya mengerti:

Percobaan 1

Itu tidak terlihat dekat dengan monoton, jadi saya mencoba iterasi hanya nilai-nilai yang akan mengurangi jumlah, jika ada, iterasi yang akan meningkatkan paling tidak sebaliknya:

l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m=[n[i]-a[i] for i in range(l)]
return [m[i]==min(m) for i in range(l)]

Sayangnya, itu tidak berakhir (setidaknya untuk n1=200, n2=400). Saya mencoba melacak nilai yang saya lihat sebelumnya dengan menginisialisasi c=set():

l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m={i:n[i]-a[i] for i in range(l)}
r=[i for i in m if m[i]==min(m.values())]
while all([a[i] in c for i in r]) and m != {}:
    m={i:m[i] for i in m if a[i] not in c}
    r+=[i for i in m.keys() if m[i]==min(m.values())]
for i in r:
    c.add(a[i])
return [i in r for i in range(l)]

Tapi itu juga tidak berakhir.

Saya belum mencoba yang lain, tetapi jika saya punya ide baru, saya akan mempostingnya di sini.

KSFT
sumber
+1 thx untuk minat Anda & menghidupkan kembali tantangan. ini tidak terlalu baik untuk kinerja tetapi Anda tetap menerima, isyarat kecil saya thx :) ... juga orang lain yang tertarik jangan ragu untuk mengobrol tentang hal itu atau mengundang saya ke dalam obrolan untuk membahas lebih lanjut
vzn
2

Python 3

Gagasan utama saya adalah menambahkan setiap angka Urutan Collatz ke f(i)fungsi secara individual sedemikian rupa sehingga meminimalkan peningkatan total f(i). Fungsi yang dihasilkan tidak sepenuhnya menurun tetapi memiliki struktur yang bagus (menurut saya :)). Grafik kedua dibuat dengan interval yang lebih panjang untuk f(i)dan fungsi hukuman yang sedikit berbeda. Kode pada Gist.

Collatz1 Collatz2

Saat menggunakan aturan (3 * n + 1) / 2, bukannya 3 * n + 1, algoritma menghasilkan monoton sepenuhnya f(i)! Saya yakin modifikasi ini dapat membuat grafik vzn jauh lebih lancar juga. Grafik kedua dibuat dengan interval yang lebih panjang untuk f(i). Kode pada Gist.

Collatz3 Collatz4

Kedua hasil serupa untuk [n,2*n]rentang yang lebih besar .

randomra
sumber
Kedua 2 adalah novel / hebat, entri luar terbaik sejauh ini! penurunan yang sepenuhnya monoton adalah sesuatu seperti terobosan! jika Anda dapat menunjukkan itu bekerja pada iterasi mulai semakin besar dalam "cara yang sama", itu adalah kandidat strategi bukti aktual ...!
vzn
@vzn Dengan beberapa modifikasi ketat monoton ftampaknya dapat dicapai. Bahkan jika algoritma saya saat ini gagal ada ruang yang cukup untuk perbaikan. Saya akan membiarkannya berjalan dan melihat apakah gagal untuk beberapa n(lebih dari 200). Monoton yang ketat lebih kuat dari dugaan Collatz sehingga saya bisa meneruskannya untuk saat ini. :) Apakah fungsi Anda berfungsi dengan baik dengan aturan (3n + 1) / 2? Mengapa Anda tidak menggunakannya?
randomra
@vzn Begitu banyak ide ... Hambatan utama adalah xkcd yang relevan :). Penurunan monoton tampaknya berlaku. Sebuah [1,n]rentang mungkin akan lebih menarik karena ada kami juga bisa bertanya (jika monoton memegang) apakah kita dapat membuat [1,n+1]dengan tidak memodifikasi [1,n]satu dan menambahkan n+1urutan untuk itu.
randomra
senang melihat inspirasi bersama! strategi pembuktian bisa berjalan baik, misalnya dalam "blok" berukuran konstan. dari percobaan pada pg yang dikutip, berbagai strategi cenderung "istirahat" untuk n yang lebih besar . deskripsi yang lebih rinci tentang algoritma Anda dalam kata-kata akan sangat bagus.
vzn
Saya porting ini untuk ruby ​​& melakukan beberapa percobaan dasar, hasil grafik di sini . kode tampaknya memiliki sedikit ketergantungan pada nondeterminisme dalam jenis tetapi mungkin tidak untuk n yang lebih besar.
vzn