diff options
| author | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2022-04-05 21:25:55 +0100 |
|---|---|---|
| committer | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2022-04-05 21:25:55 +0100 |
| commit | 6aa5c270464f36c0fb846c3dfd8b95db8dc2fa66 (patch) | |
| tree | 590c8cb0b54bb5b8edd3b068694d190d79b12378 /challenge-159/eric-cheung | |
| parent | 2e1b8113ad7946953b23a176db903732ab6c46a5 (diff) | |
| download | perlweeklychallenge-club-6aa5c270464f36c0fb846c3dfd8b95db8dc2fa66.tar.gz perlweeklychallenge-club-6aa5c270464f36c0fb846c3dfd8b95db8dc2fa66.tar.bz2 perlweeklychallenge-club-6aa5c270464f36c0fb846c3dfd8b95db8dc2fa66.zip | |
- Added guest contributions by Eric Cheung.
Diffstat (limited to 'challenge-159/eric-cheung')
| -rwxr-xr-x | challenge-159/eric-cheung/python/ch-1.py | 65 | ||||
| -rwxr-xr-x | challenge-159/eric-cheung/python/ch-2.py | 70 |
2 files changed, 135 insertions, 0 deletions
diff --git a/challenge-159/eric-cheung/python/ch-1.py b/challenge-159/eric-cheung/python/ch-1.py new file mode 100755 index 0000000000..84e4d54b07 --- /dev/null +++ b/challenge-159/eric-cheung/python/ch-1.py @@ -0,0 +1,65 @@ +## Remarks
+## https://www.geeksforgeeks.org/farey-sequence/
+
+## Python3 program to print
+## Farey Sequence of given order
+
+## Class for fraction x / y (a term in farey sequence)
+class Term:
+
+ ## Constructor to initialize
+ ## x and y in x / y
+ def __init__(self, x, y):
+ self.x = x
+ self.y = y
+
+
+## GCD of a and b
+def gcd(a, b):
+ if b == 0:
+ return a
+
+ return gcd(b, a % b)
+
+## Function to print
+## Farey sequence of order n
+def farey(n):
+
+ ## Create a vector to store terms of output
+ v = []
+
+ ## One by one find and store all terms except 0 / 1 and n / n which are known
+ for i in range(1, n + 1):
+ for j in range(i + 1, n + 1):
+
+ ## Checking whether i and j are in lowest term
+ if gcd(i, j) == 1:
+ v.append(Term(i, j))
+
+ ## Sorting the term of sequence
+ for i in range(len(v)):
+ for j in range(i + 1, len(v)):
+ if (v[i].x * v[j].y > v[j].x * v[i].y):
+ v[i], v[j] = v[j], v[i]
+
+ ## Explicitly printing first term
+ print("0 / 1", end = " ")
+
+ ## Printing other terms
+ for i in range(len(v)):
+ print("%d/%d" % (v[i].x, v[i].y), end = " ")
+
+ ## explicitly printing last term
+ print("1/1")
+
+
+# Driver Code
+if __name__ == "__main__":
+ ## n = 5 ## Example 1:
+ ## n = 7 ## Example 2:
+ n = 4 ## Example 3:
+
+ print("Farey sequence of order %d is" % n)
+ farey(n)
+
+## This code is contributed by sanjeev2552
diff --git a/challenge-159/eric-cheung/python/ch-2.py b/challenge-159/eric-cheung/python/ch-2.py new file mode 100755 index 0000000000..4e19c591df --- /dev/null +++ b/challenge-159/eric-cheung/python/ch-2.py @@ -0,0 +1,70 @@ +## Remarks
+## https://www.geeksforgeeks.org/program-mobius-function/
+
+## Python program to evaluate
+## Mobius def M(N) = 1 if N = 1
+## M(N) = 0 if any prime factor of N is contained twice
+## M(N) = (-1) ^ (no of distinct prime factors)
+
+
+import math
+
+
+## def to check if n is prime or not
+def isPrime(n) :
+
+ if (n < 2) :
+ return False
+
+ for i in range(2, n + 1) :
+ if (n % i == 0) :
+ return False
+
+ i = i * i
+
+ return True
+
+
+def mobius(n) :
+
+ p = 0
+
+ ## Handling 2 separately
+ if (n % 2 == 0) :
+
+ n = int(n / 2)
+ p = p + 1
+
+ ## If 2^2 also divides N
+ if (n % 2 == 0) :
+ return 0
+
+ ## Check for all other prime factors
+ for i in range(3, int(math.sqrt(n)) + 1) :
+
+ ## If i divides n
+ if (n % i == 0) :
+
+ n = int(n / i)
+ p = p + 1
+
+ ## If i ^ 2 also divides N
+ if (n % i == 0) :
+ return 0
+
+ i = i + 2
+
+ if(p % 2 == 0) :
+ return -1
+
+ return 1
+
+## Driver Code
+## N = 5 ## Example: 1
+## N = 10 ## Example: 2
+N = 20 ## Example: 3
+
+print ("Mobius defs M(N) at N = {} is: {}\n" . format(N, mobius(N)));
+
+
+## This code is contributed by Manish Shaw (manishshaw1)
|