Solutions for challenge #168

2 files changed, 203 insertions, 0 deletions

diff --git a/challenge-168/roger-bell-west/lua/ch-1.lua b/challenge-168/roger-bell-west/lua/ch-1.lua
new file mode 100755
index 0000000000..2b0f43b734
--- /dev/null
+++ b/challenge-168/roger-bell-west/lua/ch-1.lua
@@ -0,0 +1,102 @@
+#! /usr/bin/lua
+
+-- by Michael Anderson at
+-- https://stackoverflow.com/questions/8722620/comparing-two-index-tables-by-index-value-in-lua
+function recursive_compare(t1,t2)
+  -- Use usual comparison first.
+  if t1==t2 then return true end
+  -- We only support non-default behavior for tables
+  if (type(t1)~="table") then return false end
+  -- They better have the same metatables
+  local mt1 = getmetatable(t1)
+  local mt2 = getmetatable(t2)
+  if( not recursive_compare(mt1,mt2) ) then return false end
+
+  -- Check each key-value pair
+  -- We have to do this both ways in case we miss some.
+  -- TODO: Could probably be smarter and not check those we've 
+  -- already checked though!
+  for k1,v1 in pairs(t1) do
+    local v2 = t2[k1]
+    if( not recursive_compare(v1,v2) ) then return false end
+  end
+  for k2,v2 in pairs(t2) do
+    local v1 = t1[k2]
+    if( not recursive_compare(v1,v2) ) then return false end
+  end
+
+  return true  
+end
+
+function isprime(candidate)
+   if candidate<2 then
+      return false
+   elseif candidate==2 then
+      return true
+   elseif candidate==3 then
+      return true
+   elseif candidate % 2 == 0 then
+      return false
+   elseif candidate % 3 == 0 then
+      return false
+   end
+   local anchor=0
+   local limit=math.floor(math.sqrt(candidate))
+   while true do
+      anchor = anchor + 6
+      for t = anchor-1,anchor+1,2 do
+         if t > limit then
+            return true
+         end
+         if candidate % t == 0 then
+            return false
+         end
+      end
+   end
+end
+
+function hammingweight(x0)
+   local x = x0
+   local count = 0
+   while x > 0 do
+      x = x & (x-1)
+      count = count + 1
+   end
+   return count
+end
+
+function perrinprime(n)
+   local out={}
+   local ol = 0
+   local seq = {3, 0, 2}
+   while true do
+      local nv = seq[1] + seq[2]
+      seq[1] = seq[2]
+      seq[2] = seq[3]
+      seq[3] = nv
+      if isprime(nv) then
+         if out[nv] == nil then
+            ol = ol + 1
+         end
+         out[nv] = true
+         if ol >= n then
+            break
+         end
+      end
+   end
+   local o = {}
+   for k,v in pairs(out) do
+      table.insert(o,k)
+   end
+   table.sort(o)
+   return o
+end
+
+if recursive_compare(perrinprime(13), {2, 3, 5, 7, 17, 29, 277, 367,
+                                       853, 14197, 43721, 1442968193,
+                                       792606555396977}) then
+   io.write("Pass")
+else
+   io.write("FAIL")
+end
+print("")
diff --git a/challenge-168/roger-bell-west/lua/ch-2.lua b/challenge-168/roger-bell-west/lua/ch-2.lua
new file mode 100755
index 0000000000..978f8ed462
--- /dev/null
+++ b/challenge-168/roger-bell-west/lua/ch-2.lua
@@ -0,0 +1,101 @@
+#! /usr/bin/lua
+
+function genprimes(mx)
+   local primesh = {}
+   for i = 2, 3 do
+      primesh[i] = true
+   end
+   for i = 6, mx, 6 do
+      for j = i-1, i+1, 2 do
+         if j <= mx then
+            primesh[j]=true
+         end
+      end
+   end
+   local q={2,3,5,7}
+   local p=table.remove(q,1)
+   local mr=math.floor(math.sqrt(mx))
+   while p <= mr do
+      if primesh[p] ~= nil then
+         for i = p*p,mx,p do
+            primesh[i] = nil
+         end
+      end
+      if #q < 2 then
+         table.insert(q,q[#q]+4)
+         table.insert(q,q[#q]+2)
+      end
+      p=table.remove(q,1)
+   end
+   local primes = {}
+   for k,v in pairs(primesh) do
+      table.insert(primes,k)
+   end
+   table.sort(primes)
+   return primes
+end
+
+function primefactor(n)
+   local f={}
+   local m=n
+   for k,p in pairs(genprimes(1+math.floor(math.sqrt(m)))) do
+      while m % p == 0 do
+         m=math.floor(m/p)
+         if f[p] == nil then
+            f[p]=1
+         else
+            f[p] = f[p] + 1
+         end
+         if m==1 then
+            break
+         end
+      end
+   end
+   if m>1 then
+      if f[m] == nil then
+         f[m]=1
+      else
+         f[m] = f[m] + 1
+      end
+   end
+   return f
+end
+
+function homeprime(n0)
+   local n = n0
+   while true do
+      local pfc = 0
+      local ns = ""
+      local t = primefactor(n)
+      local kl = {}
+      for k,v in pairs(t) do
+         pfc = pfc + v
+         table.insert(kl,k)
+      end
+      table.sort(kl)
+      if pfc == 1 then
+         break
+      end
+      for k,v in pairs(kl) do
+         for i = 1,t[v] do
+            ns = ns .. v
+         end
+      end
+      n = 0 + ns
+   end
+   return n
+end
+
+if homeprime(10) == 773 then
+   io.write("Pass")
+else
+   io.write("FAIL")
+end
+io.write(" ")
+
+if homeprime(16) == 31636373 then
+   io.write("Pass")
+else
+   io.write("FAIL")
+end
+print("")