Find the Prime Signature

Question

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 code-golf, so the fewest bytes wins!

Adám · Accepted Answer · 2022-12-29 23:58:48Z

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

Luis Mendo · Accepted Answer · 2022-12-30 00:03:13Z

MATL, 5 bytes

_YFSP

Try at MATL Online!

Explanation

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

chunes · Accepted Answer · 2022-12-30 00:05:02Z

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 — Samathingamajig
– Samathingamajig, Commented Dec 30, 2022 at 0:06

alephalpha · Accepted Answer · 2022-12-30 00:05:03Z

5

PARI/GP, 27 bytes

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

Attempt This Online!

answered Dec 30, 2022 at 0:05

alephalpha

51.9k7 gold badges75 silver badges196 bronze badges

Add a comment |

Neil · Accepted Answer · 2022-12-30 02:00:59Z

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.

The Thonnu · Accepted Answer · 2022-12-31 15:00:14Z

5

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

edited Dec 31, 2022 at 15:00

The Thonnu

18.7k3 gold badges19 silver badges76 bronze badges

answered Dec 29, 2022 at 23:47

lyxal♦

35.6k2 gold badges69 silver badges148 bronze badges

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

Samathingamajig
– Samathingamajig

2022-12-29 23:55:06 +00:00
Commented Dec 29, 2022 at 23:55
\$\begingroup\$ @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 :/ \$\endgroup\$

lyxal
– lyxal ♦

2022-12-29 23:56:54 +00:00
Commented Dec 29, 2022 at 23:56
\$\begingroup\$ @lyxal using a tab character solves the alignment issue \$\endgroup\$

jezza_99
– jezza_99

2022-12-30 01:08:46 +00:00
Commented Dec 30, 2022 at 1:08

Add a comment |

Kip the Malamute · Accepted Answer · 2022-12-30 01:01:25Z

Pyt, 6 9 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 — Samathingamajig
– Samathingamajig, Commented Dec 30, 2022 at 0:10

solid.py · Accepted Answer · 2022-12-30 10:02:15Z

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
– Neil, Commented Dec 30, 2022 at 9:54

Noodle9 · Accepted Answer · 2022-12-30 12:00:18Z

4

SageMath, 45 bytes

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

Try it online!

edited Dec 30, 2022 at 12:00

answered Dec 30, 2022 at 10:25

Noodle9

20.4k3 gold badges23 silver badges47 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2022-12-30 18:14:22Z

4

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)

edited Dec 30, 2022 at 18:14

answered Dec 30, 2022 at 2:16

l4m2

32.5k2 gold badges27 silver badges116 bronze badges

\$\begingroup\$ How do 9999991 took my 10G+ RAM? \$\endgroup\$

l4m2
– l4m2

2022-12-30 02:19:48 +00:00
Commented Dec 30, 2022 at 2:19
\$\begingroup\$ For the 1 test case, this returns [undefined], length 1, which is different from an empty array [], length 0 \$\endgroup\$

Samathingamajig
– Samathingamajig

2022-12-30 02:26:55 +00:00
Commented Dec 30, 2022 at 2:26
\$\begingroup\$ I think you can use n-!w instead of n-1|w. \$\endgroup\$

Arnauld
– Arnauld

2022-12-30 17:51:11 +00:00
Commented Dec 30, 2022 at 17:51

Add a comment |

lyxal · Accepted Answer · 2022-12-29 23:57:45Z

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

Luis Mendo · Accepted Answer · 2022-12-30 00:47:17Z

Octave, 58 51 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

Kevin Cruijssen · Accepted Answer · 2022-12-30 08:03:24Z

05AB1E, 5 bytes

Ó0K{R

Try it online or verify all test cases.

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)

Dominic van Essen · Accepted Answer · 2023-01-08 08:29:39Z

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? — pajonk
– pajonk, Commented Jan 1, 2023 at 16:25

Neil · Accepted Answer · 2022-12-30 00:56:18Z

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.

south · Accepted Answer · 2022-12-30 00:57:59Z

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

Dominic van Essen · Accepted Answer · 2022-12-31 14:44:14Z

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

noodle person · Accepted Answer · 2022-12-31 21:57:55Z

2

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

edited Dec 31, 2022 at 21:57

answered Dec 30, 2022 at 1:55

noodle person

12.6k1 gold badge31 silver badges90 bronze badges

\$\begingroup\$ A quick 8-byter \$\endgroup\$

Shaggy
– Shaggy

2022-12-31 00:17:37 +00:00
Commented Dec 31, 2022 at 0:17
\$\begingroup\$ You can also golf your version down to 11 bytes \$\endgroup\$

Shaggy
– Shaggy

2022-12-31 03:15:23 +00:00
Commented Dec 31, 2022 at 3:15
\$\begingroup\$ 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? \$\endgroup\$

noodle person
– noodle person

2022-12-31 21:52:08 +00:00
Commented Dec 31, 2022 at 21:52
1

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

Shaggy
– Shaggy

2023-01-02 13:39:12 +00:00
Commented Jan 2, 2023 at 13:39
\$\begingroup\$ @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. \$\endgroup\$

noodle person
– noodle person

2023-01-02 22:36:41 +00:00
Commented Jan 2, 2023 at 22:36

| Show 2 more comments

Shaggy · Accepted Answer · 2023-01-03 17:14:52Z

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

DeathIncarnate · Accepted Answer · 2022-12-31 14:39:27Z

Burlesque, 7 bytes

fCf:)-]

Try it online!

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

The Thonnu · Accepted Answer · 2023-03-15 15:34:20Z

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

chunes · Accepted Answer · 2023-04-15 02:42:57Z

1

Arturo, 45 bytes

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

Try it

edited Apr 15, 2023 at 2:42

answered Dec 31, 2022 at 0:08

chunes

27.8k3 gold badges32 silver badges55 bronze badges

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

Samathingamajig
– Samathingamajig

2023-01-01 04:36:09 +00:00
Commented Jan 1, 2023 at 4:36
\$\begingroup\$ @Samathingamajig Fixed it. \$\endgroup\$

chunes
– chunes

2023-04-15 02:43:20 +00:00
Commented Apr 15, 2023 at 2:43

Add a comment |

Aiden Chow · Accepted Answer · 2023-01-13 16:44:10Z

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

emirps · Accepted Answer · 2023-03-15 16:48:42Z

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)

138 Aspen · Accepted Answer · 2023-04-15 03:48:39Z

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

Find the Prime Signature

I/O

Examples/Test Cases

Scoring

25 Answers 25

APL (Dyalog Extended), 6 bytes

MATL, 5 bytes

Explanation

Factor + math.primes.factors, 37 bytes

PARI/GP, 27 bytes

Charcoal, 56 bytes

Vyxal, 4 bytes

Explained

Pyt, 6 9 8 bytes

Python, 71 bytes

Python, 128 bytes

SageMath, 45 bytes

JavaScript (Node.js), 77 bytes

Jelly, 6 bytes

Explained

Octave, 58 51 47 bytes

Explanation

05AB1E, 5 bytes

R, 71 bytes

R, 74 67 bytes

Retina 0.8.2, 59 bytes

J, 12 bytes

Husk, 6 bytes

Japt, 8 bytes

Japt, 8 bytes

Burlesque, 7 bytes

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

Explanation

Arturo, 45 bytes

Desmos, 97 bytes

133 bytes

Stax, 7 bytes

Explanation

Mathematica, 38 bytes

Linked

Related

Hot Network Questions

Factor + `math.primes.factors`, 37 bytes