Deskripsi tugas
Dalam teori bilangan, fungsi Carmichael λ mengambil bilangan bulat positif n dan mengembalikan bilangan bulat paling kecil k sehingga kekuatan k -th dari masing-masing bilangan bulat koprime ke n sama dengan 1 modulo n .
Dengan bilangan bulat positif n , solusi Anda harus menghitung λ (n) . Kode terpendek dalam byte menang.
Program Anda secara teoritis seharusnya bekerja untuk input yang besar dan sewenang-wenang, tetapi tidak perlu efisien.
Kiat
Urutan semua λ (n) adalah OEIS A002322 .
Implementasi Python ungolfed akan terlihat seperti
from fractions import gcd
def carmichael(n):
coprimes = [x for x in range(1, n) if gcd(x, n) == 1]
k = 1
while not all(pow(x, k, n) == 1 for x in coprimes):
k += 1
return k
(Dengan Python, pow(A, B, C)
komputasi secara efisien pow(A, B) % C
.)
Uji kasus
Input Output
1 1
2 1
3 2
10 4
35 12
101 100
530 52
3010 84
6511 3056
10000 500
Jawaban:
Mathematica, 16 byte
Baik...
sumber
Python,
767367 byteCobalah online!
Byte lebih lanjut dapat disimpan dengan mengembalikan True, bukan 1 .
Implementasi alternatif
Menggunakan pendekatan yang sama, ada juga implementasi berikut oleh @feersum yang tidak menggunakan pemahaman daftar.
Perhatikan bahwa implementasi ini membutuhkan waktu O (n λ (n) ) . Efisiensi dapat ditingkatkan secara dramatis sementara sebenarnya menurunkan skor menjadi 66 byte , tetapi fungsi tersebut akan mengembalikan True untuk input 2 .
Latar Belakang
Definisi dan notasi
Semua variabel yang dipekerjakan akan menunjukkan bilangan bulat; n , k , dan α akan menunjukkan bilangan bulat positif ; dan p akan menunjukkan prima positif .
a | b jika b dapat dibagi dengan a , yaitu, jika ada q sehingga b = qa .
a ≡ b ( mod m) jika a dan b memiliki sama residu modulo m , yaitu, jika m | a - b .
λ (n) adalah k terkecil sehingga a k ≡ 1 ( mod n) - yaitu, sedemikian sehingga n | a k - 1 - untuk semua a yang merupakan koprime ke n .
f (n) adalah yang terkecil k sehingga sebuah 2k + 1 ≡ a k + 1 ( mod n) - yaitu, sehingga n | a k + 1 (a k - 1) - untuk semua a .
λ (n) ≤ f (n)
Fix n dan membiarkan sebuah coprime be ke n .
Dengan definisi f , n | a f (n) +1 (a f (n) - 1) . Karena a dan n tidak memiliki faktor prima yang sama, maka juga tidak ada f (n) +1 dan n , yang menyiratkan bahwa n | a f (n) - 1 .
Karena λ (n) adalah bilangan bulat terkecil k sehingga n | a k - 1 untuk semua bilangan bulat a yang merupakan koprime ke n , berarti λ (n) ≤ f (n) .
λ (n) = f (n)
Karena kita telah menetapkan ketimpangan λ (n) ≤ f (n) , cukup untuk memverifikasi bahwa k = λ (n) memenuhi kondisi yang mendefinisikan f , yaitu, bahwa n | a λ (n) +1 (a λ (n) - 1) untuk semua a . Untuk tujuan ini, kami akan menetapkan p α | a λ (n) +1 (a λ (n) - 1) setiap kali p α | n .
λ (k) | λ (n) setiap kali k | n ( sumber ), jadi (a λ (k) - 1) (a λ (n) -λ (k) + a λ (n) -2λ (k) + ⋯ + a λ (k) + 1) = a λ (n) - 1 dan, karenanya, a λ (k) - 1 | a λ (n) - 1 | a λ (n) +1 (a λ (n) - 1) .
Jika a dan p α adalah koprime, dengan definisi λ dan yang di atas, p α | a λ (p α ) - 1 | a λ (n) +1 (a λ (n) - 1) mengikuti, seperti yang diinginkan.
Jika a = 0 , maka suatu λ (n) 1 (a λ (n) - 1) = 0 , yang habis dibagi semua bilangan bulat.
Akhirnya, kita harus mempertimbangkan kasus di mana a dan p α memiliki faktor prima yang sama. Karena p adalah prima, ini menyiratkan bahwa p | a . Teorema Carmichael menyatakan bahwa λ (p α ) = (p - 1) p α - 1 jika p> 2 atau α <3 dan λ (p α ) = p α - 2 sebaliknya. Dalam semua kasus, λ (p α ) ≥ p α - 2 ≥ 2 α - 2 > α - 2 .
Karenanya, λ (n) + 1 ≥ λ (p α ) + 1> α - 1 , jadi λ (n) + 1 ≥ α dan p α | p λ (n) +1 | a λ (n) +1 | a λ (n) +1 (a λ (n) - 1) . Ini melengkapi buktinya.
Bagaimana itu bekerja
Sementara definisi f (n) dan λ (n) mempertimbangkan semua nilai yang mungkin dari a , cukup untuk menguji mereka yang terletak pada [0, ..., n - 1] .
Ketika f (n, k) disebut, itu menghitung sebuah k + 1 (a k - 1)% n untuk semua nilai yang di kisaran itu, yang 0 jika dan hanya jika n | a k + 1 (a k - 1) .
Jika semua residu yang dihitung adalah nol, k = λ (n) dan
any
mengembalikan False , jadi f (n, k) mengembalikan 1 .Di sisi lain, sementara k <λ (n) ,
1-any(...)
akan mengembalikan 0 , sehingga f disebut secara rekursif dengan nilai k yang meningkat . Yang terkemuka-~
menambahkan nilai kembali dari f (n, k + 1) , jadi kami menambahkan 1 ke f (n, λ (n)) = 1 satu kali untuk setiap bilangan bulat dalam [1, ..., λ (n) - 1 ] . Hasil akhirnya adalah λ (n) .sumber
f=lambda n,k=1,a=1:a/n or(a**k*~-a**k%n<1)*f(n,k,a+2-n%2)or-~f(n,k+1)
(Tambahkan kembali satu byte jika Anda tidak suka untuk mengambil n ** λ (n) waktu).Mathematica tanpa built-in,
5857 byteTerima kasih kepada Martin Ender karena menemukan kesalahan, lalu selamatkan saya byte yang diperlukan untuk memperbaikinya!
Terima kasih kepada miles untuk menghemat 1 byte! (yang sepertinya 2 bagi saya)
Built-in benar-benar baik-baik saja ... tetapi bagi mereka yang ingin menerapkannya tanpa menggunakan brute force, berikut ini rumus untuk fungsi Carmichael:
Jika p adalah bilangan prima, fungsi Carmichael λ (p ^ r) sama dengan φ (p ^ r) = (p-1) * p ^ (r-1) - kecuali ketika p = 2 dan r≥3, dalam hal ini setengahnya, yaitu 2 ^ (r-2).
Dan jika faktorisasi daya utama dari n sama dengan p1 ^ r1 * p2 ^ r2 * ..., maka λ (n) sama dengan kelipatan paling umum dari {λ (p1 ^ r1), λ (p2 ^ r2), .. .}.
Runtime adalah satu instan lebih dari memfaktorkan integer di tempat pertama.
sumber
EulerPhi
untuk mendapatkanLCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&
57 byte.Template Dianggap Berbahaya , 246 byte
Fungsi yang tidak disebutkan namanya (tidak ada yang namanya fungsi).
Ini adalah esolang saya yang terlupakan yang ditafsirkan oleh template instantiating kompiler C ++. Dengan kedalaman maksimum templat maks
g++
, ia dapat melakukan λ (35), tetapi tidak dapat melakukannya λ (101) (evaluasi malas membuat segalanya menjadi lebih buruk).sumber
Haskell,
5756 bytesumber
Jelly, 2 byte
Terima kasih untuk bawaannya, @ Lynn
sumber
Pyth -
191817 bytesSatu byte disimpan berkat @TheBikingViking.
Lurus brute force.
Cobalah online di sini .
sumber
f!smt
lebih pendek satu byte.Rubi,
5956 bytesumber
J,
2827 byteFungsi Carmichael adalah λ ( n ) dan fungsi totient adalah φ ( n ).
Menggunakan definisi di mana λ ( p k ) = φ ( p k ) / 2 jika p = 2 dan k > 2 yang lain φ ( p k ). Kemudian, untuk umum n = p 1 k 1 p 2 k 2 ⋯ p i k i , λ ( n ) = LCM [λ ( p 1 k 1 ) λ ( p 2 k 2 ) ⋯ λ ( p i k i )] .
Pemakaian
Perintah tambahan digunakan untuk memformat beberapa input / output.
Penjelasan
sumber
Sebenarnya,
3028251926 byteFungsi Carmichael, di
λ(n)
manan = p_0**k_0 * p_1**k_1 * ... * p_a**k_a
, didefinisikan sebagai kelipatan terkecil (LCM)λ(p_i**k_i)
untuk kekuatan prima maksimalp_i**k_i
yang membaginyan
. Mengingat bahwa untuk setiap kekuatan utama kecuali di mana prime adalah2
, fungsi Carmichael setara dengan fungsi totient Eulerλ(n) == φ(n)
, kami menggunakanφ(n)
sebagai gantinya. Untuk kasus khusus di2**k
manak ≥ 3
, kami hanya memeriksa apakah2**3 = 8
membagi menjadin
pada awal program, dan membaginya dengan 2 jika ada.Sayangnya, Sebenarnya saat ini tidak memiliki built-in LCM, jadi saya membuat LCM yang kasar. Saran golf diterima. Cobalah online!
Tidak melakukanolf
sumber
totient
dangcd
bawaan. Ini akan lebih pendek jika Sebenarnyalcm
secara langsung, tapi saya tidak keberatan begitu banyak dan itu hanya akan mematikan paling banyak 4 byte.JavaScript (ES6),
143135 byteSunting: disimpan 8 byte berkat Neil
Implementasi menggunakan pemrograman fungsional.
Tidak diikat dan dikomentari
Demo
Meskipun itu bekerja untuk
6511
dan10000
, saya tidak akan memasukkan mereka di sini karena cenderung agak lambat.sumber
0..n-1
rentang cukup mudah:[...Array(n).keys()]
. Ini tidak membutuhkan satu tetapi dua kasus khusus tapi saya masih di depan:n=>(a=[...Array(n).keys()]).find(k=>k&&!c.some(c=>a.slice(0,k).reduce(y=>y*c%n,1)-1),c=a.filter(x=>(g=(x,y)=>x?g(y%x,x):y)(x,n)==1))||1
Ruby,
101869190 bytePort Ruby jawaban saya Sebenarnya . Saran golf diterima.
Edit: -4 byte dari menghapus
a
tetapi +9 byte dari memperbaiki bug di mana1
dikembalikannil
. -1 byte terima kasih kepada Cyoce.Tidak melakukanolf
sumber
a=
. Sayangnya, Anda kembalinil
untuk n = 1 :(.(n.prime_division<<[2,1])
Memperbaikinya. Tidak yakin apakah ada cara golf.(n%8<1?n/2:n).prime_division...
menyimpan 2 byte lagi.a
adalah sisa dari upaya golf sebelumnya. Terima kasih atas pengingat tentanga
dan untuk kepala di atas1
..reduce :lcm
alih-alih.reduce(:lcm)
.JavaScript (ES 2016) 149
Implementasi referensi Python porting ke JS. Beberapa builtin Pyhton yang mewah hilang dalam js, like
gcd
danpow
, dan pemahaman array tidak standar dalam ES 6. Ini berfungsi di Firefox.Kurang golf
sumber
p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Jawa,
209207202194192 byteKode (96 byte):
fungsi tambahan (96 byte):
Menguji & ungolfed
Catatan
a
menjadiint
lebih pendek daripada jika saya harus menggunakanboolean
untuk melakukan tes saya.valueOf
semua yang baruBigInteger
daripada membuat fungsi yang terpisah (ada 5, ditambahONE
konstanta adalah freebie).gcd
dihitung berulang-ulang untuk nilai yang sama.Bercukur
if(...)a=...;
->a=...?...:1;
a==1
->a<2
BigInteger
oleh golfgcd
danmodPow
untukint
.modPow
-> rekursif==1
-><2
(tampaknya berfungsi untuk semua kasus uji, tidak tahu nomor lainnya.)sumber
p
cukup pintar. Saya mencoba menggunakan integer hanya pada awalnya juga, tetapi seperti yang saya sebutkan dalam jawaban saya, saya punya masalah presisi dan itulah sebabnya saya pindah keBigInteger
(yaituMath.pow(3, 100)%101
kembali60.0
bukan1
). Implementasi Anda kebal terhadap ini karena ia melakukan mod di setiap iterasi. Namun, masih ada bug. Untuk yang besarm
p
mungkin masih mengembalikan hasil yang salah. Juga, karena rekursi,StackOverflowError
dapat dengan mudah terjadi untuk input besar dengan ukuran stack standar.int
jenis. Saya bisa menggunakan long alih-alih int, itu akan menjadi 8 byte tambahan. Tapi dalam pandangan saya, semua test case sah jadi saya biarkan begitu saja.StackOverflowError
dapat terjadi, tetapi itulah cara kerja rekursif. Ada metode untuk membatasi hingga 32 tumpukan, tetapi ini menggunakan lebih banyak byte. Implementasi ini rapuh, ya, Anda sepenuhnya benar. Tapi itu cukup kuat untuk kasus uji.Java8
3819 +287295253248241 =325333272267260 byteImpor, 19 byte
Penjelasan
Ini adalah implementasi lurus ke depan. Co-bilangan prima dihitung dalam
Set p
dan setiap kekuatan k digunakan untuk memeriksa apakah itu sama dengan 1 modul.Saya harus menggunakan
BigInteger
karena masalah presisi.Pemakaian
Tidak disatukan
Ada saran untuk bermain golf lebih lanjut :-)
Memperbarui
B()
k()
metode danp
(co-primes) Set.sumber
k(int)
dalam satu lingkaran karena ini adalah satu-liner dan dapat dilakukan. Plus, konstanta O dapat dimasukkan ke dalamc
metode juga. Saya kira Anda akan memenangkan byte dengan melakukannya!while(n>1&&!p.stream().allMatch(x->B((int)x).modPow(B(k), B(n)).equals(O)))
mencukur byte dan memperbaiki masalah yang saya sebutkan jika Anda meletakkan himpunan dan konstanta kembali ke metode. Juga, Anda menggunakanO
dua kali, ganti denganB(1)
mencukur byte.Java,
165 163 158 152143 bytePort lain dari implementasi C saya .
Cobalah di Ideone
sumber
C ++,
208 200 149 144 140134 bytePort saya implementasi C .
Cobalah di Ideone
sumber
Racket 218 byte
Versi tidak disatukan:
Pengujian:
Keluaran:
sumber
C,
278 276 272 265 256 243 140 134125 byteIni menggunakan algoritma eksponensial modular lambat, menghitung GCD terlalu sering dan tidak ada lagi kebocoran memori!
Tidak Disatukan:
Cobalah di Ideone
sumber
Aksioma 129 byte
kurang golf
hasil
sumber