bc solution for week-079, part 1

1 files changed, 37 insertions, 0 deletions

diff --git a/challenge-079/abigail/bc/ch-1.bc b/challenge-079/abigail/bc/ch-1.bc
new file mode 100644
index 0000000000..bd708a7df8
--- /dev/null
+++ b/challenge-079/abigail/bc/ch-1.bc
@@ -0,0 +1,37 @@
+#
+# Challenge:
+#
+#   You are given a positive number $N.
+#
+#   Write a script to count the total numbrer of set bits of the binary
+#   representations of all numbers from 1 to $N and return
+#   $total_count_set_bit % 1000000007.
+#
+# https://perlweeklychallenge.org/blog/perl-weekly-challenge-079/
+#
+
+#
+# This is A000778 (https://oeis.org/A000788). There's a recursive formala
+# for the number of bits in the binary representation of 0 .. $N:
+#
+#    bits (0) = 0
+#    bits (2 * N)     =     bits (N) + bits (N - 1) + N
+#    bits (2 * N + 1) = 2 * bits (N)                + N + 1
+#
+
+bignum = 1000000007;
+
+define f(nn) {
+    auto n;
+    if (nn == 0) {return (0);}
+    if (nn % 2 == 1) {
+        n = (nn - 1) / 2;
+        return 2 * f(n) + n + 1;
+    }
+    n = nn / 2;
+    return f(n) + f(n - 1) + n;
+}
+
+define main(n) {
+    return f(n) % bignum;
+}