Maiores expoentes principais

22

Dado um número inteiro n >= 2, produz o maior expoente em sua fatoração primária. Esta é a sequência O0IS A051903 .

Exemplo

Let n = 144. Sua principal fatoração é 2^4 * 3^2. O maior expoente é 4.

Casos de teste

2 -> 1
3 -> 1
4 -> 2
5 -> 1
6 -> 1
7 -> 1
8 -> 3
9 -> 2
10 -> 1
11 -> 1
12 -> 2
144 -> 4
200 -> 3
500 -> 3
1024 -> 10
3257832488 -> 3
Mego
fonte
Sandbox
Mego 21/10

Respostas:

5

Haskell , 61 60 50 48 46 bytes

-2 bytes graças ao xnor

f n=maximum[a|k<-[2..n],a<-[1..n],n`mod`k^a<1]

Experimente online!

45 bytes com uma importação:

import NumberTheory
maximum.map snd.factorize

Experimente Online!

H.PWiz
fonte
O 0^é bonito, mas é mais curto para apenas verificar a condição como um boolean.
Xnor
4

Python 2 , 78 bytes

n=input()
e=m=0
f=2
while~-n:q=n%f<1;f+=1-q;e=q*-~e;m=max(m,e);n/=f**q
print m

Experimente online!

-5 graças a ovs .

Esta resposta não faz verificações principais. Em vez disso, tira vantagem do fato de que o expoente mais alto de um fator primo será maior ou igual ao expoente de qualquer outro fator em qualquer fatoração de um número.

Erik, o Outgolfer
fonte
81 bytes
ovs 21/10
@ovs graças, perdeu que enquanto eu estava tentando postar rapidamente
Erik o Outgolfer
78 bytes
ovs 22/10
@ovs finalmente, ficou relaxado dos if / else, graças
Erik as Outgolfer
4

Japonês -h , 9 7 bytes

k ü mÊn

Tente

k ü mÊn     :Implicit input of integer
k           :Prime factors
  ü         :Group by value
    m       :Map
     Ê      :  Length
      n     :Sort
            :Implicit output of last element
Shaggy
fonte
2
Eu sinto que este deve ser caminho mais curto, talvez eu deveria adicionar um built-in para pares prime-expoente ...
ETHproductions
Por que usar "ü: Agrupar por valor" em vez da função de classificação? Sim, talvez porque o tipo retorne uma matriz, mas precisamos de uma matriz de matrizes ...
RosLuP 18/03
1
@RosLuP, exatamente; ücria sub-matrizes de valores iguais. Ele faz também ordenar por valor primeiro, mas isso não é relevante aqui.
Shaggy
3

Mathematica, 27 bytes

Max[Last/@FactorInteger@#]&

Experimente online!

J42161217
fonte
Alternativamente Max@@Last/@FactorInteger@#&,. Infelizmente, isso não salva bytes.
totallyhuman
3

Braquilog , 5 bytes

ḋḅlᵐ⌉

Experimente online!

Explicação

ḋ          Prime decomposition
 ḅ         Group consecutive equal values
  lᵐ       Map length
    ⌉      Maximum
Fatalizar
fonte
3

Casca , 5 bytes

▲mLgp

Experimente online!

  • p - Obtém os principais fatores.
  • g - Agrupa valores adjacentes.
  • mL - Obtém os comprimentos de cada grupo.
  • - Máximo.
Mr. Xcoder
fonte
2

APL (Dyalog) , 19 bytes

CY'dfns'
⌈/12pco

Experimente online!

Quão?

2pco⎕ - Conjunto 2D de fatores primos e expoentes

1↓ - abandone os fatores

⌈/ - máximo

Uriel
fonte
2

Javascript 54 bytes

* assumindo pilha infinita (como acontece nos desafios de código-golfe)

P=(n,i=2,k)=>i>n?k:n%i?k>(K=P(n,i+1))?k:K:P(n/i,i,-~k)

console.log(P(2 )== 1)
console.log(P(3 )== 1)
console.log(P(4 )== 2)
console.log(P(5 )== 1)
console.log(P(6 )== 1)
console.log(P(7 )== 1)
console.log(P(8 )== 3)
console.log(P(9 )== 2)
console.log(P(10 )== 1)
console.log(P(11 )== 1)
console.log(P(12 )== 2)
console.log(P(144 )== 4)
console.log(P(200 )== 3)
console.log(P(500 )== 3)
console.log(P(1024 )== 10)
//console.log(P(3257832488 )== 3)

DanielIndie
fonte
2

PARI / GP, 24 bytes

n->vecmax(factor(n)[,2])

Se eu não contar a n->parte, são 21 bytes.

Jeppe Stig Nielsen
fonte
2

Oitava , 25 bytes

@(n)[~,m]=mode(factor(n))

Experimente online!

Explicação

factorproduz a matriz de expoentes primos (possivelmente repetidos) A segunda saída de modefornece o número de vezes que o modo (isto é, a entrada mais repetida) aparece.

Luis Mendo
fonte
1

Pitão , 7 bytes

eShMr8P

Experimente aqui.

Erik, o Outgolfer
fonte
Alternativas: eS/LPQP(7 bytes), eSlM.gkP(8 bytes).
Xcoder
1

Gaia , 4 bytes

ḋ)⌠)

Experimente online!

  • - Calcula a fatoração primária como pares [primos, expoentes] .

    • - Mapeie e colete o resultado com o valor máximo.

    • ) - Último elemento (expoente).

    • ) - Último elemento (expoente máximo)

Gaia , 4 bytes

ḋ)¦⌉

Experimente online!

  • - Calcula a fatoração primária como pares [primos, expoentes] .

    • - Mapa com o último elemento (expoente).

    • - Obtém o elemento máximo.

Mr. Xcoder
fonte
1

MEU , 4 bytes

ωĖ⍐←

Experimente online!

Explicação?

ωĖ⍐←
ω    = argument
 Ė   = prime exponents
  ⍐  = maximum
   ← = output without a newline
Zacharý
fonte
1

Oitava : 30 bytes

@(x)max(histc(a=factor(x),a));
  1. a=factor(x)retorna um vetor contendo os fatores primos de x. Este é um vetor classificado em ordem crescente, em que a multiplicação de todos os números se factor(x)produz de xtal forma que cada número no vetor é primo.
  2. histc(...,a)calcula um histograma no vetor de fatores primos, em que os compartimentos são os fatores primos. O histograma conta quantas vezes vimos cada número primo, produzindo o expoente de cada número primo. Podemos trapacear um pouco aqui, porque, embora factor(x)retorne números ou posições duplicados, apenas uma delas capturará a quantidade total de vezes que vemos um número primo.
  3. max(...) assim retorna o maior expoente.

Experimente online!

rayryeng - Restabelecer Monica
fonte
1

Alice , 17 bytes

/o
\i@/w].D:.t$Kq

Experimente online!

Explicação

/o
\i@/...

Essa é apenas uma estrutura para programas aritméticos simples com E / S decimal. O ...é o programa real, que já tem a entrada na pilha e deixa a saída no topo da pilha.

Na verdade, Alice tem built-ins para obter a fatoração primária de um número inteiro (mesmo com pares de expoentes primos), mas o mais curto que eu já usei é 10 bytes a mais que isso.

Em vez disso, a idéia é que dividimos repetidamente uma cópia de cada fator primo distinto da entrada, até chegarmos a 1 . O número de etapas que você executa é igual ao maior expoente principal. Abusaremos da cabeça da fita como variável do contador.

w      Remember the current IP position. Effectively starts a loop.
  ]      Move the tape head to the right, which increments our counter.
  .D     Duplicate the current value, and deduplicate its prime factors.
         That means, we'll get a number which is the product of the value's
         unique prime factors. For example 144 = 2^4 * 3^2 would become
         6 = 2 * 3.
  :      Divide the value by its deduplicated version, which decrements the
         exponents of its prime factors.
  .t     Duplicate the result and decrement it. This value becomes 0 once we
         reach a result of 1, which is when we want to terminate the loop.
$K     Jump back to the beginning of the loop if the previous value wasn't 0.
q      Retrieve the tape head's position, i.e. the number of steps we've taken
       through the above loop.
Martin Ender
fonte
1

Julia, 60 52 40 bytes

f(x)=maximum(collect(values(factor(x))))

Correção -12 + graças ao Steadybox

EricShermanCS
fonte
1
Eu acho que você precisa adicionar uma chamada para print(). Além disso, não consegui que o código fosse executado no TIO como está, presumo que ele funcione em alguma outra versão do idioma que não está disponível lá? Isso funciona bem no TIO: print(maximum(collect(values(factor(parse(BigInt,readline()))))))
Steadybox 26/10
Isso funciona no intérprete (no meu computador, pelo menos). Também causa um aviso porque a inicialização de um BigInt como esse foi preterida. No entanto, se você copiar e colar o código como está em um intérprete Julia, ele deverá funcionar. (se uma impressão for necessária porque precisa ser explicitamente impressa, eu a colocarei) #
EricShermanCS 26/10
1
A print()é necessária porque a resposta tem de ser um programa completo (que exibe a saída) ou uma função (que retorna a saída). Caso contrário, sua solução está correta. Parece que você pode salvar alguns bytes (e evitar a impressão) desta maneira:f(x)=maximum(collect(values(factor(x))))
Steadybox 26/10
1
De nada! Aqui está uma meta post sobre qual é o formato permitido para uma solução.
Steadybox 26/10/19
0

Na verdade , 4 bytes

w♂NM

Experimente online!

w♂NM - Programa completo.

w - Empurra a fatoração primária como pares [primos, expoentes].
 ♂N - Obtenha o último elemento de cada (os expoentes).
   M - Máximo.
Mr. Xcoder
fonte
Eu usei essa solução exata para escrever os casos de teste :)
Mego
@Mego Você acha que pode ficar mais curto (eu não quero que você estrague se você tiver um mais curto, apenas perguntando)? :)
Sr. Xcoder 21/10
Não, acredito que isso é ideal para a verdade.
Mego 21/10
0

Python 2 , 64 bytes

-4 bytes graças a H.PWiz.

lambda n:max(a*(n%k**a<1)for a in range(n)for k in range(2,-~n))

Experimente online!

Resposta do porto de H.PWiz Haskell . Só estou compartilhando isso porque tenho orgulho de ter conseguido entender esse pedaço de código Haskell e traduzi-lo. : P

totalmente humano
fonte
Não range(1,n)funciona?
H.PWiz
range(1, n)produz todos os números inteiros em [1, n).
totallyhuman
1
Ah, bem, você realmente não precisa ir todo o caminho até n paraa
H.PWiz
Oh, ok, eu não entendo completamente a matemática por trás disso. : P Obrigado!
totallyhuman
1
64 bytes
H.PWiz
0

Axioma, 61 bytes

f n==(a:=factors n;reduce(max,[a.i.exponent for i in 1..#a]))

Esta é a primeira vez que acho possível definir a função sem o uso de parênteses (). Em vez de "f (n) ==" "fn ==" um caractere a menos ...

RosLuP
fonte
0

Raquete , 83 79 bytes

(λ(n)(cadr(argmax cadr((let()(local-require math/number-theory)factorize)n))))

Experimente online!

(Não tenho certeza se existe um consenso sobre o que constitui uma solução completa do Racket, então vou com a convenção do Mathematica de que uma função pura conta.)

Como funciona

factorizedá a fatoração como uma lista de pares: (factorize 108)'((2 2) (3 3)). O segundo elemento de um par é dado por cadr, uma abreviação para a composição de car(cabeça de uma lista) com cdr(cauda de uma lista).

Eu me sinto boba fazendo (cadr (argmax cadr list))para encontrar o máximo dos segundos elementos, mas maxnão funciona em listas: (max (map cadr list))não faz o que queremos. Eu não sou especialista em Racket, então talvez haja uma maneira padrão melhor de fazer isso.

Raquete, 93 bytes

(λ(n)(define(p d m)(if(=(gcd m d)d)(+(p d(/ m d))1)0))(p(argmax(λ(d)(p d n))(range 2 n))n))

Experimente online!

Como funciona

Uma versão alternativa que não importa factorizee faz tudo do zero, mais ou menos. A função (p m d)encontra o maior poder do dque divide me então nós apenas encontrar maior valor de (p n d)para dentre 2e n. (Não precisamos restringir isso a números primos, pois não haverá um poder composto que funcione melhor do que os poderes primos.)

Misha Lavrov
fonte
Eu acho que a maxsolução padrão é, (apply max (map cadr list)mas (cadr (argmax cadr list))infelizmente é mais curta.
Misha Lavrov #
0

APL (NARS), 15 caracteres, 30 bytes

{⌈/+/¨v∘=¨v←π⍵}

teste:

  f←{⌈/+/¨v∘=¨v←π⍵}
  f¨2..12
1 1 2 1 1 1 3 2 1 1 2 
  f¨144 200 500 1024 3257832488
4 3 3 10 3 

Comente:

{⌈/+/¨v∘=¨v←π⍵}
          v←π⍵    π12 return 2 2 3; assign to v the array of prime divisors of argument ⍵
      v∘=¨        for each element of v, build one binary array, show with 1 where are in v array, else puts 0 
                  return one big array I call B, where each element is the binary array above
   +/¨            sum each binary element array of  B
 ⌈/               get the max of all element of B (that should be the max exponet)
RosLuP
fonte