# Find the Prime Signature

The Prime Signature of a number is the list of the exponents of the prime factors of a number, sorted in descending order (exponents of 0 are ignored). Inspired by Combo Class's "The Magnificent Patterns of Prime Signatures" video.

For example, the prime factorization of 6860 is 2 * 2 * 5 * 7 * 7 * 7, or 2^2 + 5^1 + 7^3. The exponents are 2, 1, and 3, so the Prime Signature is {3, 2, 1}

# I/O

You will be given an integer on the interval [1, 10,000,000].

You must output an array/list/vector or a string (in the format below) of the input's prime signature.

# Examples/Test Cases

Numbers Signature
1 ∅ or {}
2, 3, 5, 7, 11 {1}
4, 9, 25, 49, 121 {2}
6, 10, 14, 15, 21 {1, 1}
8, 27, 125, 343 {3}
12, 18, 20, 28 {2, 1}
16, 81, 625, 2401 {4}
24, 40, 54, 56 {3, 1}
30, 42, 66, 70 {1, 1, 1}
32, 243, 3125 {5}
36, 100, 196, 225 {2, 2}
12345 {1, 1, 1}
123456 {6, 1, 1}
1234567 {1, 1}
5174928 {5, 4, 3}
8388608 {23}
9999991 {1}

Note that these are not sets in the computer science sense because they can contain duplicate values and have an ordering (admittedly, some set implementations are ordered).

# Scoring

This is , so the fewest bytes wins!

# APL (Dyalog Extended), 6 bytes

∨2⌷2⍭⊢


Try it online!

∨ descending sort of…

2⌷ the second row of…

2⍭ the table of primes (in the first row) and their exponents (in the second row) of…

⊢ the argument

# MATL, 5 bytes

_YFSP


Try at MATL Online!

### Explanation

_YF   % Implicit input. Prime factor exponents without zeros
S     % Sort
P     % Flip. Implicit display


# Factor + math.primes.factors, 37 bytes

[ group-factors values [ >=< ] sort ]


Try it online!

• group-factors Get the prime factorization of an integer as an assoc where keys are factors and values are exponents.
• values Get the exponents.
• [ >=< ] sort Sort into descending order.
• A language with factor in its name is definitely appropriate for this challenge Commented Dec 30, 2022 at 0:06

# PARI/GP, 27 bytes

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


Attempt This Online!

# Charcoal, 56 bytes

Ｎθ≔²ηＷ⊖θ¿﹪θη≦⊕η«≔⁰ζＷ¬﹪θη«≦⊕ζ≧÷ηθ»⊞υζ»≔⟦⟧ζＷ⁻υζＦ№υ⌈ι⊞ζ⌈ιＩζ


Try it online! Link is to verbose version of code. Explanation:

Ｎθ


Input the integer.

≔²η


Start trial division at 2.

Ｗ⊖θ¿﹪θη≦⊕η


Until the integer has been reduced to 1, keep incrementing the trial divisor until it divides the integer.

«≔⁰ζＷ¬﹪θη«≦⊕ζ≧÷ηθ»⊞υζ»


Calculate the multiplicity of the trial divisor and push it to the predefined empty list.

≔⟦⟧ζＷ⁻υζＦ№υ⌈ι⊞ζ⌈ιＩζ


Sort the list in descending order and output the result.

36 bytes by importing Python modules:

≔▷”8±J≧∕*}G⦃⬤t；⁼hsλ”ＮθＩ⮌▷SＥ▷listθ§θι


Try it online! Link is to verbose version of code. Explanation:

≔▷”8±J≧∕*}G⦃⬤t；⁼hsλ”Ｎθ


Use sympy.ntheory.factorint to get a dictionary of prime factors and their multiplicities.

Ｉ⮌▷SＥ▷listθ§θι


Extract the multiplicities, sort them, and output the reversed result.

This can be reduced to 26 bytes if you run the latest version of Charcoal locally:

Ｉ⮌▷SＥ▷”8±J≧∕*}G⦃⬤t；⁼hsλ”Ｎι


Unfortunately you can't try this online because the version of Charcoal on TIO can't enumerate dictionaries and the version of Charcoal on ATO can't import sympy.

# Vyxal, 4 bytes

∆ǐsṘ


Try it Online!

So uh turns out the prime exponents built-in doesn't include 0s by complete accident - it's not a bug, just a consequence of how it's implemented and a different understanding of what a prime exponents built-in should do lol.

## Explained

∆ǐsṘ
∆ǐ   # prime exponents of the input
s  # sorted
Ṙ # reversed

• Very good! You're missing two spaces, one in each of lines 3-4 of the explanation to keep the character layout, but I can't suggest that edit with the edit button since that change is not at least 6 characters. Commented Dec 29, 2022 at 23:55
• @Samathingamajig I think the characters are misaligned because of the way the ǐ is rendered. I've noticed that happens sometimes when unicode characters aren't exactly monospace :/ Commented Dec 29, 2022 at 23:56
• @lyxal using a tab character solves the alignment issue Commented Dec 30, 2022 at 1:08

# Pyt, 69 8 bytes

Đϼ1\⇹ḋɔŞ


Try it online!

Đ            implicit input (n); duplicate top of stack
ϼ           get the unique prime factors of n
1\        remove any pesky 1s
⇹ḋ      get the prime factors of n (with duplicates)
ɔ     count the number of occurrences of each unique prime factor
Ş    sort in descending order

• Try the 1 testcase. This outputs [1] when it should output [] or similar Commented Dec 30, 2022 at 0:10

# Python, 71 bytes

-4 bytes for both code segments thanks to Neil.
-8 bytes thanks to corvus_192

lambda n:sorted(factorint(n).values())[::-1]
from sympy import*


Attempt This Online!

# Python, 128 bytes

Uses a recursive helper function to calculate the prime factors of a number.
Failed on the test cases 1234567, 9999991 due to RecursionError: maximum recursion depth exceeded

lambda n:sorted(Counter(f(n)).values())[::-1]
f=lambda n,i=2:n//i*[0]and f(n,i+1)if n%i else[i]+f(n//i)
from collections import*


Attempt This Online!

• Reversing the output of sorted using [::-1] saves 4 bytes over ,reverse=1.
– Neil
Commented Dec 30, 2022 at 9:54
• 67 bytes: from sympy import* Commented Dec 30, 2022 at 9:59
• Very interesting use of itertools :p Commented Dec 30, 2022 at 10:31

# SageMath, 45 bytes

lambda n:sorted(e for p,e in factor(n))[::-1]


Try it online!

# JavaScript (Node.js), 77 bytes

f=(n,i=2,w)=>n%i?n-!w?f(n,i+1).concat(w||[]).sort((a,b)=>b-a):[]:f(n/i,i,-~w)


Try it online!

Thank Arnauld for -1 or real[]ify(was two solutions)

• How do 9999991 took my 10G+ RAM?
– l4m2
Commented Dec 30, 2022 at 2:19
• For the 1 test case, this returns [undefined], length 1, which is different from an empty array [], length 0 Commented Dec 30, 2022 at 2:26
• I think you can use n-!w instead of n-1|w. Commented Dec 30, 2022 at 17:51

# Jelly, 6 bytes

ÆE¹ƇṢU


Try it online!

A port of my vyxal answer.

## Explained

ÆE¹ƇṢU
ÆE     # Prime exponents of the input - contains 0s
¹Ƈ   # so filter out those 0s
Ṣ  # sort the list
U # and reverse it


# Octave, 5851 47 bytes

@(n)-sort(-diff(find(diff([0 factor(n) n<2]))))


Try it online!

### Explanation

@(n)                                              % Define anonymous function
factor(n)            % Prime factors of input
[0                      % Prepend 0 and...
n<2]       % ...postpend 1 if n<2, 0 otherwise
diff(                 )      % Consecutive differences
find(                       )     % Indices of nonzeros
diff(                             )    % Consecutive differences
-sort(-                                   )   % Negate, sort, negate


# 05AB1E, 5 bytes

Ó0K{R


Explanation:

Ó      # Get a list of the prime factorization of the (implicit) input-integer
0K    # Remove all 0s
{   # Sort it (from lowest to highest)
R  # Reverse it (from highest to lowest)
# (after which the result is output implicitly)


# R, 71 bytes

f=\(n,m=2,l=0)if(n%%m,-sort(-c(if(l)l,if(n>1)f(n,m+1))),f(n/m,m,l+1))


Attempt This Online!

Recursive function that directly calculates prime exponents, and sorts them on every recursive call (which is unneccessary except for the outermost call, so overflows the stack for large inputs).

# R, 74 67 bytes

Edit: -7 bytes thanks to pajonk

\(n,?=\(n,m)if(n>1)if(n%%m,n?m+1,c(m,n/m?m)))-sort(-table(n?2))


Attempt This Online!

Uses recursive helper function ? to calculate prime factors, and then sorts their exponents a single time (and thus copes with much larger inputs, but at the expense of 3 more bytes of code).

• How about renaming the helper function in the second approach for -7 bytes? Commented Jan 1, 2023 at 16:25
• @pajonk - Thanks! Commented Jan 8, 2023 at 8:29

# Retina 0.8.2, 59 bytes

.+
$* m(+\A(1+)(\1)+$
$1¶$#2
(?=(¶.+))(\1)+$¶$#2
1A
O^#


Try it online! Outputs prime signature on separate lines but link is to test suite that joins on commas for convenience. Explanation:

.+
$*  Convert to unary. m(  Run the rest of the script in multiline mode where $ matches at the end of any line.

+\A(1+)(\1)+1¶$#2  Repeatedly extract the smallest prime factor of the input number. ($#2 is actually one less than the smallest prime factor but it's consistent and we only care about the multiplicities anyway.) As this is slow for large numbers the test suite omits some of the slower cases.

(?=(¶.+))(\1)+$¶$#2


Get the multiplicities of each factor.

1A


Remove the 1 remaining after all of the prime factors have been extracted.

O^#


Sort the multiplicities in descending numeric order.

# J, 12 bytes

__\:~@{:@q:]


Independently found, but essentially a port of Adám's APL answer. An exact port would be 1\:~@{__ q:], at 12 bytes as well.

Attempt This Online!

__\:~@{:@q:]
__       q:]  NB. find prime exponents excluding zero
{:@     NB. take the tail of the result
\:~@        NB. descending sort the result


# Husk, 6 bytes

↔OmLgp


Try it online!

     p  # get the prime factors
g   # group identical elements
mL    # get the length of each group
# (these are the prime exponents)
O      # sort into ascending order
↔       # and reverse


# Japt, 8 bytes

-6 thanks to @Shaggy

k ü mÊñn


Try it

k ü mÊñn
k        Get the prime factors of the input
ü      Group the factors to lists of the same element
mÊ   Map each group to its length
ñn Sort them in descending order

• A quick 8-byter Commented Dec 31, 2022 at 0:17
• You can also golf your version down to 11 bytes Commented Dec 31, 2022 at 3:15
• Thanks @Shaggy. Took me a little while to understand the 8-byte version but I think I got it. So it groups the factors, gets the length of each, and sorts them using the n function? Commented Dec 31, 2022 at 21:52
• Rough explanation: Get the prime factors, group & sort, map lengths and sort by subtracting from 2 (in my version) or by negating (in the version you posted). Commented Jan 2, 2023 at 13:39
• @Shaggy - Can you explain why ñÍ sorts them by subtracting from 2? I realize that Í is a shortcut for n2, but I don't see how the 2 gets passed to n. Also, I thought my version was equivalent to .sort((a,b)=>b-a), is that what you mean by negating or is it doing something else? Thanks. Commented Jan 2, 2023 at 22:36

# Japt, 8 bytes

Gave Jacob my initial solution, so here's an alternative.

k òÎmÊÍÔ


Try it

k òÎmÊÍÔ     :Implicit input of integer
k            :Prime factors
ò          :Partition between elements where
Î         :  The sign of their differences is truthy (non-zero)
m        :Map
Ê       :  Length
Í      :Sort
Ô     :Reverse


# Burlesque, 7 bytes

fCf:)-]


Try it online!

fC   # Prime factors
f:   # Count occurrences
)-]  # Map-Take counts


# Thunno, $$\ 5 \log_{256}(96) \approx \$$ 4.12 bytes

Zhwz;


Attempt This Online!

#### Explanation

Zhwz;  # Implicit input
Zh     # Prime factor exponents
w    # Without zeros
z;  # Reverse-sorted
# Implicit output


# Arturo, 45 bytes

\$=>[factors.prime&|tally|values|sort|reverse]


Try it

• Not sure what happens when ran on a real machine, but when I try the testcase 1 it times out, which would not be an acceptable output Commented Jan 1, 2023 at 4:36
• @Samathingamajig Fixed it. Commented Apr 15, 2023 at 2:43

# Desmos, 97 bytes

A=[2...n]
P=A[∑_{N=3}^A0^{mod(A,N-1)}=0]
L=log_P(gcd(n,P^n))
F=L.sort[L.length...1]
f(n)=F[F>0]


Try It On Desmos!

Try It On Desmos! - Prettified

This theoretically works for all inputs $$\\le19998\$$, but in reality, because of floating point issues, this only works for numbers up to around $$\15\$$ or so.

Below is a version that works for all numbers up to $$\19998\$$, at the cost of a few bytes:

### 133 bytes

A=join([1....5n],n)
P=A[∑_{N=2}^{floor(A^{.5})}0^{mod(A,N)}=0]
L=log_P(gcd(n,P^{floor(log_Pn)}))
F=L.sort[L.length...1]
f(n)=F[F>0]


Try It On Desmos!

Try It On Desmos! - Prettified

# Stax, 7 bytes

òT║≥Q{U


Run and debug it

This is a packed stax program which unpacks to the following 8 bytes:

|n0-or|u


Run and debug it

# Explanation

|n       # list of prime exponents
0-     # remove 0s
o    # sort
r   # reverse
|u # uneval (print array as array)


# Mathematica, 38 bytes

Golfed vesrion, try it online!

f=Reverse@Sort[Last/@FactorInteger@#]&


Ungolfed version

PrimeSignature[n_Integer] := Module[{factorization, exponents},
factorization = FactorInteger[n];
exponents = Last /@ factorization;
Sort[exponents]//Reverse
]

PrimeSignature[6860]//Print
`