sgreen solutions to challenge 175

5 files changed, 256 insertions, 0 deletions

diff --git a/challenge-175/sgreen/blog.txt b/challenge-175/sgreen/blog.txt
new file mode 100644
index 0000000000..6c0fe917cc
--- /dev/null
+++ b/challenge-175/sgreen/blog.txt
@@ -0,0 +1 @@
+https://dev.to/simongreennet/totient-numbers-on-a-sunday-5fnc
\ No newline at end of file
diff --git a/challenge-175/sgreen/perl/ch-1.pl b/challenge-175/sgreen/perl/ch-1.pl
new file mode 100755
index 0000000000..632ae593c4
--- /dev/null
+++ b/challenge-175/sgreen/perl/ch-1.pl
@@ -0,0 +1,25 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature 'say';
+use experimental 'signatures';
+
+use Date::Calc (qw(This_Year Days_in_Month Day_of_Week));
+
+# Use the year provided or the current year if it wasn't
+sub main ( $year = This_Year() ) {
+
+    foreach my $month ( 1 .. 12 ) {
+        # Get the number of days in a month
+        my $last_day = Days_in_Month( $year, $month );
+
+        # Get the day of week of the last day (Monday is 1, Sunday is 7)
+        my $dow = Day_of_Week( $year, $month, $last_day );
+
+        # Take off the number of days to get last Sunday
+        say sprintf '%d-%02d-%02d', $year, $month, $last_day - $dow % 7;
+    }
+}
+
+main(@ARGV);
diff --git a/challenge-175/sgreen/perl/ch-2.pl b/challenge-175/sgreen/perl/ch-2.pl
new file mode 100755
index 0000000000..107eb35f2b
--- /dev/null
+++ b/challenge-175/sgreen/perl/ch-2.pl
@@ -0,0 +1,108 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature (qw(say state));
+use experimental 'signatures';
+use List::Util 'none';
+
+our @primes = ();
+
+sub is_prime ($number) {
+    # Return true or false if the number is a prime
+    if ( $number < 2 ) {
+        return;
+    }
+
+    foreach my $i (@primes) {
+        if ( $number % $i == 0 ) {
+            return;
+        }
+    }
+
+    # It's a prime
+    return 1;
+}
+
+sub get_factors ($num) {
+    # Get the prime factors that make up the numbers
+    state %factors = ();
+
+    if ( not exists $factors{$num} ) {
+        $factors{$num} = [];
+
+        foreach my $p (@primes) {
+            push @{ $factors{$num} }, $p if $num % $p == 0;
+        }
+    }
+
+    return $factors{$num};
+}
+
+sub get_totients ($num) {
+    state %totients = ();
+    # Count the number of values between 1 and num-1 that has the gcd of 1
+
+    # If we've calculated this before, return the result
+    if ( not exists $totients{$num} ) {
+        my $factors = get_factors($num);
+        my %primes  = map { $_, 1 } @$factors;
+
+        my $count = 0;
+        foreach my $n ( 1 .. $num - 1 ) {
+            # Count this number if it has no common factors (other than 1)
+            $factors = get_factors($n);
+            ++$count if none { $primes{$_} } @$factors;
+        }
+
+        # Store the result when we need it again
+        $totients{$num} = $count;
+    }
+
+    return $totients{$num};
+}
+
+sub is_ptn ($num) {
+    # Return whether this number is a perfect totient number
+
+    # Keep a count of the total
+    my $totals = 0;
+
+    # Loop until we get to one
+    my $n = $num;
+    while ( $n > 1 ) {
+        my $totient = get_totients($n);
+        $totals += $totient;
+
+        if ( $totals > $num ) {
+            # Short circuit exit if we know it will be False
+            return;
+        }
+
+        $n = $totient;
+    }
+
+    return $totals == $num ? 1 : 0;
+}
+
+sub main {
+    my @solutions = ();
+    my $number    = 0;
+
+    # Loop until we have 20 solutions
+    while ( scalar(@solutions) < 20 ) {
+        $number++;
+
+        if ( is_prime($number) ) {
+            push @primes, $number;
+        }
+
+        if ( is_ptn($number) ) {
+            push @solutions, $number;
+        }
+    }
+
+    say join ', ', @solutions;
+}
+
+main();
\ No newline at end of file
diff --git a/challenge-175/sgreen/python/ch-1.py b/challenge-175/sgreen/python/ch-1.py
new file mode 100755
index 0000000000..9c99981d3b
--- /dev/null
+++ b/challenge-175/sgreen/python/ch-1.py
@@ -0,0 +1,25 @@
+#!/usr/bin/env python3
+
+import sys
+from datetime import date, timedelta
+from dateutil.relativedelta import relativedelta
+
+
+def main(arg):
+    # Use the year provided or the current year if it wasn't
+    year = int(arg[0]) if len(arg) else date.today().year
+
+    for m in range(12):
+        # Get the last day of each month
+        dt = date(year, 1+m, 1) + relativedelta(months=1) - timedelta(days=1)
+
+        # Get the day of week (Monday is 1, Sunday is 7)
+        dow = dt.isoweekday()
+
+        # Take off the number of days to get last Sunday
+        last_sunday = dt-timedelta(days=dow % 7)
+        print(last_sunday.isoformat())
+
+
+if __name__ == '__main__':
+    main(sys.argv[1:])
diff --git a/challenge-175/sgreen/python/ch-2.py b/challenge-175/sgreen/python/ch-2.py
new file mode 100755
index 0000000000..a04379a679
--- /dev/null
+++ b/challenge-175/sgreen/python/ch-2.py
@@ -0,0 +1,97 @@
+#!/usr/bin/env python3
+
+import math
+
+primes = []
+factors = {}
+totients = {}
+
+
+def is_prime(number):
+    '''Return true or false if the number is a prime'''
+    if number < 2:
+        return False
+
+    for i in primes:
+        if number % i == 0:
+            return False
+
+    # It's a prime
+    return True
+
+
+def get_factors(num):
+    '''Get the prime factors that make up the numbers'''
+    global factors
+
+    if num not in factors:
+        factors[num] = set()
+
+        for p in primes:
+            if num % p == 0:
+                factors[num].add(p)
+
+    return factors[num]
+
+
+def get_totients(num):
+    '''Count the number of values between 1 and num-1 that has the gcd of 1'''
+    global totients
+
+    # If we've calculated this before, return the result
+    if num not in totients:
+        factors = get_factors(num)
+
+        count = 0
+        for n in range(1, num):
+            # Count this number if it has no common factors (other than 1)
+            if not factors.intersection(get_factors(n)):
+                count += 1
+
+        # Store the result when we need it again
+        totients[num] = count
+
+    return totients[num]
+
+
+def is_ptn(num):
+    '''Return whether this number is a perfect totient number'''
+
+    # Keep a count of the total
+    totals = 0
+
+    # Loop until we get to one
+    n = num
+    while n > 1:
+        totient = get_totients(n)
+        totals += totient
+
+        if totals > num:
+            # Short circuit exit if we know it will be False
+            return False
+
+        n = totient
+
+    return totals == num
+
+
+def main():
+    global primes
+    solutions = []
+    number = 0
+
+    # Loop until we have 20 solutions
+    while(len(solutions) < 20):
+        number += 1
+
+        if is_prime(number):
+            primes.append(number)
+
+        if is_ptn(number):
+            solutions.append(number)
+
+    print(*solutions, sep=', ')
+
+
+if __name__ == '__main__':
+    main()