pengantar
Teori bilangan penuh dengan keajaiban, dalam bentuk koneksi yang tidak terduga. Ini salah satunya.
Dua bilangan bulat yang co-prime jika mereka tidak memiliki faktor kesamaan selain 1. Mengingat nomor N , mempertimbangkan semua bilangan bulat dari 1 sampai N . Gambar dua bilangan bulat seperti itu secara acak (semua bilangan bulat memiliki probabilitas yang sama untuk dipilih pada setiap undian; undian bersifat independen dan dengan penggantian). Misalkan p menunjukkan probabilitas bahwa dua bilangan bulat yang dipilih adalah co-prime. Kemudian p cenderung ke 6 / π 2 ≈ 0,6079 ... karena N cenderung tak hingga.
Tantangan
Tujuan dari tantangan ini adalah untuk menghitung p sebagai fungsi dari N .
Sebagai contoh, pertimbangkan N = 4. Ada 16 pasangan yang mungkin diperoleh dari bilangan bulat 1,2,3,4. 11 dari pasangan tersebut adalah co-prime, yaitu (1,1), (1,2), (1,3), (1,4), (2,1), (3,1), (4,1) ), (2,3), (3,2), (3,4), (4,3). Jadi p adalah 11/16 = 0,6875 untuk N = 4.
The tepat nilai p perlu dihitung dengan setidaknya empat desimal. Ini menyiratkan bahwa perhitungan harus bersifat deterministik (berlawanan dengan Monte Carlo). Tapi itu tidak perlu menjadi penghitungan langsung dari semua pasangan seperti di atas; metode apa pun dapat digunakan.
Argumen fungsi atau stdin / stdout dapat digunakan. Jika menampilkan output, trailing zero dapat dihilangkan. Jadi misalnya 0.6300
bisa ditampilkan sebagai 0.63
. Ini harus ditampilkan sebagai angka desimal, bukan sebagai pecahan (menampilkan string 63/100
tidak diperbolehkan).
Kriteria yang menang adalah byte paling sedikit. Tidak ada batasan dalam penggunaan fungsi bawaan.
Uji kasus
Input / output (hanya empat desimal yang wajib, seperti yang ditunjukkan di atas):
1 / 1.000000000000000
2 / 0.750000000000000
4 / 0.687500000000000
10 / 0.630000000000000
100 / 0.608700000000000
1000 / 0.608383000000000
sumber
63/100
merupakan literal yang valid, dapat digunakan dalam perhitungan. (Langs yang saya bicarakan: Factor , Racket )Jawaban:
Jelly ,
128 byteCobalah online!
Kode biner berikut berfungsi dengan versi juru bahasa Jelly ini .
Ide
Jelas, jumlah pasangan (j, k) sedemikian rupa sehingga j ≤ k dan j dan k adalah co-prime sama dengan jumlah pasangan (k, j) yang memenuhi kondisi yang sama. Juga, jika j = k , j = 1 = k .
Jadi, untuk menghitung jumlah pasangan co-prime dengan koordinat antara 1 dan n , cukup untuk menghitung jumlah m dari pasangan (j, k) sedemikian sehingga j ≤ k , kemudian menghitung 2m - 1 .
Akhirnya, karena fungsi total Euler φ (k) menghasilkan bilangan bulat antara antara 1 dan k yang co-prime ke k , kita dapat menghitung m sebagai φ (1) + ... + φ (n) .
Kode
sumber
Mathematica
4342 byteSaya menemukan titik-titik Kisi terlihat dari asal , dari mana gambar di bawah ini diambil, untuk membantu dalam membingkai ulang masalah melalui pertanyaan-pertanyaan berikut mengenai wilayah kuadrat tertentu dari unit kisi:
Contohnya
Nol trailing dihilangkan.
Pengaturan waktu
Waktunya, dalam detik, mendahului jawabannya.
sumber
Pyth -
1311 byteTest Suite .
sumber
Mathematica,
4232 byteFungsi anonim, menggunakan kekuatan kasar sederhana. Kasing terakhir beroperasi sekitar 0,37 detik pada mesin saya. Penjelasan:
sumber
Count[Array[GCD,{#, #}],1,2]/#^2.&
Jadilah tamu saya.Dyalog APL, 15 byte
Cukup mudah. Ini adalah kereta fungsi monadik. Iota adalah angka dari 1 hingga input, jadi kami mengambil produk luar dengan gcd, lalu menghitung proporsi yang.
sumber
Oktaf,
4947 byteHanya menghitung
gcd
semua pasangan dan menghitung.sumber
kron
! Ide bagus!meshgrid
, tetapi kemudian saya perhatikan saya bisa melakukan hal yang sama dengankron
inline! (-> fungsi anonim)JavaScript (ES6), 88 byte
Penjelasan
Uji
Butuh beberapa saat untuk
>100
nilai ( ) yang besar darin
.Tampilkan cuplikan kode
sumber
Serius, 15 byte
Hex Dump:
Cobalah secara Online
Saya tidak akan repot menjelaskannya karena secara harfiah menggunakan algoritma yang persis sama dengan solusi Dennis's Jelly (meskipun saya mendapatkannya secara mandiri).
sumber
J,
1917 bytePemakaian:
Penjelasan:
Solusi Dennis memberikan penjelasan yang bagus bagaimana kita bisa menggunakan fungsi totient.
Cobalah online di sini.
sumber
Mathematica, 35 byte
Menerapkan algoritma @ Dennis.
Hitung jumlah totient (fungsi phi Euler) pada rentang dari 1 hingga nilai input. Lipat gandakan dengan floating point dua (dengan presisi empat digit) dan kurangi satu. (Lebih presisi dapat dipertahankan dengan menggunakan sebagai gantinya "
2
" dan "1`4
".) Ini adalah jumlah total pasangan koprime, jadi bagi dengan kuadrat input untuk mendapatkan fraksi yang diinginkan. Karena keduanya adalah angka perkiraan, demikian juga hasilnya.Pengujian (dengan data penghitungan waktu di kolom kiri karena setidaknya salah satu dari kami menganggap itu menarik), dengan fungsi yang ditetapkan
f
agar garis uji lebih mudah dibaca .:Sunting: Memperlihatkan jangkauan jangkauan input (menukar ketelitian dengan yang satu bukannya yang dua karena sebaliknya hasilnya menjadi agak monoton) dan menantang orang lain untuk melakukan hal yang sama ...
RepeatedTiming[]
melakukan perhitungan beberapa kali dan mengambil rata-rata kali, berusaha mengabaikan cache dingin dan efek lain yang menyebabkan pencilan waktu. Batas asimptotik adalahjadi untuk argumen> 10 ^ 4, kita bisa mengembalikan "0.6079" dan memenuhi persyaratan presisi dan akurasi yang ditentukan.
sumber
Julia, 95 byte
Hanya pendekatan sederhana untuk saat ini; Saya akan mencari solusi yang lebih pendek / lebih elegan segera. Ini adalah fungsi anonim yang menerima integer dan mengembalikan float. Untuk menyebutnya, tetapkan ke variabel.
Tidak Disatukan:
sumber
collect
objek malas untuk mengambilnyalength
.length
tidak memiliki metode yang ditentukan, yang merupakan kasus di sini untuk iterator kombinasi yang difilter. Demikian pulaendof
tidak akan berhasil karena tidak ada metode untuk tipe itugetindex
.range
tidak mengembalikan objek yang samacombinations
. Yang terakhir mengembalikan iterator atas kombinasi yang merupakan tipe terpisah tanpalength
metode yang ditentukan . Lihat di sini . (Juga:
sintaks lebih disukai daripadarange
untuk membangun rentang;))Sage, 55 byte
Berkat Sage menghitung semuanya secara simbolis, masalah epsilon alat berat dan titik apung tidak muncul. Tradeoff adalah, untuk mengikuti aturan format output, diperlukan panggilan tambahan untuk
n()
(fungsi aproksimal desimal).Cobalah online
sumber
MATL ,
2017 byteIni menggunakan versi bahasa saat ini (5.0.0) .
Pendekatan berdasarkan jawaban @ flawr .
Sunting (28 April 2015) : Cobalah online! Setelah jawaban ini diposting, fungsi
Y)
diubah namanya menjadiX:
; tautan termasuk perubahan itu.Contoh
Penjelasan
Jawaban lama: 20 byte
Penjelasan
sumber
PARI / GP , 25 byte
Membuat fungsi anonim akan menghemat satu byte, tetapi kemudian saya harus menggunakannya
self
membuatnya lebih mahal secara keseluruhan.sumber
Factor,
120113 byteSaya telah menghabiskan golf kelas ini dan saya tidak bisa membuatnya lebih pendek.
Terjemahan dari: Julia .
Contoh berjalan pada 5 kasus uji pertama (nilai 1000 menyebabkannya membekukan editor, dan saya tidak dapat diganggu untuk mengkompilasi yang dapat dieksekusi sekarang):
sumber
Samau , 12 byte
Penafian: Tidak bersaing karena saya memperbarui bahasa setelah pertanyaan diposting.
Hex dump (Samau menggunakan pengkodean CP737):
Menggunakan algoritma yang sama dengan jawaban Dennis di Jelly.
sumber
Python2 / Pypy, 178 byte
Itu
x
File:Berlari:
Kode ini menghitung pasangan co-prime
(n,m) for m<n
dua kali (c+=2
). Ini mengabaikan(i,i) for i=1..n
yang ok kecuali untuk(1,1)
, sehingga dikoreksi dengan menginisialisasi counter dengan1
(1.0
untuk mempersiapkan divisi float nanti) untuk mengkompensasi.sumber