Use the same function to determine whether a number is a power of 2.

We now use the same algorithm (but implemented in different languages)
to determine whether a number is a power of 2. This replaces the
preprocessed powers of 2, and lookup tables.

12 files changed, 181 insertions, 104 deletions

diff --git a/challenge-136/abigail/awk/ch-1.gawk b/challenge-136/abigail/awk/ch-1.gawk
index c40210446f..12f563a4ea 100644
--- a/challenge-136/abigail/awk/ch-1.gawk
+++ b/challenge-136/abigail/awk/ch-1.gawk
@@ -26,16 +26,19 @@ function gcd (u, v, u_odd, v_odd) {
          :                            gcd(v - u,         u)
 }
 
-#
-# Pre calculate powers of 2. We can do powers up to and including 2^52
-#
-BEGIN {
-    for (i = 1; i <= 52; i ++) {
-        power_of_2 [lshift (1, i)] = 1
-    }
+function is_power_of_n (number, n) {
+    return number <  1 ? 0  \
+         : number == 1 ? 1  \
+         : number %  n ? 0  \
+         : is_power_of_n(number / n, n)
 }
 
+function is_power_of_2 (number) {
+    return is_power_of_n(number, 2)
+}
+                 
 
 {
-    print power_of_2 [gcd($1, $2)] || 0
+    r = gcd($1, $2)
+    print (r > 1 && is_power_of_2(r) ? 1 : 0)
 }
diff --git a/challenge-136/abigail/bash/ch-1.sh b/challenge-136/abigail/bash/ch-1.sh
index 9c3ac91402..857e3b7f7e 100644
--- a/challenge-136/abigail/bash/ch-1.sh
+++ b/challenge-136/abigail/bash/ch-1.sh
@@ -23,18 +23,32 @@ function gcd () {
     fi
 }
 
+function is_power_of_n () {
+    local number=$1
+    local n=$2
+    if   ((number < 1))
+    then is_power_of_n=0
+    elif ((number == 1))
+    then is_power_of_n=1
+    elif ((number % n > 0))
+    then is_power_of_n=0
+    else is_power_of_n $((number / 2)) $n
+    fi
+}
+
+function is_power_of_2 () {
+    is_power_of_n $1 2
+    is_power_of_2=$is_power_of_n
+}
+
 set -f
 
-#
-# Calculate the powers of 2 (greater than 1). 2^62 is the max a bash
-# integer holds
-#
-declare -a power_of_2
-for ((i = 1; i <= 62; i ++))
-do  power_of_2[$((1 << i))]=1
-done
 
 while read n m
 do   gcd $n $m
-     echo ${power_of_2[$gcd]:-0}
+     is_power_of_2 $gcd
+     if ((gcd > 1 && is_power_of_2 == 1))
+     then echo 1
+     else echo 0
+     fi
 done
diff --git a/challenge-136/abigail/bc/ch-1.bc b/challenge-136/abigail/bc/ch-1.bc
index 8f9f92486b..9a0c347386 100644
--- a/challenge-136/abigail/bc/ch-1.bc
+++ b/challenge-136/abigail/bc/ch-1.bc
@@ -14,17 +14,22 @@ define g (a, b) {
                 return a 
 }
 
-define p (n) {
-    if (n < 1) {return 0}
-    while (n % 2 == 0) n = n / 2
-    return n == 1
+define p (n, m) {
+    if (n <  1)    {return 0}
+    if (n == 1)    {return 1}
+    if (n % m > 0) {return 0}
+                    return p (n / m, m)
+}
+
+define q (n) {
+    return p (n, 2)
 }
 
 while (1) {
     n = read (); if (n == 0) {break}
     m = read (); if (m == 0) {break}
     r = g (n, m)
-    r > 1 && p (r)
+    r > 1 && q (r)
 }
 
 quit
diff --git a/challenge-136/abigail/c/ch-1.c b/challenge-136/abigail/c/ch-1.c
index 57acd46d89..d1c218aee5 100644
--- a/challenge-136/abigail/c/ch-1.c
+++ b/challenge-136/abigail/c/ch-1.c
@@ -1,6 +1,7 @@
 # include <stdlib.h>
 # include <stdio.h>
 # include <string.h>
+# include <stdbool.h>
 
 /*
  * See ../README.md
@@ -28,25 +29,24 @@ long long gcd (long long u, long long v) {
          :                    gcd (v - u,  u);
 }
 
+bool is_power_of_n (long long number, long long n) {
+    return number <  1 ? false
+         : number == 1 ? true
+         : number %  n ? false
+         : is_power_of_n (number / n, n);
+}
+bool is_power_of_2 (long long number) {
+    return is_power_of_n (number, 2);
+}
+     
+
 
 int main (void) {
     long long n, m;
 
     while (scanf ("%lld %lld", &n, &m) == 2) {
-        long long ggcd = gcd (n, m);
-        short valid = 0;
-        /*
-         * Check whether ggcd is a power of 2
-         */
-        if (ggcd > 1) {
-            while (ggcd % 2 == 0) {
-                ggcd /= 2;
-            }
-            if (ggcd == 1) {
-                valid = 1;
-            }
-        }
-        printf ("%d\n", valid);
+        long long r = gcd (n, m);
+        printf ("%d\n", r > 1 && is_power_of_2 (r) ? 1 : 0);
     }
 
     return (0);
diff --git a/challenge-136/abigail/go/ch-1.go b/challenge-136/abigail/go/ch-1.go
index edb0536a2d..6c9e59ab1b 100644
--- a/challenge-136/abigail/go/ch-1.go
+++ b/challenge-136/abigail/go/ch-1.go
@@ -29,19 +29,24 @@ func gcd (u int, v int) int {
                            return gcd (v - u,  u)
 }
 
-func main () {
-    var power_of_2 map [int] int = make (map [int] int)
-    for i := 1; i < 62; i ++ {
-        power_of_2 [i << 1] = 1
-    }
+func is_power_of_n (number int, n int) bool {
+    if (number <  1)     {return false}
+    if (number == 1)     {return true}
+    if (number % n != 0) {return false}
+                          return is_power_of_n (number / n, n)
+}
+func is_power_of_2 (number int) bool {
+    return is_power_of_n (number, 2)
+}
 
+func main () {
     for {
         var n, m int
         c, err := fmt . Scanf ("%d %d", &n, &m);
         if c != 2 || err != nil {
             break;
         }
-        if _, ok := power_of_2 [gcd (m, n)]; ok {
+        if r := gcd (m, n); r > 1 && is_power_of_2 (r) {
             fmt . Print ("1\n")
         } else {
             fmt . Print ("0\n")
diff --git a/challenge-136/abigail/lua/ch-1.lua b/challenge-136/abigail/lua/ch-1.lua
index 1c3e149da6..44ea00f251 100644
--- a/challenge-136/abigail/lua/ch-1.lua
+++ b/challenge-136/abigail/lua/ch-1.lua
@@ -18,22 +18,21 @@ function gcd (a, b)
                    return gcd (b, a % b)
 end
 
---
--- Precalculate all the relevant powers of 2. Note that in pre 5-3 lua
--- integers are doubles, and start losing precision at 2^53, so we go
--- up to 2^52.
---
-local power_of_2 = {}
-local power      = 1
-for i = 1, 52 do
-    power = power * 2
-    power_of_2 [power] = 1
+function is_power_of_n (number, n)
+    if number <  1    then return false end
+    if number == 1    then return true  end
+    if number % n > 1 then return false end
+                      return (is_power_of_n (number / n, n))
 end
 
+function is_power_of_2 (number)
+    return is_power_of_n (number, 2)
+end
 
 for line in io . lines () do
     local _, _, n, m = line : find ("([0-9]+)%s+([0-9]+)")
-    if power_of_2 [gcd (tonumber (n), tonumber (m))] then
+    local r = gcd (tonumber (n), tonumber (m))
+    if r > 1 and is_power_of_2 (r) then
         print (1)
     else
         print (0)
diff --git a/challenge-136/abigail/node/ch-1.js b/challenge-136/abigail/node/ch-1.js
index 1fb04ad1c4..af49fa3977 100644
--- a/challenge-136/abigail/node/ch-1.js
+++ b/challenge-136/abigail/node/ch-1.js
@@ -18,19 +18,26 @@ function gcd (a, b) {
                  return gcd (b, a % b)
 }
 
-//
-// Precalculate the powers of 2. We're losing precision around 2^53
-//
-let power_of_2 = {};
-let power = 1;
-for (let i = 1; i < 53; i ++) {
-    power *= 2;
-    power_of_2 [power] = 1;
+function is_power_of_n (number, n) {
+    if (number <  1) {return false}
+    if (number == 1) {return true}
+    if (number %  n) {return false}
+                      return is_power_of_n (number / n, n)
+}
+
+function is_power_of_2 (number) {
+    return is_power_of_n (number, 2)
 }
 
   require ('readline')
 . createInterface ({input: process . stdin})   
 . on              ('line', line => {
     let [m, n] = line . trim () . split (' ') . map (x => +x)
-    console . log (power_of_2 [gcd (m, n)] || 0)
+    let  r     = gcd (m, n)
+    if (r > 1 && is_power_of_2 (r)) {
+        console . log (1)
+    }
+    else {
+        console . log (0)
+    }
 })
diff --git a/challenge-136/abigail/perl/ch-1.pl b/challenge-136/abigail/perl/ch-1.pl
index 445d00a1fd..ac0b598577 100644
--- a/challenge-136/abigail/perl/ch-1.pl
+++ b/challenge-136/abigail/perl/ch-1.pl
@@ -22,11 +22,6 @@ use experimental 'lexical_subs';
 # for instance in weeks 82, 89 and 93.
 # So, we copy-and-pasted some code.
 #
-# We could write some code to check whether a number is a power of 2.
-# But there are only 63 powers of 2 which fit in a 64 bit integer, one
-# of them being 1. So, we can just precalculate the ones we're interested in.
-#
-my %power_of_2 = map {1 << $_ => 1} 1 .. 62;
 
 #
 # Find the GCD, using Stein's algorithm
@@ -45,6 +40,25 @@ sub gcd ($u, $v) {
 }
 
 #
+# Return true of $number is a power of $n, that is
+# $number == $n ^ $p for some non-negative integer $p
+#
+sub is_power_of_n ($number, $n) {
+    use integer;
+    $number <  1 ? 0
+  : $number == 1 ? 1
+  : $number % $n ? 0
+  : is_power_of_n ($number / $n, $n)
+}
+
+sub is_power_of_2 ($number) {
+    is_power_of_n ($number, 2)
+}
+
+#
 # Main program
 #
-say $power_of_2 {gcd split} || 0 while <>;
+while (<>) {
+    my  $r = gcd split;
+    say $r > 1 && is_power_of_2 ($r) ? 1 : 0
+}
diff --git a/challenge-136/abigail/python/ch-1.py b/challenge-136/abigail/python/ch-1.py
index 86da426994..0c27429811 100644
--- a/challenge-136/abigail/python/ch-1.py
+++ b/challenge-136/abigail/python/ch-1.py
@@ -11,13 +11,22 @@
 import fileinput
 import math
 
+def is_power_of_n (number, n):
+    if number < 1:
+        return False
+    if number == 1:
+        return True
+    if number % n:
+        return False
+    return is_power_of_n (number / n, n)
+
+def is_power_of_2 (number):
+    return is_power_of_n (number, 2)
+
 for line in fileinput . input ():
     m, n = line . strip () . split (' ')
-    gcd = math . gcd (int (m), int (n))
-    valid = 0
-    if gcd > 1:
-        while gcd % 2 == 0:
-            gcd = gcd / 2
-        if gcd == 1:
-            valid = 1
-    print (valid)
+    r = math . gcd (int (m), int (n))
+    if r > 1 and is_power_of_2 (r):
+        print (1)
+    else:
+        print (0)
diff --git a/challenge-136/abigail/ruby/ch-1.rb b/challenge-136/abigail/ruby/ch-1.rb
index 72ef8542f1..aa050a843e 100644
--- a/challenge-136/abigail/ruby/ch-1.rb
+++ b/challenge-136/abigail/ruby/ch-1.rb
@@ -8,18 +8,20 @@
 # Run as: ruby ch-1.rb < input-file
 #
 
+def is_power_of_n (number, n)
+    return number <  1    ? false
+         : number == 1    ? true
+         : number % n > 0 ? false
+         : is_power_of_n(number / n, n)
+end
+
+def is_power_of_2 (number)
+    return is_power_of_n(number, 2)
+end
+
 ARGF . each_line do
     | line |
     m, n = line . split . map {|x| x . to_i}
-    gcd = m . gcd (n)
-    valid = 0
-    if gcd > 1 then
-        while gcd % 2 == 0 do
-            gcd /= 2
-        end
-        if gcd == 1 then
-            valid = 1
-        end
-    end
-    puts (valid)
+    r = m . gcd (n)
+    puts (r > 1 && is_power_of_2(r) ? 1 : 0)
 end
diff --git a/challenge-136/abigail/scheme/ch-1.scm b/challenge-136/abigail/scheme/ch-1.scm
index 3e9728abbf..d537b754e0 100644
--- a/challenge-136/abigail/scheme/ch-1.scm
+++ b/challenge-136/abigail/scheme/ch-1.scm
@@ -24,19 +24,29 @@
 )
 
 ;;;
-;;; Return #t if n is a power of 2, other than 1
-;;;
-(define (is-power-of-2 n)
-    (cond ((= (modulo n 2) 1) #f)
-          ((= n 2) #t)
-          (else (is-power-of-2 (/ n 2)))))
+;;; Return #t if number is a power of n, that is, number == n ^ p
+;;; for some non-negative integer p. Return #f otherwise.
+;;;
+(define (is-power-of-n number n)
+    (cond ((< number 1) #f)
+          ((= number 1) #t)
+          ((> (modulo number n) 0) #f)
+          (else (is-power-of-n (/ number n) n)))
+)
+
+(define (is-power-of-2 number)
+    (is-power-of-n number 2)
+)
 
 (define (main)
     (define m (read))
     (define n (read))
+    (define r)
     (if (not (eof-object? m))
         (begin
-            (display (if (is-power-of-2 (gcd m n)) 1 0))(newline)
+            (set! r (gcd m n))
+            (display (if (and (> r 1) (is-power-of-2 r)) 1 0))
+            (newline)
             (main)
         )
     )
diff --git a/challenge-136/abigail/tcl/ch-1.tcl b/challenge-136/abigail/tcl/ch-1.tcl
index 53a25f8956..39210c7e16 100644
--- a/challenge-136/abigail/tcl/ch-1.tcl
+++ b/challenge-136/abigail/tcl/ch-1.tcl
@@ -30,18 +30,27 @@ proc gcd {u v} {
     return [gcd [expr $v - $u] $u]
 }
 
+#  
+# Return 1 if number is a power of n, that is, number == n ^ p   
+# for some non-negative integer p. Return 0 otherwise.   
+#
+proc is_power_of_n {number n} {
+    if {$number <  1} {return 0}
+    if {$number == 1} {return 1}
+    if {$number % $n} {return 0}
+                       return [is_power_of_n [expr $number / $n] $n]
+}
+
+proc is_power_of_2 {number} {
+    return [is_power_of_n $number 2]
+}
 
 while {[gets stdin line] >= 0} {
     lassign [split $line " "] m n
-    set ggcd [gcd $m $n]
-    set valid 0
-    if {$ggcd > 1} {
-        while {$ggcd % 2 == 0} {
-            set ggcd [expr $ggcd / 2]
-        }
-        if {$ggcd == 1} {
-            set valid 1
-        }
+    set r [gcd $m $n]
+    if {$r > 1 && [is_power_of_2 $r]} {
+        puts 1
+    } else {
+        puts 0
     }
-    puts $valid
 }