22
\$\begingroup\$

Given an integer n >= 2, output the largest exponent in its prime factorization. This is OEIS sequence A051903.

Example

Let n = 144. Its prime factorization is 2^4 * 3^2. The largest exponent is 4.

Test Cases

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
\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – Mego Oct 21 '17 at 17:43

28 Answers 28

8
\$\begingroup\$

05AB1E, 2 bytes

ÓZ

Try it online!

How?

Ó   exponents of prime factors
 Z  maximum
\$\endgroup\$
7
\$\begingroup\$

Python 2, 62 57 56 bytes

lambda n:max(k%n-n%(k/n+2)**(k%n)*n for k in range(n*n))

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Jelly, 3 bytes

ÆEṀ

Try it online!

ÆEṀ  - Full program / Monadic link.

ÆE   - Array of exponents of prime factorization.
  Ṁ  - Maximum.

This also works in M. Try it online!

\$\endgroup\$
5
\$\begingroup\$

Haskell, 61 60 50 48 46 bytes

-2 bytes thanks to xnor

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

Try it online!

45 bytes with an import:

import NumberTheory
maximum.map snd.factorize

Try it Online!

\$\endgroup\$
  • \$\begingroup\$ The 0^ is cute, but it's shorter to just check the condition as a boolean. \$\endgroup\$ – xnor Oct 22 '17 at 20:41
4
\$\begingroup\$

Ohm v2, 2 bytes

n↑

Try it online!

Explanation?

No.

\$\endgroup\$
4
\$\begingroup\$

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

Try it online!

-5 thanks to ovs.

This answer doesn't do prime checks. Instead, it takes advantage of the fact that the highest exponent of a prime factor will be greater than or equal to the exponent of any other factor in any factorization of a number.

\$\endgroup\$
  • \$\begingroup\$ 81 bytes \$\endgroup\$ – ovs Oct 21 '17 at 18:12
  • \$\begingroup\$ @ovs thanks, missed that while I was trying to post quickly \$\endgroup\$ – Erik the Outgolfer Oct 21 '17 at 18:15
  • \$\begingroup\$ 78 bytes \$\endgroup\$ – ovs Oct 22 '17 at 12:59
  • \$\begingroup\$ @ovs finally, got relaxed from the if/else, thanks \$\endgroup\$ – Erik the Outgolfer Oct 22 '17 at 13:00
4
\$\begingroup\$

Japt -h, 9 7 bytes

k ü mÊn

Try it

k ü mÊn     :Implicit input of integer
k           :Prime factors
  ü         :Group by value
    m       :Map
     Ê      :  Length
      n     :Sort
            :Implicit output of last element
\$\endgroup\$
  • 2
    \$\begingroup\$ I feel like this should be way shorter, maybe I should add a built-in for prime-exponent pairs... \$\endgroup\$ – ETHproductions Oct 23 '17 at 13:34
  • \$\begingroup\$ Why to use "ü :Group by value" instead of sort function? Yes perhaps because sort return one array but we need one array of arrays... \$\endgroup\$ – RosLuP Mar 18 at 10:06
  • 1
    \$\begingroup\$ @RosLuP, Exactly; ü creates sub-arrays of the equal values. It does also sort by value first but that's not relevant here. \$\endgroup\$ – Shaggy Mar 18 at 10:22
3
\$\begingroup\$

Mathematica, 27 bytes

Max[Last/@FactorInteger@#]&

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Alternatively, Max@@Last/@FactorInteger@#&. Unfortunately this doesn't save any bytes. \$\endgroup\$ – totallyhuman Oct 21 '17 at 18:24
3
\$\begingroup\$

MATL, 4 bytes

YFX>

Try it online!

       % implicit input
YF     % Exponents of prime factors
X>     % maximum
       % implicit output

\$\endgroup\$
3
\$\begingroup\$

Brachylog, 5 bytes

ḋḅlᵐ⌉

Try it online!

Explanation

ḋ          Prime decomposition
 ḅ         Group consecutive equal values
  lᵐ       Map length
    ⌉      Maximum
\$\endgroup\$
3
\$\begingroup\$

Husk, 5 bytes

▲mLgp

Try it online!

  • p – Gets the prime factors.
  • g – Groups adjacent values.
  • mL – Gets the lengths of each group.
  • – Maximum.
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog), 19 bytes

⎕CY'dfns'
⌈/1↓2pco⎕

Try it online!

How?

2pco⎕ - 2D array of prime factors and exponents

1↓ - drop the factors

⌈/ - maximum

\$\endgroup\$
2
\$\begingroup\$

Javascript 54 bytes

*assuming infinite stack (as do in code-golf challenges)

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)

\$\endgroup\$
2
\$\begingroup\$

PARI/GP, 24 bytes

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

If I do not count the n-> part, it is 21 bytes.

\$\endgroup\$
2
\$\begingroup\$

Octave, 25 bytes

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

Try it online!

Explanation

factor produces the array of (possibly repeated) prime exponents The second output of mode gives the number of times that the mode (i.e. the most repeated entry) appears.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 7 bytes

eShMr8P

Try it here.

\$\endgroup\$
  • \$\begingroup\$ Alternatives: eS/LPQP (7 bytes), eSlM.gkP (8 bytes). \$\endgroup\$ – Mr. Xcoder Oct 21 '17 at 17:55
1
\$\begingroup\$

Python 2, 90 84 bytes

f=lambda n,i=2,l=[0]:(n<2)*max(map(l.count,l))or n%i and f(n,i+1,l)or f(n/i,2,l+[i])

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Gaia, 4 bytes

ḋ)⌠)

Try it online!

  • - Computes the prime factorization as [prime, exponent] pairs.

    • - Map and collect the result with the maximal value.

    • ) - Last element (exponent).

    • ) - Last element (maximal exponent)

Gaia, 4 bytes

ḋ)¦⌉

Try it online!

  • - Computes the prime factorization as [prime, exponent] pairs.

    • - Map with the last element (exponent).

    • - Gets the maximum element.

\$\endgroup\$
1
\$\begingroup\$

MY, 4 bytes

ωĖ⍐←

Try it online!

Explanation?

ωĖ⍐←
ω    = argument
 Ė   = prime exponents
  ⍐  = maximum
   ← = output without a newline
\$\endgroup\$
1
\$\begingroup\$

Octave: 30 bytes

@(x)max(histc(a=factor(x),a));
  1. a=factor(x) returns a vector containing the prime factors of x. This is a vector sorted in ascending order where the multiplication of all numbers in factor(x) yields x itself such that each number in the vector is prime.
  2. histc(...,a) calculates a histogram on the prime factor vector where the bins are the prime factors. The histogram counts up how many times we have seen each prime number thus yielding the exponent of each prime number. We can cheat here a bit because even though factor(x) will return duplicate numbers or bins, only one of the bins will capture the total amount of times we see a prime number.
  3. max(...) thus returns the largest exponent.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Alice, 17 bytes

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

Try it online!

Explanation

/o
\i@/...

This is just a framework for simple-ish arithmetic programs with decimal I/O. The ... is the actual program, which already has the input on the stack and leaves the output on top of the stack.

Alice actually has built-ins to get the prime factorisation of an integer (even with prime-exponent pairs), but the shortest I've come up with using those is 10 bytes longer than this.

Instead the idea is that we repeatedly divide one copy of each distinct prime factor out of the input, until we reach 1. The number of steps this takes is equal to the largest prime exponent. We'll be abusing the tape head as the counter variable.

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.
\$\endgroup\$
1
\$\begingroup\$

Julia, 60 52 40 bytes

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

-12 +correction thanks to Steadybox

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you need to add a call to print(). Also, I couldn't get the code to run on TIO as is, I assume it works on some other version of the language not available there? This runs fine on TIO: print(maximum(collect(values(factor(parse(BigInt,readline())))))) \$\endgroup\$ – Steadybox Oct 26 '17 at 2:28
  • \$\begingroup\$ This works on the interpreter (on my computer, at least). It also causes a warning because initializing a BigInt like that has been deprecated. Nonetheless, if you copy and paste the code as-is into a Julia interpreter, it should work. (if a print is required because it has to explicitly be printed, ill put that in) \$\endgroup\$ – EricShermanCS Oct 26 '17 at 2:36
  • 1
    \$\begingroup\$ The print() is needed because the answer needs to be a full program (that displays the output) or a function (that returns the output). Otherwise your solution is fine. It seems that you can save some bytes (and avoid the print) this way: f(x)=maximum(collect(values(factor(x)))) \$\endgroup\$ – Steadybox Oct 26 '17 at 2:46
  • 1
    \$\begingroup\$ You're welcome! Here's a meta post on what is the allowed format for a solution. \$\endgroup\$ – Steadybox Oct 26 '17 at 2:58
0
\$\begingroup\$

Actually, 4 bytes

w♂NM

Try it online!

w♂NM  - Full program.

w     - Pushes the prime factorization as [prime, exponent] pairs.
 ♂N   - Get the last element of each (the exponents).
   M  - Maximum.
\$\endgroup\$
  • \$\begingroup\$ I used this exact solution for writing the test cases :) \$\endgroup\$ – Mego Oct 21 '17 at 17:57
  • \$\begingroup\$ @Mego Do you think it can get shorter (I don't want you to spoil if you have a shorter one, just asking)? :) \$\endgroup\$ – Mr. Xcoder Oct 21 '17 at 17:59
  • \$\begingroup\$ No, I believe this is optimal for Actually. \$\endgroup\$ – Mego Oct 21 '17 at 17:59
0
\$\begingroup\$

Python 2, 64 bytes

-4 bytes thanks to H.PWiz.

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

Try it online!

Port of H.PWiz's Haskell answer. I'm only sharing this because I'm proud that I was able to understand this piece of Haskell code and translate it. :P

\$\endgroup\$
  • \$\begingroup\$ Does range(1,n) not work? \$\endgroup\$ – H.PWiz Oct 21 '17 at 18:45
  • \$\begingroup\$ range(1, n) produces all integers in [1, n). \$\endgroup\$ – totallyhuman Oct 21 '17 at 18:46
  • 1
    \$\begingroup\$ Ah, well you don't actually need to go all the way up to n for a \$\endgroup\$ – H.PWiz Oct 21 '17 at 18:47
  • \$\begingroup\$ Oh, okay, I don't completely understand the math behind it. :P Thanks! \$\endgroup\$ – totallyhuman Oct 21 '17 at 18:47
  • 1
    \$\begingroup\$ 64 bytes \$\endgroup\$ – H.PWiz Oct 21 '17 at 18:57
0
\$\begingroup\$

Axiom, 61 bytes

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

This is the first time i find it is possible define the function without the use of () parenthesis. Instead of "f(n)==" "f n==" one character less...

\$\endgroup\$
0
\$\begingroup\$

Racket, 83 79 bytes

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

Try it online!

(I'm not sure if there's a consensus on what constitutes a complete Racket solution, so I'm going with the Mathematica convention that a pure function counts.)

How it works

factorize gives the factorization as a list of pairs: (factorize 108) gives '((2 2) (3 3)). The second element of a pair is given by cadr, a shorthand for the composition of car (head of a list) with cdr (tail of a list).

I feel silly doing (cadr (argmax cadr list)) to find the maximum of the second elements, but max doesn't work on lists: (max (map cadr list)) doesn't do what we want. I'm not an expert in Racket, so maybe there's a standard better way to do this.

Racket, 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))

Try it online!

How it works

An alternative version that doesn't import factorize and instead does everything from scratch, more or less. The function (p m d) finds the highest power of d that divides m and then we just find highest value of (p n d) for d between 2 and n. (We don't need to restrict this to primes, since there will not be a composite power that works better than prime powers.)

\$\endgroup\$
  • \$\begingroup\$ I guess the standard max solution is (apply max (map cadr list) but (cadr (argmax cadr list)) is unfortunately shorter. \$\endgroup\$ – Misha Lavrov Oct 23 '17 at 15:45
0
\$\begingroup\$

J, 9 bytes

[:>./_&q:

Max of <./ all prime exponents _&q:

Try it online!

\$\endgroup\$
0
\$\begingroup\$

APL(NARS), 15 chars, 30 bytes

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

test:

  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 

comment:

{⌈/+/¨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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.