Diberi angka n >= 2
, output semua bilangan bulat positif kurang dari n
tempat gcd(n, k) == 1
(dengan k
menjadi salah satu dari nomor output). Jumlah semacam ini saling memberontak satu sama lain.
Contoh: 10
memberikan output [1, 3, 7, 9]
(dalam bentuk apa pun yang Anda suka, asalkan jumlahnya dipisahkan secara jelas dan dalam semacam daftar). Daftar tidak dapat memiliki entri duplikat dan tidak harus diurutkan.
Lebih banyak kasus uji:
2 -> [1]
3 -> [1, 2]
6 -> [1, 5]
10 -> [1, 3, 7, 9]
20 -> [1, 3, 7, 9, 11, 13, 17, 19]
25 -> [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24]
30 -> [1, 7, 11, 13, 17, 19, 23, 29]
Kami juga tidak menghitung angka-angka di atas n
yang sesuai n
, hanya karena saya cukup yakin ada solusi tak terbatas.
Perhatikan juga: Angka-angka yang saling coprime juga dikatakan relatif prima atau sama-sama prima satu sama lain.
code-golf
math
number-theory
primes
Rɪᴋᴇʀ
sumber
sumber
1\n3\n
) Dihitung sebagai output yang valid?Jawaban:
Jelly , 3 byte
Cobalah online!
Bagaimana cara kerjanya?
Bukti validitas
Karena kita ingin mengekstrak coprimes saja, nilai minimum dari daftar Greatest-Common-pembagi memiliki menjadi 1 untuk
ÐṂ
trik bekerja. Mari kita buktikan bahwa (dalam dua metode berbeda):Kisaran yang dihasilkan secara implisit, berisi dan . Pembagi umum terbesar adalah integer yang benar-benar positif, karenanya dijamin akan terjadi dan akan selalu menjadi nilai minimum.[ 1 , masukan ] 1 1gcd ( 1 , x ) = 1∀x ∈ Z∗ 1
Dua bilangan bulat positif berturut-turut selalu merupakan koprime. Pertimbangkan , dengan . Kemudian kita mengambil bilangan bulat positif lain sehingga dan . y = x + 1 k k ∣ x k ∣ yx , y∈ Z∗ y= x + 1 k k ∣ x k ∣ y
Ini menyiratkan bahwa , jadi , dengan demikian . Satu-satunya bilangan bulat positif untuk membagi adalah itu sendiri, sehingga dijamin akan muncul dalam daftar dan akan selalu menjadi nilai minimum.k ∣ ( x + 1 - x ) k ∣ 1 1 1k ∣ ( y- x ) k ∣ ( x + 1 - x ) k ∣ 1 1 1
sumber
ÐṂ
ada saat itu, toh saya cukup puas dengan yang ini.DṂ
memang ada, tetapi hanya bekerja untuk monad. Komit dilaksanakanÞ
,ÐṂ
,ÐṀ
untuk diad tanggal 9 Mei 2017.Python 2 ,
6147 byteCobalah online!
Latar Belakang
Pertimbangkan cincin itu . Sementara cincin ini biasanya didefinisikan menggunakan modul residu modulo , ia juga dapat dianggap sebagai himpunan , di mana operator penjumlahan dan multiplikasi ditentukan oleh dan , di mana menunjukkan penambahan yang biasa, perkalian, dan operator modulo melalui bilangan bulat.n Z n( Zn, +n, ⋅n) n a + n b = ( a + b )Zn= { 0 , ... , n - 1 } a ⋅ n b = a ⋅ ba +nb = ( a + b )%n + ,a ⋅nb = a ⋅ b%n +,⋅, and %
Dua elemen dan dari disebut saling inversi multiplikatif modulo jika . Perhatikan bahwa setiap kali .a Z n n a ⋅ n b = 1b Zn n 1a⋅nb=1%n n > 11%n=1 n>1
Fix dan membiarkan menjadi coprime dari di . Jika untuk dua elemen dan dari , kita memiliki . Ini menyiratkan bahwa , dan kami mengikuti , yaitu, membagi secara merata. Karena tidak berbagi pembagi utama dengan , ini berarti bahwa . Akhirnya, karenaa n Z n a ⋅ n x = a ⋅ n y x y Z n a ⋅ xn>1 a n Zn a⋅nx=a⋅ny x y Zn a ⋅ ( x - y )a⋅x%n=a⋅y%n n ∣ a ⋅ ( x - y )a⋅(x−y)%n=a⋅x%n−a⋅y%n=0 n∣a⋅(x−y) a ⋅ ( x - y ) n a n ∣ x - y - n < x - y < n x = y a ⋅ n 0 , … , a ⋅ n ( n - 1 ) Z n Z n n 1 b Z n a ⋅ n b = 1n a⋅(x−y) n a n∣x−y −n<x−y<n , kami menyimpulkan bahwa . Ini menunjukkan bahwa produk adalah semua elemen berbeda . Karena memiliki tepat elemen, satu (dan tepat satu) dari produk tersebut harus sama dengan , yaitu, ada unik di sehingga .x=y a⋅n0,…,a⋅n(n−1) Zn Zn n 1 b Zn a⋅nb=1
Sebaliknya memperbaiki dan membiarkan menjadi unsur yang tidak coprime untuk . Dalam hal ini, ada prime sehingga dan . Jika mengaku inverse modulo perkalian (sebut saja ), kita akan memiliki yang , yang berarti bahwa dan, karena itu, , jadi . Sejak , kita ikuti itua Z n n p p ∣ a p ∣ n a n b a ⋅ n b = 1 a ⋅ bn>1 a Zn n p p∣a p∣n a n b a⋅nb=1 ( a ⋅ b - 1 )a⋅b%n=1 n ∣ a ⋅ b - 1 p ∣ a p ∣ a ⋅ b p ∣ n p ∣ a ⋅ b - 1 p ∣ ( a ⋅ b ) - ( a ⋅ b - 1 ) = 1 p(a⋅b−1)%n=a⋅b%n−1=0 n∣a⋅b−1 p∣a p∣a⋅b . Di sisi lain, karena , kami juga mengikuti . Dengan cara ini, , yang bertentangan dengan asumsi bahwa adalah bilangan prima.p∣n p∣a⋅b−1 p∣(a⋅b)−(a⋅b−1)=1 p
Ini membuktikan bahwa pernyataan berikut ini setara ketika .n>1
na dan adalah koprime.n
na menerima modul invers multiplikatif .n
na mengakui modul invers multiplikatif yang unik .n
Bagaimana itu bekerja
Untuk setiap pasangan bilangan bulat dan dalam , bilangan bulat adalah unik; pada kenyataannya, dan adalah hasil bagi dan sisa dari dibagi dengan , yaitu, mengingat , kita dapat memulihkan dan , di mana menunjukkan pembagian integer . Akhirnya, karena dan , adalah elemen ; sebenarnya, .b Z n k : = a ⋅ n + b a b k n k a = k / n b = ka b Zn k:=a⋅n+b a b k n k a=k/n / a ≤ n - 1 b ≤ n - 1 k Z n 2 k ≤ ( n - 1 ) ⋅ n + ( n - 1 ) = n 2 - 1b=k%n / a≤n−1 b≤n−1 k Zn2 k≤(n−1)⋅n+(n−1)=n2−1
Seperti disebutkan di atas, jika dan adalah koprime, akan ada unik sehingga , yaitu, akan ada unik sehingga dan , sehingga daftar yang dihasilkan akan berisi tepat sekali.n b a ⋅ ba n b k k / n = a k / n ⋅ ka⋅b%n=1 k k/n=a ak/n⋅k%n=(k/n)⋅(k%n)%n=1 a
Sebaliknya, jika dan yang tidak coprime, kondisi akan palsu untuk semua nilai sehingga , sehingga daftar yang dihasilkan akan tidak mengandung .n k / n ⋅ ka n k a = k / n ak/n⋅k%n=1 k a=k/n a
Ini membuktikan bahwa daftar yang dikembalikan lambda akan berisi semua coprimes di tepat sekali.Z nn Zn
sumber
Jelly , 4 byte
Cobalah online!
Bagaimana itu bekerja
sumber
gRỊT
ÐṂ
) untuk mendapatkan 3 byte .Mathematica, 25 byte
Format output yang sedikit aneh, di mana setiap hasil dibungkus dalam daftar yang terpisah, misalnya
{{1}, {3}, {7}, {9}}
. Jika tidak, saya punya dua solusi dengan kecepatan 30 byte:Mathematica sebenarnya memiliki
CoprimeQ
tetapi itu terlalu lama.sumber
Q
artinya iniCoprimeQ
?EvenQ
,PrimeQ
atauSubsetQ
.2sable , 4 byte
Kode:
Penjelasan:
Menggunakan pengkodean CP-1252 . Cobalah online!
sumber
Python,
938274 bytef
secara rekursif memeriksa koprimes, dan lambda kedua menghasilkannya. Menghasilkan daftar.sumber
Sebenarnya , 8 byte
Cobalah online!
Penjelasan:
sumber
range(1, n)
jika itu menghemat byte.R
(range(1, n+1)
) danr
(range(n)
). Karena mereka setara, saya memilihR
(karena saya tidak sengaja menekan caps lock saat menulis kode).MATL , 7 byte
Cobalah online!
sumber
MATLAB / Oktaf, 22 byte
Cobalah online!
sumber
JavaScript (ES6),
6461 byteDisimpan 3 byte berkat @ user81655
Cuplikan tes
sumber
a==
dengana<2
?a
mungkin 0 pada titik tertentu. Saya harus memeriksafilter
untuk menghapus kebutuhan untuk menerimab
parameter:...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
Ubur-ubur ,
1918 byteIni bekerja dengan menghitung faktorisasi utama dari setiap angka dalam rentang dan memeriksa apakah itu memotong input (Jellyfish belum memiliki builtin gcd). Untuk alasan bermain golf, hasilnya dalam urutan menurun. Cobalah online!
Penjelasan
Pertama,
i
dievaluasi input; untuk input10
, nilaii
-selnya adalah10
.Di sini
r
(rentang) diterapkan pada input dan 1. Karena input lebih besar dari 1, kisaran berada dalam urutan menurun; untuk input10
, ini memberi[9 8 7 6 5 4 3 2 1]
.Bagian ini adalah satu fungsi besar, yang dievaluasi pada
i
dan rentang di atas.Persimpangan (
n
) dari faktor prima (x
).Apakah ini kosong? (
N
)Utas ke level 0, uji untuk setiap elemen rentang.
Saring (
#
) kisaran sehubungan dengan daftar boolean ini. Fungsi yang dihasilkan oleh[
ingin menggunakan argumen#
sebagai argumennya sendiri, jadi kami menempatkan aB
untuk memblokir#
agar tidak mendapatkan argumen apa pun. Jika tidak, nilai~
-sel akan digunakan sebagai argumen fungsi besar. Akhirnya,p
cetak hasilnya.sumber
Ditumpuk, tidak bersaing,
2421 byteDisimpan 3 byte, terinspirasi oleh ruby Borsunho . (
1 eq
untuk2<
)Coba di sini!
Ini adalah n-lambda yang mengambil argumen tunggal dan menghasilkan array.
sumber
keep
tidak bekerja dengan baik.CJam , 14 byte
Cobalah online!
Penjelasan
Kami tidak perlu memeriksa semua kemungkinan pembagi
a
danb
untuk menguji apakah mereka coprime. Cukuplah untuk melihat apakah ada faktor utamab
pemisaha
.sumber
Mathematica, 26 byte
sumber
Perl 6 , 20 byte
sumber
Brachylog ,
1613 byteIni adalah fungsi yang mengambil N sebagai input, dan menghasilkan semua bilangan bulat kurang dari dan coprime untuk itu.
Cobalah online! Seperti yang sering terjadi di Brachylog, ini memiliki kode tambahan yang ditambahkan untuk membuat fungsi menjadi program penuh; Penerjemah Brachylog, jika diberi fungsi alih-alih program penuh, akan menjalankannya tetapi tidak mencetak hasilnya, yang berarti Anda tidak dapat benar-benar mengamati kerjanya.
Penjelasan:
Program Brachylog adalah rantai kendala; biasanya, LHS dari satu batasan adalah RHS dari yang berikutnya.
Memotong tiga karakter dengan menyadari tidak ada alasan untuk memeriksa untuk melihat apakah faktor umum (yang sudah diketahui sebagai faktor utama dari output) adalah faktor utama dari input. Kita sudah tahu itu prima, jadi kita bisa mengecek apakah itu faktor. Saya terkejut di sini yang
:A*?
tidak mengirim penerjemah ke loop tak terbatas dan tidak mengizinkan nilai non-integer untuk A , tetapi karena penerjemah melakukan apa yang saya inginkan, saya akan menerimanya.sumber
Dyalog APL, 10 byte .
Penjelasan (input
n
):sumber
⍨
Japt
-f
,9852 byteCobalah
sumber
o f_jU
j
juga dapat digunakan untuk menguji apakah 2 angka adalah co-prime.Mathematica, 33 byte
Berisi U + F4A1
sumber
Haskell, 27 byte
Cobalah online!
sumber
Julia 0,5 , 23 byte
Cobalah online!
sumber
meme , 11 byte, tidak bersaing , ketinggalan jaman
Non-bersaing karena iterasi STDIN adalah hal baru. Menggunakan pengkodean UTF-8.
Penjelasan:
}
mengakses item input berikutnya, tetapi input terakhir dilewati saat diberikan, sehingga memasukkan6
akan menghasilkan seperti6 6 6 6 6 ...
di STDIN, sehingga memungkinkan untuk membaca dua output dari satu.sumber
05AB1E , 3 byte
Cobalah online!
Memiliki fitur baru.
sumber
Ruby,
3634Memang, ini bukan jawaban yang sangat terilhami .
2 byte disimpan berkat Conor O'Brien.
sumber
(n)
Python 3 , 60 byte
Impor gcd alih-alih menulis lambda baru untuk itu. Saran golf diterima. Cobalah online!
sumber
Julia, 30 byte
Fungsi anonim.
filter
menghapus elemen dari daftar yang tidak benar berdasarkan suatu fungsi.Dalam hal ini, fungsinya adalah
x->(gcd(n,x)<2)
(true jika gcd dari input dan elemen daftar kurang dari 2). Daftarnya adalah kisaran1:n
.sumber
PARI / GP , 27 byte
Ini menggunakan set-notasi yang diperkenalkan di versi 2.6.0 (2013). Dalam versi sebelumnya, diperlukan empat byte lagi:
akan dibutuhkan.
sumber
[1..n]
), periksa apakah gcd adalah 1 (gcd(n,k)<2
), kembalikan angkanya dengan properti ini. The->
adalah notasi fungsi / penutupan, lebih pendek dengan 2 byte dari sintaks fungsi normal dan[...|...<-...,...]
merupakan notasi set dijelaskan dalam jawaban (lihat bagian 2.3.14 di Pengguna Manual, atau mencari<-
).05AB1E , 4 byte
Cobalah online!
Bagaimana itu bekerja
sumber
C (gcc) , 54 byte
Ini adalah port jawaban Python saya .
Cobalah online!
sumber
Pyth , 5 byte
Cobalah online!
Bagaimana itu bekerja
Perhatikan bahwa Pyth menggunakan pengindeksan 0.
sumber