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.

Improve this question
\$\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

Reset to default
1
2
7
\$\begingroup\$

MATL, 7 5 bytes

Yfd~s

Try it online! Or verify all test cases.

Explanation

Yf    % Implicit input. Obtain prime factors, sorted and with repetitions
d     % Consecutive differences
~     % Logical negate: zeros become 1, nonzeros become 0
s     % Sum. Implicit display
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I was not aware how factor works in MATL, really cool=) \$\endgroup\$
    – flawr
    Commented Aug 28, 2016 at 12:19
  • \$\begingroup\$ @flawr Do you mean YF (in the 7-byte version of the code) or Yf (5-byte)? The latter is as in MATLAB \$\endgroup\$
    – Luis Mendo
    Commented Aug 28, 2016 at 12:20
  • 1
    \$\begingroup\$ The function for the exponents, the 5 byte now is even more clever=) \$\endgroup\$
    – flawr
    Commented Aug 28, 2016 at 12:22
7
\$\begingroup\$

Brachylog, 11 bytes

$pPd:Pr:la-

Try it online!

Explanation

$pP            P is the list of prime factors of the Input
  Pd           Remove all duplicates in P
    :Pr        Construct the list [P, P minus duplicates]
       :la     Apply "length" to the two elements of that list
          -    Output is the subtraction of the first element by the second one
Improve this answer
\$\endgroup\$
7
\$\begingroup\$

Mathematica, 23 bytes

PrimeOmega@#-PrimeNu@#&

Very boring. FactorInteger already takes up 13 bytes, and I can't see much that can be done with the remaining 10.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Jelly, 5 bytes

ÆfI¬S

Try it online!

Verify all testcases.

Port of Luis Mendo's answer in MATL.

ÆfI¬S

Æf     Implicit input. Obtain prime factors, sorted and with repetitions
  I    Consecutive differences
   ¬   Logical negate: zeros become 1, nonzeros become 0
    S  Sum. Implicit display
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ For the previous approach, ÆF’SṪ would have worked I think \$\endgroup\$
    – Sp3000
    Commented Aug 28, 2016 at 12:31
  • \$\begingroup\$ @Sp3000 You should post that \$\endgroup\$
    – Leaky Nun
    Commented Aug 28, 2016 at 12:32
  • \$\begingroup\$ @LeakyNun I was trying to port it myself, but the definition of ¬ confused me. I didn't know it vectorized \$\endgroup\$
    – Luis Mendo
    Commented Aug 28, 2016 at 12:42
  • \$\begingroup\$ @LuisMendo Indeed the Jelly docs are messy. \$\endgroup\$
    – Leaky Nun
    Commented Aug 28, 2016 at 12:45
4
\$\begingroup\$

J, 11 10 bytes

Saved 1 byte thanks to Jonah.

1#.1-~:@q:
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 1#.1-~:@q: for 10 bytes. nice idea using ~: btw. \$\endgroup\$
    – Jonah
    Commented Feb 4, 2019 at 17:32
3
\$\begingroup\$

05AB1E, 6 bytes

Òg¹fg-

Explanation

Òg      # number of prime factors with duplicates
     -  # minus
  ¹fg   # number of prime factors without duplicates

Try it online!

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Haskell, 65 bytes

(c%x)n|x>n=c|mod n x>0=c%(x+1)$n|y<-div n x=(c+0^mod y x)%x$y
0%2
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ if that is one function: who is the input variable? who is the output? thank u... \$\endgroup\$
    – user58988
    Commented Aug 30, 2016 at 21:09
  • \$\begingroup\$ (%) takes 3 input variables : an accumulator (c), an integer (x) and an integer (n) . It returns the excess of (n) when c is set to 0 and x to 2. So (0%2) is a partial function that takes n and returns its excess \$\endgroup\$
    – Damien
    Commented Aug 31, 2016 at 5:58
3
\$\begingroup\$

05AB1E, 4 bytes

Ò¥_O

Port of @LuisMendo's MATL answer.

Try it online or verify the first 15 test cases.

Explanation:

Ò       # Get all prime factors with duplicates from the (implicit) input
        # (automatically sorted from lowest to highest)
 ¥      # Get all deltas
  _     # Check if it's equal to 0 (0 becomes 1; everything else becomes 0)
   O    # Take the sum (and output implicitly)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Husk, 5 4 bytes

ΣẊ=p

Try it online!

-1 byte from Dominic Van Essen.

Improve this answer
\$\endgroup\$
1
2
\$\begingroup\$

Pyth, 7 bytes

-lPQl{P

Try it online.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

C, 74 bytes

f(n,e,r,i){r=0;for(i=2;n>1;i++,r+=e?e-1:e)for(e=0;n%i<1;e++)n/=i;return r;}

Ideone it!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 2, 57 56 bytes

f=lambda n,k=2:n/k and[f(n,k+1),(n/k%k<1)+f(n/k)][n%k<1]

Thanks to @JonathanAllan for golfing off 1 byte!

Test it on Ideone.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Ah nice - you can save a byte by using n/k%k<1 \$\endgroup\$
    – Jonathan Allan
    Commented Aug 28, 2016 at 22:40
  • \$\begingroup\$ Right, n is already divisible by k at that point. Thanks! \$\endgroup\$
    – Dennis
    Commented Aug 28, 2016 at 23:01
1
\$\begingroup\$

Python 2, 100 99 98 96 bytes

n=input()
i=2
f=[]
while i<n:
 if n%i:i+=1
 else:n/=i;f+=i,
if-~n:f+=n,
print len(f)-len(set(f))

Most of the code is taken up by a golfed version of this SO answer, which stores the prime factors of the input in f. Then we simply use set manipulation to calculate the excess factors.

Thanks to Leaky Nun for saving 1 3 bytes!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Brachylog, 11 bytes

$p@b:la:-a+

Try it online!

Verify all testcases. (The wrapper is longer than the function...)

$p@b:la:-a+

$p            prime factorization
  @b          group blocks of equal elements
    :la       length of each
       :-a    each minus 1
          +   sum
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

S.I.L.O.S, 113 bytes

readIO
t=2
lbla
e=0
GOTO b
lblc
i/t
e+1
lblb
m=i
m%t
n=1
n-m
if n c
d=e
d/d
e-d
r+e
A=i
A-1
t+1
if A a
printInt r

Try it online!

A port of my answer in C.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ So so close to beating C :( \$\endgroup\$
    – Rohan Jhunjhunwala
    Commented Aug 28, 2016 at 15:55
1
\$\begingroup\$

Javascript (ES6), 53 51 46 bytes

e=(n,i=2)=>i<n?n%i?e(n,i+1):e(n/=i,i)+!(n%i):0

Saved 5 bytes thanks to Neil

Example:

e=(n,i=2)=>i<n?n%i?e(n,i+1):e(n/=i,i)+!(n%i):0

// computing e(n) for n in [1, 30]
for(var n = 1, list = []; n <= 30; n++) {
  list.push(e(n));
}
console.log(list.join(','));

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can save 5 bytes by calculating r recursively: f=(n,i=2)=>i<n?n%i?f(n,i+1):f(n/=i,i)+!(n%i):0. \$\endgroup\$
    – Neil
    Commented Aug 28, 2016 at 17:09
1
\$\begingroup\$

Bash, 77 bytes

IFS=$'\n '
f=(`factor $1`)
g=(`uniq<<<"${f[*]}"`)
echo $((${#f[*]}-${#g[*]}))

Complete program, with input in $1 and output to stdout.

We set IFS to begin with a newline, so that the expansion "${f[*]}" is newline-separated. We use arithmetic substitution to print the difference between the number of words in the factorisation with the result of filtering through uniq. The number itself is printed as a prefix by factor, but it is also present after filtering, so falls out in the subtraction.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt, 6 bytes

k äÎxÌ

Try it

k äÎxÌ     :Implicit input of integer
k          :Prime factors
  ä        :Consecutive pairs reduced by
   Î       :  Signs of differences (0 or -1)
    x      :Sum of
     Ì     :  Signs of differences with -1 (0 -> 1 and -1 -> 0)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Factor + math.primes.factors math.unicode, 40 bytes

[ group-factors unzip Σ swap length - ]

Attempt This Online!

               ! 12
group-factors  ! { { 2 2 } { 3 1 } }
unzip          ! { 2 3 } { 2 1 }
Σ              ! { 2 3 } 3
swap           ! 3 { 2 3 }
length         ! 3 2
-              ! 1
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Pyt, 4 bytes

ḋ₋¬Ʃ

Try it online!

Port of Leaky Nun's Jelly answer

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 87 bytes

import Data.Numbers.Primes
import Data.List
x=(\x->length x-length(nub x)).primeFactors

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Kamilalisp, 15 bytes

[-&[⍴] #0 ⊙]@⋔⌹

Attempt This Online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Nekomata, 3 bytes

ƒ←∑

Attempt This Online!

ƒ       Factor; returns a list of unique prime factors and a list of their exponents
 ←      Decrement the exponents
  ∑     Sum
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby -rprime, 31 bytes

->n{n.prime_division.sum{_2-1}}

Attempt This Online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Python, (with sympy) 66 bytes

import sympy;lambda n:sum(x-1for x in sympy.factorint(n).values())

sympy.factorint returns a dictionary with factors as keys and their multiplicities as values, so the sum of the values is Ω(n) and the number of values is ω(n), so the sum of the decremented values is what we want.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

CJam, 11 bytes

ri_mf,\mF,-

Try it online!

Explanation

ri_         Get an integer from input and duplicate it
   mf,      Get the number of prime factors (with repetition)
      \     Swap top 2 elements on the stack
       mF,  Get the number of prime factors (with exponents)
          - Subtract
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

C, 158

#define G(a,b) if(a)goto b
#define R return
f(n,i,j,o,w){if(!n)R 0;o=w=i=j=0;a:i+=2;b:if(n%i==0){++j;G(n/=i,b);}o+=!!j;w+=j;i+=(i==2);j=0;G(i*i<n,a);R w-o;}

In the start there is the goto instruction... even if this is more long than yours it is more readable and right [if i not consider n too much big...] one Language that has 10000 library functions is wrost than a Language that with few, 20 or 30 library functions can do all better [because we can not remember all these functions]

#define F for
#define P printf

main(i,r)
{F(i=0; i<100; ++i)
   r=f(i,0,0,0,0),P("[%u|%u]",i,r);
 R  0;
}

/*
 158
 [0|0][1|0][2|0][3|0][4|1][5|0][6|0][7|0][8|2]
 [9|0][10|0][11|0][12|1][13|0][14|0][15|0][16|3]
 [17|0][18|0][19|0][20|1][21|0][22|0][23|0][24|2][25|1][26|0][27|0] [28|1]
 [29|0][30|0][31|0][32|4][33|0][34|0][35|0][36|1]
 [37|0][38|0][39|0][40|2][41|0]
 */
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

GNU sed + coreutils, 55 bytes

(including +1 for -r flag)

s/^/factor /e
s/ ([^ ]+)(( \1)*)/\2/g
s/[^ ]//g
y/ /1/

Input in decimal, on stdin; output in unary, on stdout.

Explanation

#!/bin/sed -rf

# factor the number
s/^/factor /e
# remove first of each number repeated 0 or more times
s/ ([^ ]+)(( \1)*)/\2/g
# count just the spaces
s/[^ ]//g
y/ /1/
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

APL(NARS) 35 chars, 70 bytes

{⍵=1:0⋄k-⍨+/+/¨{w=⍵⊃v}¨⍳k←≢v←∪w←π⍵}

the function π find the factorization in prime of its argument; there is few to say it seems clear, but for me does more operations (from factorization) than the minimum...the range of count characters is out golfing languages because it seems too much count, but less than not golfing languages... test:

  f←{⍵=1:0⋄k-⍨+/+/¨{w=⍵⊃v}¨⍳k←≢v←∪w←π⍵}
  f¨1..15
0 0 0 1 0 0 0 2 1 0 0 1 0 0 0
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Arturo, 47 bytes

$=>[k:tally factors.prime&(∑values k)-size k]

Try it!

Improve this answer
\$\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.