From 13809215bbd6899853b500386805feffe995bbe4 Mon Sep 17 00:00:00 2001
From: Roger Bell_West <roger@firedrake.org>
Date: Mon, 4 Apr 2022 09:49:42 +0100
Subject: Solutions for challenge #159

---
 challenge-159/roger-bell-west/python/ch-1.py | 50 +++++++++++++++++++
 challenge-159/roger-bell-west/python/ch-2.py | 75 ++++++++++++++++++++++++++++
 2 files changed, 125 insertions(+)
 create mode 100755 challenge-159/roger-bell-west/python/ch-1.py
 create mode 100755 challenge-159/roger-bell-west/python/ch-2.py

(limited to 'challenge-159/roger-bell-west/python')

diff --git a/challenge-159/roger-bell-west/python/ch-1.py b/challenge-159/roger-bell-west/python/ch-1.py
new file mode 100755
index 0000000000..d6e05acf97
--- /dev/null
+++ b/challenge-159/roger-bell-west/python/ch-1.py
@@ -0,0 +1,50 @@
+#! /usr/bin/python3
+
+import unittest
+
+from math import gcd
+from functools import reduce
+
+def lcm(m,n):
+  return m//gcd(m,n)*n
+
+def lcmseries(s):
+  return reduce(lcm, s)
+
+def farey(n):
+  l=lcmseries(range(2,n+1))
+  d=dict()
+  s=[]
+  for i in range(1,n+1):
+    m=l // i
+    for j in range(0,i+1):
+      k=m*j
+      if not k in d:
+        d[k]=[j,i]
+        s.append(k)
+  s.sort()
+  return [d[i] for i in s]
+
+class TestFarey(unittest.TestCase):
+
+        def test_ex1(self):
+          self.assertEqual(farey(5),
+                           [[0,1], [1,5], [1,4], [1,3], [2,5], [1,2],
+                            [3,5], [2,3], [3,4], [4,5], [1,1]],
+                           'example 1')
+
+        def test_ex2(self):
+          self.assertEqual(farey(7),
+                           [[0,1], [1,7], [1,6], [1,5], [1,4], [2,7],
+                            [1,3], [2,5], [3,7], [1,2], [4,7], [3,5],
+                            [2,3], [5,7], [3,4], [4,5], [5,6], [6,7],
+                            [1,1]],
+                           'example 2')
+
+        def test_ex3(self):
+          self.assertEqual(farey(4),
+                           [[0,1], [1,4], [1,3], [1,2], [2,3], [3,4],
+                            [1,1]],
+                           'example 3')
+
+unittest.main()
diff --git a/challenge-159/roger-bell-west/python/ch-2.py b/challenge-159/roger-bell-west/python/ch-2.py
new file mode 100755
index 0000000000..125eed5e55
--- /dev/null
+++ b/challenge-159/roger-bell-west/python/ch-2.py
@@ -0,0 +1,75 @@
+#! /usr/bin/python3
+
+import unittest
+
+from math import sqrt,floor,gcd
+from collections import deque
+
+def genprimes(mx):
+  primesh=set(range(2,4))
+  for i in range(6,mx+2,6):
+    for j in range(i-1,i+2,2):
+      if j <= mx:
+        primesh.add(j)
+  q=deque([2,3,5,7])
+  p=q.popleft()
+  mr=floor(sqrt(mx))
+  while p <= mr:
+    if p in primesh:
+      for i in range(p*p,mx+1,p):
+        primesh.discard(i)
+    if len(q) < 2:
+      q.append(q[-1]+4)
+      q.append(q[-1]+2)
+    p=q.popleft()
+  primes=list(primesh)
+  primes.sort()
+  return primes
+
+def primefactor(n):
+  f=dict()
+  m=n
+  for p in genprimes(floor(sqrt(n))):
+    while (m % p == 0):
+      m //= p
+      if p in f:
+        f[p] += 1
+      else:
+        f[p] = 1
+    if m==1:
+      break
+  if m > 1:
+    if m in f:
+      f[m] += 1
+    else:
+      f[m] = 1
+  return f
+
+def moebius(n):
+  z=0
+  for k,v in primefactor(n).items():
+    if v > 1:
+      return 0
+    z += 1
+  if z % 2 == 0:
+    return 1
+  return -1
+
+class TestMoebius(unittest.TestCase):
+
+        def test_ex1(self):
+          self.assertEqual(moebius(5),
+                           -1,
+                           'example 1')
+
+        def test_ex2(self):
+          self.assertEqual(moebius(10),
+                           1,
+                           'example 2')
+
+        def test_ex3(self):
+          self.assertEqual(moebius(20),
+                           0,
+                           'example 3')
+
+unittest.main()
-- 
cgit