Calcular a função Carmichael

36

Descrição da tarefa

Na teoria dos números, a função Carmichael  λ pega um número inteiro positivo  n e retorna o número inteiro menos positivo k, de modo que a k -ésima potência de cada número inteiro coprime para n seja igual a 1 módulo n .

Dado um número inteiro positivo n , sua solução deve calcular λ (n) . O código mais curto em bytes vence.

Teoricamente, seu programa deve funcionar com entradas arbitrariamente grandes, mas não precisa ser eficiente.

Dicas

A sequência de todos os λ (n) é OEIS A002322 .

Uma implementação Python não-gasta pareceria

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

(Em Python, pow(A, B, C)calcula com eficiência pow(A, B) % C.)

Casos de teste

Input    Output
1        1
2        1
3        2
10       4
35       12
101      100
530      52
3010     84
6511     3056
10000    500
Lynn
fonte
O que teoricamente significa aqui? Posso assumir que a entrada n se encaixa em um número inteiro de 16 bits? Posso assumir que n ^ λ (n) se encaixa em um dobro?
Dennis
2
Sim e sim, eu diria. Como em teoria , as teorias incluem fingir que seus tipos nativos são arbitrariamente precisos e grandes (eu pensei que era consenso, mas não tenho certeza).
Lynn

Respostas:

48

Mathematica, 16 bytes

CarmichaelLambda

Bem...

Martin Ender
fonte
38
..... realmente. ._.
acrolith 18/09/16
12
Eu não gosto de você mathematica
downrep_nation
29

Python, 76 73 67 bytes

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

Experimente online!

Um outro byte pode ser salvo retornando True em vez de 1 .

Implementação alternativa

Usando a mesma abordagem, também existe a seguinte implementação por @feersum, que não usa compreensão de lista.

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)

Observe que essa implementação requer tempo O (n λ (n) ) . A eficiência pode ser melhorada drasticamente enquanto diminui a pontuação para 66 bytes , mas a função retornará True para a entrada 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)

fundo

Definições e notação

Todas as variáveis ​​empregadas indicarão números inteiros; n , k , e α denotará positivos inteiros; e p denotará um primo positivo .

a | b se b é divisível por a , ie, se houver q tal que b = qa .

a ≡ b ( mod m) se a e b tiverem o mesmo resíduo módulo m , ou seja, se m | a - b .

λ (n) é o menor k tal que um k ≡ 1 ( mod n) - ou seja, tal que n | um k - 1 - para todo um que são primos entre si para n .

f (n) representa a menor k tal que um 2k + 1 ≡ um k + 1 ( mod n) - ou seja, de tal modo que n | a k + 1 (a k - 1) - para todos a .

λ (n) ≤ f (n)

Corrija n e deixe a ser coprime para n .

Pela definição de f , n | a f (n) +1 (a f (n) - 1) . Desde um e n não tem um fator primo comum, nem um f (n) 1 e n , o que implica que n | a f (n) - 1 .

Como λ (n) é o menor número inteiro k tal que n | a k - 1 para todos os inteiros a que são coprime para n , segue-se que λ (n) ≤ f (n) .

λ (n) = f (n)

Como já estabelecemos a desigualdade λ (n) ≤ f (n) , é suficiente verificar que k = λ (n) satisfaz a condição que define f , ou seja, que n | a λ (n) +1 (a λ (n) - 1) para todos a . Para esse fim, estabeleceremos que p α | a λ (n) +1 (a λ (n) - 1) sempre que p α | n .

λ (k) λ (n) sempre que k | n ( fonte ), então (a λ (k) - 1) (a λ (n) -λ (k) + a λ (n) -2λ (k) + ⋯ + a λ (k) + 1) = a λ (n) - 1 e, portanto, a λ (k) - 1 | a λ (n) - 1 | a λ (n) +1 (a λ (n) - 1) .

Se a e p α são coprime, pela definição de λ e acima, p α | a λ (p α ) - 1 | a λ (n) +1 (a λ (n) - 1) segue, conforme desejado.

Se a = 0 , em seguida, um λ (n) 1 (um λ (n) - 1) = 0 , que é divisível por todos os inteiros.

Finalmente, devemos considerar o caso em que um e p α tem um fator primordial comum. Como p é primo, isso implica que p | a . O teorema de Carmichael estabelece que λ (p α ) = (p - 1) p α - 1 se p> 2 ou α <3 e que λ (p α ) = p α - 2 caso contrário. Em todos os casos, λ (p α ) ≥ p α - 2 ≥ 2 α - 2 > α - 2 .

Portanto, λ (n) + 1 ≥ λ (p α ) + 1> α - 1 , de modo λ (n) + 1 ≥ α e p α | p λ (n) +1 | a λ (n) +1 | a λ (n) +1 (a λ (n) - 1) . Isso completa a prova.

Como funciona

Enquanto as definições de f (n) e λ (n) consideram todos os valores possíveis de a , é suficiente testar aqueles que estão em [0, ..., n - 1] .

Quando f (n, k) é chamada, ele calcula um k + 1 (um k - 1)% n para todos os valores de um nessa gama, o que é 0 , se e somente se n | a k + 1 (a k - 1) .

Se todos os resíduos calculados forem zero, k = λ (n) e anyretorna False , então f (n, k) retorna 1 .

Por outro lado, enquanto k <λ (n) , 1-any(...)retornará 0 , então f é chamado recursivamente com um valor incrementado de k . O início -~incrementa o valor de retorno de f (n, k + 1) , então adicionamos 1 a f (n, λ (n)) = 1 uma vez para cada número inteiro em [1, ..., λ (n) - 1 ] . O resultado final é, portanto, λ (n) .

Dennis
fonte
Você pode salvar pelo menos 4 com recursão, em vez de compreender a lista: 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)(Adicione um byte novamente se não gostar de demorar n ** λ (n) tempo).
feersum 19/09/16
1
Obrigado! Enquanto isso, encontrei uma melhoria no meu algoritmo que parece anular o benefício de se repetir em vez de usar uma compreensão de lista.
Dennis
14

Mathematica sem built-in, 58 57 bytes

Agradeço a Martin Ender por encontrar um erro e depois me salvou os bytes necessários para corrigi-lo!

Graças a milhas por economizar 1 byte! (que me pareceu 2)

Os embutidos são totalmente bons ... mas para aqueles que querem implementá-lo sem usar força bruta, aqui está uma fórmula para a função Carmichael:

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

Se p é um primo, a função Carmichael λ (p ^ r) é igual a φ (p ^ r) = (p-1) * p ^ (r-1) - exceto quando p = 2 e r≥3, nesse caso é metade disso, ou seja 2 ^ (r-2).

E se a fatoração de potência principal de n for igual a p1 ^ r1 * p2 ^ r2 * ..., então λ (n) será igual ao múltiplo menos comum de {λ (p1 ^ r1), λ (p2 ^ r2), .. .}.

O tempo de execução é um instante a mais do que fatorar o número inteiro em primeiro lugar.

Greg Martin
fonte
Você pode usar EulerPhipara obter LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&57 bytes.
miles
@miles bem visto! Eu conto 56 bytes, você pode conferir?
Greg Martin
Sim, são 57 bytes .
miles
claramente eu até tento jogar golfe na minha contagem ....: /
Greg Martin
12

Modelos considerados nocivos , 246 bytes

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

Uma função sem nome (não que haja funções nomeadas).

Este é um esquecimento esquecido meu que é interpretado por um compilador C ++ instanciando modelos. Com a profundidade máxima padrão do modelo de g++, ele pode executar λ (35), mas não pode executar λ (101) (a avaliação lenta torna as coisas piores).

feersum
fonte
10

Haskell, 57 56 bytes

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

Geléia, 2 bytes

Æc

Obrigado pelo builtin, @Lynn

dianne
fonte
31
............. ._.
Maltysen 18/09/16
10
Eu nunca entendo o ponto de implementar esses embutidos ridiculamente específicos.
Fatalize 18/09/16
31
Isso é quase uma adição ao idioma criado especificamente para esse desafio. Confirme por Lynn há 2 dias, desafio por @Lynn today
edc65
5
@ edc65 Sem mencionar que esse built-in é praticamente inútil fora desse desafio e seus derivados.
Fatalize 19/09/16
3
Bem, a função Carmichael é importante na teoria dos números (como a resposta atualmente reflete), então eu não chamaria isso de inútil.
Greg Martin
6

Pitão - 19 18 17 bytes

Um byte economizado graças a @TheBikingViking.

Força bruta reta.

f!sm*t.^dTQq1iQdQ

Experimente online aqui .

Maltysen
fonte
f!smté um byte mais curto.
TheBikingViking
@TheBikingViking oh, yeah graças
Maltysen
Dói meus olhos, como diabos é esse python ..? Amamos no entanto haha :)
Yohan Obadia
6

Rubi, 59. 56 bytes

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

J, 28 27 bytes

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

A função Carmichael é λ ( n ) e a função totiente é φ ( n ).

Usa a definição em que λ ( p k ) = φ ( p k ) / 2 se p = 2 e k > 2 mais φ ( p k ). Então, para geral 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 )] .

Uso

Comandos extras usados ​​para formatar várias entradas / saídas.

   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

Explicação

[:*./@(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
milhas
fonte
Isso fornece a resposta errada para 10000 (1000 em vez dos 500 corretos) e, de fato, para cada múltiplo de 8. 2 é um primo peculiar e λ (2 ^ a) = 2 ^ {a-2} (não 2 ^ { a-1}) quando a≥3.
Greg Martin
Obrigado por capturar isso, parece que eu nem consigo ler minha própria saída
milhas
às vezes você não está sozinho ... :)
Greg Martin
5

Na verdade, 30 28 25 19 26 bytes

A função Carmichael, λ(n)onde n = p_0**k_0 * p_1**k_1 * ... * p_a**k_a, é definida como o mínimo múltiplo comum (LCM) λ(p_i**k_i)para as potências primárias máximas p_i**k_ique se dividem n. Dado que, para todo poder primordial, exceto onde está o primo 2, a função Carmichael é equivalente à função totiente de Euler λ(n) == φ(n), usamos em seu φ(n)lugar. Para o caso especial de 2**konde k ≥ 3, apenas verificamos se 2**3 = 8divide em nno início do programa e, se o fizer, dividimos por 2.

Infelizmente, atualmente, na verdade, não há um LCM embutido, então criei um LCM de força bruta. Sugestões de golfe são bem-vindas. Experimente online!

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

Ungolfing

         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
fonte
2
Na verdade, não tenho ideia de como você fez isso em apenas 19 bytes.
Buffer Over Leia
@TheBitByte Com o uso dos totiente gcdbuiltins. Isso seria mais curto se realmente tivesse lcmdiretamente, mas eu não me importo muito com isso e isso apenas derrubaria 4 bytes, no máximo.
Sherlock9
1
A afirmação de que lcm (* a) = produto (* a) / gcd (* a) é verdadeira quando * a é uma lista de exatamente dois números; no entanto, geralmente é falso para listas mais longas (exemplo: se * a é {6,10,15}, fornece 900 em vez da resposta correta de 60). [Nesse caso, está errado é * a também é uma lista de um número!] E você pode verificar se obteve a resposta errada para mais da metade dos casos de teste listados no OP.
Greg Martin
@GregMartin Obrigado pelo aviso. Fixo.
Sherlock9
4

JavaScript (ES6), 143 135 bytes

Edit: salvou 8 bytes graças a Neil

Uma implementação usando programação funcional.

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

Ungolfed e comentou

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

Embora funcione para 6511e 10000não os incluirei aqui, pois tende a ser um pouco lento.

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
fonte
1
JS pode fazer 0..n-1varia bastante facilidade: [...Array(n).keys()]. Isso não requer um, mas dois casos especiais, mas eu ainda estou à frente: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 bytes

Uma porta Ruby da minha resposta Real . Sugestões de golfe são bem-vindas.

Edit: -4 bytes de remoção, amas +9 bytes de correção de um bug onde 1retornados nil. -1 byte graças a Cyoce.

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

Ungolfing

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
fonte
Você não precisa a=. Infelizmente, você retornar nilpara n = 1 :(. (n.prime_division<<[2,1])Correções Não tenho certeza se há uma maneira Golfier..
m-Chrzan
(n%8<1?n/2:n).prime_division...salva outros 2 bytes.
m-Chrzan
@ m-chrzan aé um remanescente de uma tentativa anterior de golfe. Obrigado pelo lembrete sobre ae pelo aviso 1.
Sherlock9
Você pode salvar um byte usando em .reduce :lcmvez de .reduce(:lcm).
Cyoce 24/09/16
1

JavaScript (ES 2016) 149

Implementação de referência Python portada para JS. Faltam alguns recursos sofisticados do Pyhton nos js, like gcde pow, e a compreensão da matriz não é padrão no ES 6. Isso funciona no 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')

Menos golfe

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
fonte
modpow recursivo é mais curto:p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Olivier Grégoire
1

Java, 209 207 202 194 192 bytes

Código (96 bytes):

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;}}

funções extras (96 bytes):

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;}

Testes e não destruídos

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);
  }
}

Notas

  • o uso de aser umint é mais curto do que se eu tivesse que usar a booleanpara realizar meus testes.
  • Sim, é mais curto para valueOftodos os novosBigInteger que criar uma função separada (existem 5, mais a ONEconstante é um brinde).
  • O algoritmo é diferente do algoritmo @Master_ex ', portanto, não é apenas um repost de golfe. Além disso, esse algoritmo é muito menos eficiente comogcd é calculado repetidamente para os mesmos valores.

Barbear

  1. 209 -> 207 bytes:
    • if(...)a=...; -> a=...?...:1;
    • a==1 -> a<2
  2. 207 -> 202 bytes
    • Livre-se de BigIntegergolfe gcde modPowpara int.
  3. 202 -> 194 bytes
    • loop modPow-> recursivo
  4. 194 -> 192 bytes
    • ==1-> <2(parece funcionar para todos os casos de teste, não sabe para outros números.)
Olivier Grégoire
fonte
Ei! Eu notei que a saída não é a esperada. Veja a pergunta para os resultados esperados. Pessoalmente, costumo escrever testes de unidade antes de começar a jogar meu código, isso ajuda! Eu acho que o problema poderia ser o modPow em números inteiros, eu também tive esse problema e é por isso que usei o BigInteger no final.
Master_ex
Hmmm ... Estou surpreso, deixei meus testes rodarem a cada mudança. Vou verificar o que há de errado.
Olivier Grégoire
1
@ Master_ex eu consertei. Voltar à versão anterior está ok.
Olivier Grégoire
Acho seu método recursivo modpow pbastante inteligente. Também tentei usar apenas números inteiros no início, mas como mencionei na resposta, tive problemas de precisão e foi por isso que mudei para BigInteger(ou seja, Math.pow(3, 100)%101retornei em 60.0vez de 1). Sua implementação é imune a isso porque executa o mod em cada iteração. No entanto, ele ainda sofre de um bug. Para grandes m painda pode retornar resultados errados. Além disso, devido à recursão, StackOverflowErrorpode ocorrer facilmente para entradas grandes com o tamanho da pilha padrão.
Master_ex
@ Master_ex Sim, isso é uma consequência da restrição de inttipos. Eu poderia usar longos em vez de ints, isso seria 8 bytes extras. Mas, na minha opinião, todos os casos de teste são válidos, então deixo assim. StackOverflowErrorpode acontecer, mas é assim que a recursividade funciona. Existem métodos para limitar a 32 pilhas, mas usam muitos mais bytes. Esta implementação é frágil, sim, você está totalmente certo. Mas é forte o suficiente para os casos de teste.
Olivier Grégoire
1

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

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];}

Importações, 19 bytes

import java.math.*;

Explicação

É uma implementação direta. Os co-primos são calculados na Set ppotência de cada indivíduo e é usado para verificar se é igual a 1 módulo n.

Eu tive que usar BigIntegerpor causa de problemas de precisão.

Uso

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

Ungolfed

// 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];
}

Quaisquer sugestões para jogar mais são bem-vindas :-)

Atualizar

  • Nenhum elemento fora das funções que mantêm o estado
  • Seguiu o conselho de Olivier Grégoire e salvou 1 byte de B()
  • Removido o k()método e p(co-primos) Set.
  • Removida a conversão não necessária para int.
  • Varags adicionadas e uso por vez de enquanto.
Master_ex
fonte
Você pode ter uma versão ungolfed (com quebras de linha, os comentários aqui e ali, etc.)
OldBunny2800
@ OldBunny2800: Sim, claro. No entanto, farei isso mais tarde hoje, porque agora estou ocupado!
Master_ex
@ OldBunny2800: Eu adicionei uma versão ungolfed :-)
Master_ex
Hmmm ... não sei se isso conta, pois não é uma função nem um programa. Se for uma função, existem elementos externos que mantêm o estado, tornando-o um método de fato (a função é pura entrada-> saída sem estado externo); se for um programa, todo o método principal está ausente. Se minhas interpretações estiverem incorretas, por favor me diga! Eu acho que é melhor incluir k(int)no loop, pois é uma linha e pode ser feito. Além disso, a constante O também pode ser inserida no cmétodo. Eu acho que você ganhará bytes fazendo isso!
Olivier Grégoire
Concretamente, while(n>1&&!p.stream().allMatch(x->B((int)x).modPow(B(k), B(n)).equals(O)))raspa bytes e corrige os problemas que eu mencionei se você colocar o conjunto e a constante novamente no método. Além disso, você usa Oduas vezes, substitua por B(1)para barbear bytes.
Olivier Grégoire
1

Java, 165 163 158 152 143 bytes

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;}

Outra porta da minha implementação C .

Experimente no Ideone

teto
fonte
1

C ++, 208 200 149 144 140 134 bytes

[](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;};

Uma porta de minha implementação C .

Experimente no Ideone

teto
fonte
0

Raquete 218 bytes

(λ(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))))

Versão não destruída:

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

Teste:

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

Saída:

1
2
4
12
100
52
84
3056
500
rnso
fonte
0

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

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;}

Isso usa um algoritmo de exponenciação modular lento, calcula o GCD com muita freqüência e não mais vaza memória!

Ungolfed:

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;
}

Experimente no Ideone

teto
fonte
0

Axiom 129 bytes

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)

menos golfe

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

resultados

(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
fonte