Hitung fungsi Carmichael

36

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
Lynn
sumber
Apa yang dimaksud secara teoritis di sini? Dapatkah saya berasumsi bahwa input n cocok dengan integer 16-bit? Dapatkah saya berasumsi bahwa n ^ λ (n) cocok dengan dobel?
Dennis
2
Ya dan ya, menurutku. Seperti pada, secara teoritis termasuk berpura - pura jenis asli Anda tepat dan besar (saya pikir itu adalah konsensus, tapi saya tidak yakin).
Lynn

Jawaban:

48

Mathematica, 16 byte

CarmichaelLambda

Baik...

Martin Ender
sumber
38
..... sungguh. ._.
acrolith
12
Saya tidak suka kamu Mathematica
downrep_nation
29

Python, 76 73 67 byte

f=lambda n,k=1:1-any(a**-~k*~-a**k%n for a in range(n))or-~f(n,k+1)

Cobalah 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.

f=lambda n,k=1,a=1:a/n or(a**-~k*~-a**k%n<1)*f(n,k,a+1)or-~f(n,k+1)

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 .

f=lambda n,k=1,a=1:a/n or~-a**k*a**-~k%n<1==f(n,k,a+1)or-~f(n,k+1)

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 anymengembalikan 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) .

Dennis
sumber
Anda dapat menyimpan setidaknya 4 dengan rekursi alih-alih pemahaman daftar: 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).
feersum
1
Terima kasih! Sementara itu, saya menemukan peningkatan pada algoritma saya yang tampaknya meniadakan manfaat pengulangan alih-alih menggunakan pemahaman daftar.
Dennis
14

Mathematica tanpa built-in, 58 57 byte

Terima 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:

LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&

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.

Greg Martin
sumber
Anda dapat menggunakan EulerPhiuntuk mendapatkan LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&57 byte.
mil
@miles terlihat dengan baik! Saya menghitung 56 byte, dapatkah Anda memeriksa?
Greg Martin
Ya, itu 57 byte .
miles
jelas saya bahkan mencoba golf menghitung saya ....: /
Greg Martin
12

Template Dianggap Berbahaya , 246 byte

Fun<Ap<Fun<If<Eq<A<2>,T>,A<1>,And<Eq<Ap<Fun<If<A<1>,Ap<A<0>,Rem<A<2>,A<1>>,A<1>>,A<2>>>,A<1,1>,A<2>>,T>,Sub<Ap<Fun<Rem<If<A<1>,Mul<A<2,1>,Ap<A<0>,Sub<A<1>,T>>>,T>,A<1,2>>>,A<1>>,T>>,Ap<A<0>,Add<A<1>,T>,A<1,1>>,Ap<A<0>,A<1>,Sub<A<2>,T>>>>,T,A<1>>>

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).

feersum
sumber
10

Haskell, 57 56 byte

f n=[k|k<-[1..],and[mod(m^k)n<2|m<-[1..n],gcd m n<2]]!!0
dianne
sumber
8

Jelly, 2 byte

Æc

Terima kasih untuk bawaannya, @ Lynn

dianne
sumber
31
............. ._
Maltysen
10
Saya tidak pernah mengerti titik penerapan built-in yang sangat spesifik.
Fatalkan
31
Ini hampir merupakan tambahan bahasa yang khusus dibuat untuk tantangan ini. Komit oleh Lynn 2 hari lalu, tantangan oleh @Lynn hari ini
edc65
5
@ edc65 Belum lagi built-in ini tidak berguna di luar tantangan ini dan turunannya.
Fatalkan
3
Nah, fungsi Carmichael penting dalam teori bilangan (seperti tercermin pada jawaban teratas saat ini), jadi saya tidak akan menyebutnya tidak berguna.
Greg Martin
6

Pyth - 19 18 17 bytes

Satu byte disimpan berkat @TheBikingViking.

Lurus brute force.

f!sm*t.^dTQq1iQdQ

Cobalah online di sini .

Maltysen
sumber
f!smtlebih pendek satu byte.
TheBikingViking
@TheBikingViking oh, ya terima kasih
Maltysen
Sakit mataku, bagaimana sih ini python ..? Meskipun begitu menyukainya haha ​​:)
Yohan Obadia
6

Rubi, 59 56 byte

->x{a=1..x
a.detect{|k|a.all?{|y|x.gcd(y)>1||y**k%x<2}}}
m-chrzan
sumber
5

J, 28 27 byte

[:*./@(5&p:%2^0=8&|)2^/@p:]

Fungsi 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 2p 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.

   f =: [:*./@(5&p:%2^0=8&|)2^/@p:]
   f 530
52
   (,.f"0) 1 2 3 10 35 101 530 3010 6511 10000
    1    1
    2    1
    3    2
   10    4
   35   12
  101  100
  530   52
 3010   84
 6511 3056
10000  500

Penjelasan

[:*./@(5&p:%2^0=8&|)2^/@p:]  Input: integer n
                          ]  Identity function, get n
                    2   p:   Get a table of prime/exponent values for n
                     ^/@     Raise each prime to its exponent to get the prime powers of n
[:    (            )         Operate on the prime powers
                8&|            Take each modulo 8
              0=               Test if its equal to 0, 1 if true else 0
            2^                 Raise 2 to the power of each
       5&p:                    Apply the totient function to each prime power
           %                   Divide it by the powers of 2
  *./@                       Reduce using LCM and return
mil
sumber
Ini memberikan jawaban yang salah untuk 10.000 (1000 bukannya 500 yang benar), dan memang untuk setiap kelipatan 8. 2 adalah prima yang aneh, dan λ (2 ^ a) = 2 ^ {a-2} (bukan 2 ^ { a-1}) saat a≥3.
Greg Martin
Terima kasih telah menangkap itu, sepertinya saya bahkan tidak bisa membaca hasil
mil
kadang-kadang Anda tidak sendirian .... :)
Greg Martin
5

Sebenarnya, 30 28 25 19 26 byte

Fungsi Carmichael, di λ(n)mana n = p_0**k_0 * p_1**k_1 * ... * p_a**k_a, didefinisikan sebagai kelipatan terkecil (LCM) λ(p_i**k_i)untuk kekuatan prima maksimal p_i**k_iyang membaginya n. Mengingat bahwa untuk setiap kekuatan utama kecuali di mana prime adalah 2, fungsi Carmichael setara dengan fungsi totient Euler λ(n) == φ(n), kami menggunakan φ(n)sebagai gantinya. Untuk kasus khusus di 2**kmana k ≥ 3, kami hanya memeriksa apakah 2**3 = 8membagi menjadi npada 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!

;7&Yu@\w`iⁿ▒`M╗2`╜@♀%ΣY`╓N

Tidak melakukanolf

         Implicit input n.
;        Duplicate n.
7&       n&7 == n%8.
Yu       Logical NOT and increment. If n%8 == 0, return 2. Else, return 1.
@\       Integer divide n by 2 if n%8==0, by 1 otherwise.
          Thus, we have dealt with the special case where p_i == 2 and e_i >= 3.
w        Full prime factorization of n as a list of [prime, exponent] lists.
`...`M   Map the following function over the prime factorization.
  i        Flatten the array, pushing exponent, then prime to the stack.
  ⁿ▒       totient(pow(prime, exponent)).
╗        Save that list of totients in register 0.
2`...`╓  Get the first two values of n where the following function f(n) is truthy.
         Those two numbers will be 0 and our LCM.
  ╜@       Push the list in register 0 and swap with our n.
  ♀%       Get n mod (every number in the list)
  Σ        Sum the modulos. This sum will be 0, if and only if this number is 0 or LCM.
  Y        Logical NOT, so that we only get a truthy if the sum of modulos is 0.
N        Grab the second number, our LCM. Implicit return.
Sherlock9
sumber
2
Sebenarnya, saya tidak tahu bagaimana Anda melakukan ini hanya dalam 19 byte.
Buffer Over Read
@TheBitByte Dengan penggunaan totientdan gcdbawaan. Ini akan lebih pendek jika Sebenarnya lcmsecara langsung, tapi saya tidak keberatan begitu banyak dan itu hanya akan mematikan paling banyak 4 byte.
Sherlock9
1
Pernyataan bahwa lcm (* a) = produk (* a) / gcd (* a) benar ketika * a adalah daftar persis dua angka; Namun, secara umum salah untuk daftar yang lebih panjang (contoh: jika * a adalah {6,10,15}, itu memberikan 900 bukannya jawaban yang benar dari 60). [Dalam hal ini, itu salah adalah * a adalah daftar satu nomor juga!] Dan Anda dapat memeriksa bahwa Anda mendapatkan jawaban yang salah untuk lebih dari setengah kasus uji yang tercantum dalam OP.
Greg Martin
@GregMartin Terima kasih atas bantuannya. Tetap.
Sherlock9
4

JavaScript (ES6), 143 135 byte

Sunting: disimpan 8 byte berkat Neil

Implementasi menggunakan pemrograman fungsional.

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

Tidak diikat dan dikomentari

n =>                                          // Given a positive integer n:
  (A = [...Array(n).keys()])                  // Build A = [0 ... n-1].
  .find(k =>                                  // Try to find k in [1 ... n-1] such as
    k && !c.some(c =>                         // for each coprime c: c^k ≡ 1 (mod n).
      A.slice(0, k).reduce(y =>               // We use reduce() to compute
        y * c % n, 1                          // c^k mod n.
      ) - 1                                   // Compare it with 1.
    ),                                        // The list of coprimes is precomputed
    c = A.filter(x =>                         // before the find() loop is executed:
      (                                       // for each x in [0 ... n-1], keep
        g = (x, y) => x ? g(y % x, x) : y     // only integers that verify:
      )(x, n) == 1                            // gcd(x, n) = 1
    )                                         // (computed recursively)
  ) || 1                                      // Default result is 1 (for n = 1)

Demo

Meskipun itu bekerja untuk 6511dan 10000, saya tidak akan memasukkan mereka di sini karena cenderung agak lambat.

let f =
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

console.log(f(1));     // 1
console.log(f(2));     // 1
console.log(f(3));     // 2
console.log(f(10));    // 4
console.log(f(35));    // 12
console.log(f(101));   // 100
console.log(f(530));   // 52
console.log(f(3010));  // 84

Arnauld
sumber
1
JS dapat melakukan 0..n-1rentang 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
Neil
2

Ruby, 101 86 91 90 byte

Port Ruby jawaban saya Sebenarnya . Saran golf diterima.

Edit: -4 byte dari menghapus atetapi +9 byte dari memperbaiki bug di mana 1dikembalikan nil. -1 byte terima kasih kepada Cyoce.

require'prime'
->n{((n%8<1?n/2:n).prime_division<<[2,1]).map{|x,y|x**~-y*~-x}.reduce :lcm}

Tidak melakukanolf

require 'prime'
def carmichael(n)
  if n%8 < 1
    n /= 2
  end
  a = []
  n.prime_division.do each |x,y|
    a << x**(y-1)*(x-1)
  end
  return a.reduce :lcm
end
Sherlock9
sumber
Anda tidak perlu a=. Sayangnya, Anda kembali niluntuk n = 1 :(. (n.prime_division<<[2,1])Memperbaikinya. Tidak yakin apakah ada cara golf.
m-chrzan
(n%8<1?n/2:n).prime_division...menyimpan 2 byte lagi.
m-chrzan
@ m-chrzan aadalah sisa dari upaya golf sebelumnya. Terima kasih atas pengingat tentang adan untuk kepala di atas 1.
Sherlock9
Anda dapat menyimpan byte dengan menggunakan .reduce :lcmalih-alih .reduce(:lcm).
Cyoce
1

JavaScript (ES 2016) 149

Implementasi referensi Python porting ke JS. Beberapa builtin Pyhton yang mewah hilang dalam js, like gcddan pow, dan pemahaman array tidak standar dalam ES 6. Ini berfungsi di Firefox.

n=>eval('for(g=(a,b)=>b?g(b,a%b):a,p=(a,b,c)=>eval("for(r=1;b--;)r=r*a%c"),c=[for(_ of Array(i=n))if(g(i--,n)<2)i+1],k=1;c.some(x=>p(x,k,n)-1);)++k')

Kurang golf

n=>{
  g=(a,b)=>b?g(b,a%b):a
  p=(a,b,c)=>{ 
    for(r=1;b--;)
      r=r*a%c
    return r
  }
  c=[for(_ of Array(i=n)) if(g(i--,n)<2) i+1]
  for(k=1;c.some(x=>p(x,k,n)-1);)
    ++k
  return k
} 
edc65
sumber
modpow rekursif lebih pendek:p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Olivier Grégoire
1

Jawa, 209 207 202 194 192 byte

Kode (96 byte):

n->{for(int x,k=1,a;;k++){for(a=1,x=0;++x<=n&&a<2;)a=g(x,n)<2?p(x,k,n):1;if(a<2||n<2)return k;}}

fungsi tambahan (96 byte):

int g(int a,int b){return b<1?a:g(b,a%b);}int p(int n,int p,int m){return p<2?n:n*p(n,p-1,m)%m;}

Menguji & ungolfed

import java.util.Arrays;
import java.util.function.IntUnaryOperator;

public class Main2 {

  static int g(int a,int b) { // recursive gcd
    return b < 1
        ? a
        : g(b,a%b);
  }

  static int p(int n, int p, int m) { // recursive modpow
    return p < 2
      ? n
      : n * p(n, p - 1, m) % m;
  }

  public static void main(String[] args) {

    IntUnaryOperator f = n -> {
      for(int x,k=1,a;;k++) { // for each k
        for(a=1,x=0;++x<=n&&a<2;) // for each x
          a=g(x,n)<2?p(x,k,n):1; // compute modpow(x,k,n) if g(x,n)
        if(a<2||n<2) // if all modpow(x,k,n)=1. Also check for weird result for n=1.
          return k;
      }
    };

    Arrays.stream(new int[]{1, 2, 3, 10, 35, 101, 530, 3010, 6511, 10000})
        .map(f)
        .forEach(System.out::println);
  }
}

Catatan

  • penggunaan amenjadi intlebih pendek daripada jika saya harus menggunakan booleanuntuk melakukan tes saya.
  • Ya, ini lebih pendek untuk valueOfsemua yang baru BigIntegerdaripada membuat fungsi yang terpisah (ada 5, ditambah ONEkonstanta adalah freebie).
  • Algoritma berbeda dari algoritma @Master_ex ', jadi ini bukan hanya repost golf. Juga, algoritma ini jauh lebih efisien karena gcddihitung berulang-ulang untuk nilai yang sama.

Bercukur

  1. 209 -> 207 byte:
    • if(...)a=...; -> a=...?...:1;
    • a==1 -> a<2
  2. 207 -> 202 byte
    • Got menyingkirkan BigIntegeroleh golf gcddan modPowuntuk int.
  3. 202 -> 194 byte
    • perulangan modPow-> rekursif
  4. 194 -> 192 byte
    • ==1-> <2(tampaknya berfungsi untuk semua kasus uji, tidak tahu nomor lainnya.)
Olivier Grégoire
sumber
Hei! Saya perhatikan bahwa outputnya tidak seperti yang diharapkan. Lihat pertanyaan untuk hasil yang diharapkan. Secara pribadi, saya sering menulis tes unit sebelum mulai bermain golf kode saya, itu membantu! Saya kira masalahnya bisa jadi modPow pada bilangan bulat, saya juga punya masalah ini dan itulah sebabnya saya menggunakan BigInteger pada akhirnya.
Master_ex
Hmmm ... Saya terkejut, saya membiarkan tes saya berjalan di setiap perubahan. Saya akan memeriksa apa yang salah.
Olivier Grégoire
1
@ Master_ex saya memperbaikinya. Kembali ke versi sebelumnya tidak masalah.
Olivier Grégoire
Saya menemukan metode modpow rekursif Anda pcukup 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 ke BigInteger(yaitu Math.pow(3, 100)%101kembali 60.0bukan 1). Implementasi Anda kebal terhadap ini karena ia melakukan mod di setiap iterasi. Namun, masih ada bug. Untuk yang besar m pmungkin masih mengembalikan hasil yang salah. Juga, karena rekursi, StackOverflowErrordapat dengan mudah terjadi untuk input besar dengan ukuran stack standar.
Master_ex
@Master_ex Ya, itu konsekuensi dari pembatasan intjenis. 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. StackOverflowErrordapat 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.
Olivier Grégoire
1

Java8 38 19 + 287 295 253 248 241 = 325 333 272 267 260 byte

BigInteger B(int i){return new BigInteger(""+i);}int c(int...k){int n=k[0];for(k[0]=1;n>1&!java.util.stream.IntStream.range(0,n).filter(i->B(n).gcd(B(i)).equals(B(1))).allMatch(x->B(x).modPow(B(k[0]),B(n)).equals(B(1)));k[0]++);return k[0];}

Impor, 19 byte

import java.math.*;

Penjelasan

Ini adalah implementasi lurus ke depan. Co-bilangan prima dihitung dalam Set pdan setiap kekuatan k digunakan untuk memeriksa apakah itu sama dengan 1 modul.

Saya harus menggunakan BigIntegerkarena masalah presisi.

Pemakaian

public static void main(String[] args) {
    Carmichael c = new Carmichael();
    System.out.println(c.c(3)); // prints 2
}

Tidak disatukan

// returns the BigInteger representation of the given interger
BigInteger B(int i) {
    return new BigInteger(""+i);
}
// for a given integer it returns the result of the carmichael function again as interger
// so the return value cannot be larger
int c(int... k) {
    int n = k[0];
    // iterate k[0] until for all co-primes this is true: (x^n) mod n == 1, if n==1 skip the loop
    for (k[0]=1;n > 1 && !java.util.stream.IntStream.range(0, n)
                .filter(i -> B(n).gcd(B(i)).equals(B(1)))
                .allMatch(x -> B((int) x).modPow(B(k[0]), B(n)).equals(B(1)));k[0]++);
    return k[0];
}

Ada saran untuk bermain golf lebih lanjut :-)

Memperbarui

  • Tidak ada elemen di luar fungsi yang menjaga status
  • Mengikuti saran Olivier Grégoire dan menyelamatkan 1 byte dari B()
  • Dihapus k()metode dan p(co-primes) Set.
  • Dihapus casting tidak diperlukan untuk int.
  • Menambahkan varag dan digunakan untuk sementara.
Master_ex
sumber
Bisakah Anda memiliki versi tanpa serigala (dengan linebreak, komentar di sana-sini, dll.)
OldBunny2800
@ OldBunny2800: Ya, tentu. Namun, saya akan melakukannya hari ini karena sekarang saya sibuk!
Master_ex
@ OldBunny2800: Saya menambahkan versi ungolfed :-)
Master_ex
Hmmm ... Saya tidak yakin apakah ini diperhitungkan karena itu bukan fungsi atau program. Jika itu sebuah fungsi, ada elemen di luarnya yang mempertahankan status, menjadikannya metode de facto (fungsi adalah input murni-> output tanpa status eksternal), jika itu sebuah program, seluruh metode utama tidak ada. Jika interpretasi saya salah, tolong beri tahu saya! Saya pikir lebih baik untuk memasukkannya k(int)dalam satu lingkaran karena ini adalah satu-liner dan dapat dilakukan. Plus, konstanta O dapat dimasukkan ke dalam cmetode juga. Saya kira Anda akan memenangkan byte dengan melakukannya!
Olivier Grégoire
Secara konkret, 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 menggunakan Odua kali, ganti dengan B(1)mencukur byte.
Olivier Grégoire
1

Java, 165 163 158 152 143 byte

int l(int n){int k=1,x,a,b,t,d=1;for(;d>0;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;b>0;b=a%b,a=t)t=b;for(t=b=1;b++<=k;t=t*x%n);}return k;}

Port lain dari implementasi C saya .

Cobalah di Ideone

plafon
sumber
1

C ++, 208 200 149 144 140 134 byte

[](int n){int k=1,x,a,b,t,d=1;for(;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;};

Port saya implementasi C .

Cobalah di Ideone

plafon
sumber
0

Racket 218 byte

(λ(n)(let((fl #f)(cl(for/list((i n) #:when(coprime? n i))i)))(for/sum((k(range 1 n))#:break fl)(set! fl #t)
(for((i(length cl))#:break(not fl))(when(not(= 1(modulo(expt(list-ref cl i)k)n)))(set! fl #f)))(if fl k 0))))

Versi tidak disatukan:

(require math)
(define f
  (λ(n)
    (let ((fl #f)
          (cl (for/list ((i n) #:when (coprime? n i))
                i)))
             (for/sum ((k (range 1 n)) #:break fl)
               (set! fl #t)
               (for ((i (length cl)) #:break (not fl))
                 (when (not (= 1 (modulo (expt (list-ref cl i) k) n)))
                   (set! fl #f)))
               (if fl k 0)))))

Pengujian:

(f 2) 
(f 3)
(f 10)
(f 35)
(f 101)
(f 530)
(f 3010)
(f 6511)
(f 10000)

Keluaran:

1
2
4
12
100
52
84
3056
500
juga
sumber
0

C, 278 276 272 265 256 243 140 134 125 byte

k,x,a,b,t,d;l(n){for(k=d=1;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;}

Ini menggunakan algoritma eksponensial modular lambat, menghitung GCD terlalu sering dan tidak ada lagi kebocoran memori!

Tidak Disatukan:

int gcd( int a, int b ) {
  int t;
  while( b ) {
    t = b;
    b = a%b;
    a = t;
  }
  return a;
}
int pw(int a,int b,int c){
  int t=1;
  for( int e=0; e<b; e++ ) {
    t=(t*a)%c;
  }
  return t;
}
int carmichael(int n) {
  int k = 1;
  for( ;; ) {
    int done = 1;
    for( int x=1; x<n; x++ ) {
      if( gcd(x,n)==1 && pw(x,k,n) != 1 ) {
        done = 0;
        k++;
      }
    }
    if( done ) break;
  }
  return k;
}

Cobalah di Ideone

plafon
sumber
0

Aksioma 129 byte

c(n)==(r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1);repeat(for a in r repeat(v:=powmod(a,k,n);v~=1=>break);v<=1=>break;k:=k+1);k)

kurang golf

cml(n)==
 r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1)
 repeat 
   for a in r repeat(v:=powmod(a,k,n);v~=1=>break)
   v<=1=>break
   k:=k+1
 k

hasil

(3) -> [i,c(i)] for i in [1,2,3,10,35,101,530,3010,6511,10000]
   Compiling function c with type PositiveInteger -> PositiveInteger

   (3)
   [[1,1], [2,1], [3,2], [10,4], [35,12], [101,100], [530,52], [3010,84],
    [6511,3056], [10000,500]]
                                             Type: Tuple List PositiveInteger
RosLuP
sumber