20
\$\begingroup\$

For a positive integer n with the prime factorization n = p1^e1 * p2^e2 * ... pk^ek where p1,...,pk are primes and e1,...,ek are positive integers, we can define two functions:

  • Ω(n) = e1+e2+...+ek the number of prime divisors (counted with multiplicity) (A001222)
    • ω(n) = k the number of distinct prime divisors. (A001221)

With those two functions we define the excess e(n) = Ω(n) - ω(n) (A046660). This can be considered as a measure of how close a number is to being squarefree.

Challenge

For a given positive integer n return e(n).

Examples

For n = 12 = 2^2 * 3 we have Ω(12) = 2+1 and ω(12) = 2 and therefore e(12) = Ω(12) - ω(12) = 1. For any squarefree number n we obivously have e(n) = 0. The first few terms are

1       0
2       0
3       0
4       1
5       0
6       0
7       0
8       2
9       1
10      0
11      0
12      1
13      0
14      0
15      0

Some more details in the OEIS wiki.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Maybe clarify that ^ is power \$\endgroup\$
    – Luis Mendo
    Commented Aug 28, 2016 at 12:08
  • 5
    \$\begingroup\$ This is not necessary in my opinion. This symbol is used here and all over the internet, as well as on many calculators and in many programming languages. \$\endgroup\$
    – flawr
    Commented Aug 28, 2016 at 12:11

31 Answers 31

1
2
0
\$\begingroup\$

Vyxal s, 3 bytes

ǐ¯†

Try it Online!

Ports 05AB1E. Vyncode makes the byte count worse.

Explained

ǐ¯†
ǐ    # Prime factors with duplicates
 ¯   # deltas
  †  # vectorised negation
# summed by the s flag   
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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