Les plus grands exposants principaux

22

Étant donné un entier n >= 2, affichez le plus grand exposant de sa factorisation principale. Il s'agit de la séquence OEIS A051903 .

Exemple

Soit n = 144. Sa factorisation principale est 2^4 * 3^2. Le plus grand exposant est 4.

Cas de test

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
la source
Sandbox
Mego

Réponses:

5

Haskell , 61 60 50 48 46 octets

-2 octets grâce à xnor

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

Essayez-le en ligne!

45 octets avec une importation:

import NumberTheory
maximum.map snd.factorize

Essayez-le en ligne!

H.PWiz
la source
Le 0^est mignon, mais il est plus court pour vérifier la condition en tant que booléen.
xnor
4

Python 2 , 78 octets

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

Essayez-le en ligne!

-5 grâce aux ovs .

Cette réponse ne fait pas de vérifications principales. Au lieu de cela, il tire parti du fait que l'exposant le plus élevé d'un facteur premier sera supérieur ou égal à l'exposant de tout autre facteur dans toute factorisation d'un nombre.

Erik le Outgolfer
la source
81 octets
ovs
@ovs merci, j'ai raté ça pendant que j'essayais de poster rapidement
Erik the Outgolfer
78 octets
ovs
@ovs enfin, détendu de l'if / else, merci
Erik the Outgolfer
4

Japt -h , 9 7 octets

k ü mÊn

Essayez-le

k ü mÊn     :Implicit input of integer
k           :Prime factors
  ü         :Group by value
    m       :Map
     Ê      :  Length
      n     :Sort
            :Implicit output of last element
Hirsute
la source
2
Je pense que cela devrait être beaucoup plus court, je devrais peut-être ajouter un module intégré pour les paires exposant principal ...
ETHproductions
Pourquoi utiliser "ü: Grouper par valeur" au lieu de la fonction de tri? Oui peut-être parce que sort renvoie un tableau mais nous avons besoin d'un tableau de tableaux ...
RosLuP
1
@RosLuP, exactement; ücrée des sous-tableaux de valeurs égales. Il fait également trier par première valeur , mais ce n'est pas pertinent en l' espèce.
Shaggy
3

Mathematica, 27 octets

Max[Last/@FactorInteger@#]&

Essayez-le en ligne!

J42161217
la source
Vous pouvez également Max@@Last/@FactorInteger@#&. Malheureusement, cela n'économise aucun octet.
2017 totalement humain
3

Brachylog , 5 octets

ḋḅlᵐ⌉

Essayez-le en ligne!

Explication

ḋ          Prime decomposition
 ḅ         Group consecutive equal values
  lᵐ       Map length
    ⌉      Maximum
Fatalize
la source
3

Husk , 5 octets

▲mLgp

Essayez-le en ligne!

  • p - Obtient les facteurs premiers.
  • g - Regroupe les valeurs adjacentes.
  • mL - Obtient les longueurs de chaque groupe.
  • - Maximum.
M. Xcoder
la source
2

APL (Dyalog) , 19 octets

CY'dfns'
⌈/12pco

Essayez-le en ligne!

Comment?

2pco⎕ - Tableau 2D de facteurs premiers et d'exposants

1↓ - laisser tomber les facteurs

⌈/ - maximum

Uriel
la source
2

Javascript 54 octets

* en supposant une pile infinie (comme dans les défis de code-golf)

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
la source
2

PARI / GP, 24 octets

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

Si je ne compte pas la n->partie, c'est 21 octets.

Jeppe Stig Nielsen
la source
2

Octave , 25 octets

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

Essayez-le en ligne!

Explication

factorproduit le tableau d'exposants premiers (éventuellement répétés) La deuxième sortie de modedonne le nombre de fois que le mode (c'est-à-dire l'entrée la plus répétée) apparaît.

Luis Mendo
la source
1

Pyth , 7 octets

eShMr8P

Essayez-le ici.

Erik le Outgolfer
la source
Alternatives: eS/LPQP(7 octets), eSlM.gkP(8 octets).
M. Xcoder
1

Gaia , 4 octets

ḋ)⌠)

Essayez-le en ligne!

  • - Calcule la factorisation principale en paires [prime, exposant] .

    • - Cartographie et collecte du résultat avec la valeur maximale.

    • ) - Dernier élément (exposant).

    • ) - Dernier élément (exposant maximal)

Gaia , 4 octets

ḋ)¦⌉

Essayez-le en ligne!

  • - Calcule la factorisation principale en paires [prime, exposant] .

    • - Carte avec le dernier élément (exposant).

    • - Obtient l'élément maximum.

M. Xcoder
la source
1

MY , 4 octets

ωĖ⍐←

Essayez-le en ligne!

Explication?

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

Octave : 30 octets

@(x)max(histc(a=factor(x),a));
  1. a=factor(x)renvoie un vecteur contenant les facteurs premiers de x. Il s'agit d'un vecteur trié par ordre croissant où la multiplication de tous les nombres dans les factor(x)rendementsx telle sorte que chaque nombre dans le vecteur est premier.
  2. histc(...,a)calcule un histogramme sur le vecteur de facteur premier où les cases sont les facteurs premiers. L'histogramme compte le nombre de fois où nous avons vu chaque nombre premier, donnant ainsi l'exposant de chaque nombre premier. Nous pouvons tricher ici un peu parce que même si factor(x)nous retournerons des nombres ou des bacs en double, un seul des bacs capturera le nombre total de fois où nous verrons un nombre premier.
  3. max(...) renvoie donc le plus grand exposant.

Essayez-le en ligne!

rayryeng - Réintégrer Monica
la source
1

Alice , 17 octets

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

Essayez-le en ligne!

Explication

/o
\i@/...

Ceci est juste un cadre pour les programmes arithmétiques simples avec des E / S décimales. C'est ...le programme réel, qui a déjà l'entrée sur la pile et laisse la sortie au-dessus de la pile.

Alice a en fait des fonctions intégrées pour obtenir la factorisation première d'un entier (même avec des paires exposant-prime), mais la plus courte que j'ai trouvée en utilisant celles-ci est 10 octets de plus que cela.

Au lieu de cela, l'idée est que nous divisons à plusieurs reprises une copie de chaque facteur premier distinct de l'entrée, jusqu'à ce que nous atteignions 1 . Le nombre d'étapes que cela prend est égal au plus grand exposant premier. Nous allons abuser de la tête de bande comme variable de compteur.

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
la source
1

Julia, 60 52 40 octets

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

-12 + correction grâce à Steadybox

EricShermanCS
la source
1
Je pense que vous devez ajouter un appel à print(). De plus, je n'ai pas pu faire fonctionner le code sur TIO tel quel, je suppose qu'il fonctionne sur une autre version du langage qui n'est pas disponible là-bas? Cela fonctionne bien sur TIO: print(maximum(collect(values(factor(parse(BigInt,readline()))))))
Steadybox
Cela fonctionne sur l'interprète (sur mon ordinateur, au moins). Il provoque également un avertissement, car l'initialisation d'un BigInt comme celui-ci est obsolète. Néanmoins, si vous copiez et collez le code tel quel dans un interpréteur Julia, cela devrait fonctionner. (si une impression est requise car elle doit être explicitement imprimée,
je ne
1
Le print()est nécessaire car la réponse doit être un programme complet (qui affiche la sortie) ou une fonction (qui renvoie la sortie). Sinon, votre solution est très bien. Il semble que vous pouvez économiser quelques octets (et éviter l'impression) de cette façon:f(x)=maximum(collect(values(factor(x))))
Steadybox
1
Vous êtes les bienvenus! Voici une méta-publication sur le format autorisé pour une solution.
Steadybox
0

En fait , 4 octets

w♂NM

Essayez-le en ligne!

w♂NM - Programme complet.

w - Pousse la factorisation principale en paires [prime, exposant].
 ♂N - Récupère le dernier élément de chacun (les exposants).
   M - Maximum.
M. Xcoder
la source
J'ai utilisé cette solution exacte pour écrire les cas de test :)
Mego
@Mego Pensez-vous qu'il peut raccourcir (je ne veux pas que vous vous gâtiez si vous en avez un plus court, je vous le demande)? :)
M. Xcoder
Non, je pense que c'est optimal pour En fait.
Mego
0

Python 2 , 64 octets

-4 octets grâce à H.PWiz.

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

Essayez-le en ligne!

Réponse de Haskell de H.PWiz . Je ne partage cela que parce que je suis fier d'avoir pu comprendre ce morceau de code Haskell et le traduire. : P

totalement humain
la source
Ça range(1,n)ne marche pas?
H.PWiz
range(1, n)produit tous les entiers dans [1, n).
2017 totalement humain
1
Ah, eh bien, vous n'avez pas vraiment besoin d'aller jusqu'à n poura
H.PWiz
Oh, d'accord, je ne comprends pas complètement les mathématiques derrière ça. : P Merci!
2017 totalement humain
1
64 octets
H.PWiz
0

Axiome, 61 octets

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

C'est la première fois que je trouve qu'il est possible de définir la fonction sans utiliser de parenthèses (). Au lieu de "f (n) ==" "fn ==" un caractère de moins ...

RosLuP
la source
0

Raquette , 83 79 octets

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

Essayez-le en ligne!

(Je ne suis pas sûr qu'il y ait un consensus sur ce qui constitue une solution complète de Racket, donc je vais avec la convention Mathematica qu'une fonction pure compte.)

Comment ça marche

factorizedonne la factorisation sous forme de liste de paires: (factorize 108)donne '((2 2) (3 3)). Le deuxième élément d'une paire est donné par cadr, un raccourci pour la composition de car(tête de liste) avec cdr(queue de liste).

Je me sens idiot de faire (cadr (argmax cadr list))pour trouver le maximum des seconds éléments, mais maxne fonctionne pas sur les listes:(max (map cadr list)) ne fait pas ce que nous voulons. Je ne suis pas un expert en raquette, donc il y a peut-être une meilleure façon standard de le faire.

Raquette, 93 octets

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

Essayez-le en ligne!

Comment ça marche

Une version alternative qui n'importe pas factorizeet fait tout à partir de zéro, plus ou moins. La fonction (p m d)trouve la puissance la plus élevée de dcette division m, puis nous trouvons simplement la valeur la plus élevée de (p n d)pour dentre 2et n. (Nous n'avons pas besoin de limiter cela aux nombres premiers, car il n'y aura pas de puissance composite qui fonctionne mieux que les puissances premières.)

Misha Lavrov
la source
Je suppose que la maxsolution standard est (apply max (map cadr list)mais (cadr (argmax cadr list))est malheureusement plus courte.
Misha Lavrov
0

APL (NARS), 15 caractères, 30 octets

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

tester:

  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 

commentaire:

{⌈/+/¨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
la source