Perl solution for Week 79.

1 files changed, 51 insertions, 0 deletions

diff --git a/challenge-079/abigail/perl/ch-1.pl b/challenge-079/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..a2a8d27818
--- /dev/null
+++ b/challenge-079/abigail/perl/ch-1.pl
@@ -0,0 +1,51 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+#
+# 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
+#
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+use integer;
+
+my $BIG_NUM = 1_000_000_007;
+
+sub bits ($n) {
+    state $bits;
+    $$bits {$n} ||= 
+        $n == 0 ? 0
+      : do {
+            my $half = int ($n / 2);
+            bits ($half) + $half + ($n % 2 ? bits ($half) + 1
+                                           : bits ($half - 1))
+      }
+}
+
+say bits (<>) % $BIG_NUM;
+
+
+__END__