FilesExpand file tree

 patch-1

/

MobiusFunction.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

40 lines (36 loc) · 813 Bytes

 patch-1

/

MobiusFunction.py

Top

File metadata and controls

• Code
• Blame

40 lines (36 loc) · 813 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

def is_square_free(factors):

'''

This functions takes a list of prime factors as input.

returns True if the factors are square free.

'''

for i in factors:

if factors.count(i) > 1:

return False

return True

def prime_factors(n):

'''

Returns prime factors of n as a list.

'''

i = 2

factors = []

while i * i <= n:

if n % i:

i += 1

else:

n //= i

factors.append(i)

if n > 1:

factors.append(n)

return factors

def mobius_function(n):

'''

Defines Mobius function

'''

factors = prime_factors(n)

if is_square_free(factors):

if len(factors) % 2 == 0:

return 1

elif len(factors) % 2 != 0:

return -1

else:

return 0