diff options
| -rw-r--r-- | challenge-158/james-smith/README.md | 136 | ||||
| -rw-r--r-- | challenge-158/james-smith/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-158/james-smith/perl/ch-1.pl | 62 | ||||
| -rw-r--r-- | challenge-158/james-smith/perl/ch-2.pl | 19 |
4 files changed, 179 insertions, 39 deletions
diff --git a/challenge-158/james-smith/README.md b/challenge-158/james-smith/README.md index e2c34fce9a..342202ccbf 100644 --- a/challenge-158/james-smith/README.md +++ b/challenge-158/james-smith/README.md @@ -1,6 +1,6 @@ -[< Previous 156](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-156/james-smith) | -[Next 158 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-158/james-smith) -# The Weekly Challenge 157 +[< Previous 157](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-157/james-smith) | +[Next 159 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-159/james-smith) +# The Weekly Challenge 158 You can find more information about this weeks, and previous weeks challenges at: @@ -12,62 +12,120 @@ submit solutions in whichever language you feel comfortable with. You can find the solutions here on github at: -https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-157/james-smith +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-158/james-smith -# Challenge 1 - Pythagorean Means +# Challenge 1 - Additive primes -***You are given a set of integers. Write a script to compute all three Pythagorean Means i.e. Arithmetic Mean, Geometric Mean and Harmonic Mean of the given set of integers.*** +***Additive primes are prime numbers for which the sum of their decimal digits are also primes.*** ## The solution -Computing the means is relatively straight forward. We just need to keep the sum of values, the product of values & the sum of their reciprocals. +We loop through each prime p, work out the digit sum (by repeated modulo 10/divide by 10) and check that it is prime. +We craft this as two loops - an outer `for` loop and an inner `do {} while`. -Once we have these sums, it is easy to return the respective means - dividing by `$N`, taking the `$N`-th root and taking `$N` divided by the sum. +```perl +use Math::Prime::Util qw(next_prime is_prime); + +sub additive_primes { + my @res; + for( + my $p = 2 ; + my $s = 0, ( my $q = $p ) <= $N; + (is_prime $s) && (push @res, $p), $p = next_prime $p + ) { + do { $s += $q % 10 } while $q = int $q / 10; + } + @res; +} +``` +## Output +``` +2, 3, 5, 7, 11, 23, 29, 41, 43, 47, 61, 67, 83, 89 +``` +## Notes + * We use a C-style `for` loop, with it's three parts *initialization*, *condition* and *increment*. + * The *condition* and *increment* statements are complicated, each with two parts separated by `,`s. + * The *condition* block is called at the start of each loop, and so we use it to initialise the variables as the loop, as well as checking the condition. + * The *increment* block is called at the end of the loop and so stores the value of `$p` if it is an additive prime, then it increments the loop with the next prime. + * Rather than doing a split and sum we use repeated dividing and summing, as it is more efficient around 20-30% more efficient. The increased performance is probably due to avoiding the "duality" of perl variables storing numbers as numbers/strings. + +## Extra code + +Rewritten with single line `for` ... (the original version of the code) ```perl -sub means { - my ($am, $gm, $hm) = (0, 1, 0); - $am+=$_, $gm*=$_, $hm+=1/$_ for @_; - ( $am/@_, $gm**(1/@_), @_/$hm ); +sub additive_primes_div { + my @res; + for(my$p=2; my$s=0,(my $q=$p)<=$N;(is_prime$s)&&(push@res,$p),$p=next_prime$p) { + do { $s += $q % 10 } while $q = int $q / 10; + } + @res; +} +``` + +Alternative form with `for split`: + +```perl +sub additive_primes_split { + my @res; + for( my $p = 2; my $s = 0, $p <= $N ; $p = next_prime $p ) { + $s+=$_ for split //, $p; + push @res, $p if is_prime $s; + } + @res; } ``` -### Notes: - * we assume that (a) the list is not empty, and (b) all integer values are not equal to `0`. - * the code is optimal in the number of operators. - * We should note that if the array size is large the geometric mean product can get large (prior to taking the *n*th root). So the value of `$gm` could be multipled by the *n*th root of each number in turn. So the middle line would be `$gm*=$_**(1/@_)` and the last line would just contain `$gm`. - * If we look at the geometric mean of the numbers `1` .. `$N` then the naive method above fails when `$N` is `171` just returning `Inf`, whereas the code below continues working giving the right answer - * the other two means this shouldn't be an issue (the intermediate calculation is a summation) +And an alternate using `sum0`... + ```perl -sub means_scalable { - my ($am, $gm, $hm) = (0, 1, 0); - $am+=$_, $gm*=$_**(1/@_), $hm+=1/$_ for @_; - ( $am/@_, $gm, @_/$hm ); +sub additive_primes_split_sum0 { + my @res; + for( my $p = 2; $p <= $N ; $p = next_prime $p ) { + push @res, $p if is_prime sum0 split //, $p; + } + @res; } ``` -# Challenge 2 - Brazilian Number +### Relative performance + + * `div`/`mod` method - 100% + * `split` - 75% + * `sum0 split` - 45% + +# Challenge 2 - First series buban primes -***You are given a number `N > 3`. Write a script to find out if the given number is a Brazilian Number. A positive integer number `N` has at least one natural number `B` where `1 < B < N-1` where the representation of N in base B has same digits.*** +***Write a script to compute first series cuban primes <= 1000. (First series cuban primes have the form `((x+1)^3-x^3)/(x+1-x)` = `3x^2+3x+1`)*** ## The solution -For any value of `$B` we can check that the digits are the same by repeated integer division. We first store the last digit `$last` below, and compare each digit with this value. If they are the not the same we jump out of the inner loop to the next value of the outer loop `next OUTER`. So if they are the same it falls down to the `return 1;` inside the outer loop. If all fail we never get to the `return 1;` so return `0` from the last line of the function. +The solution is rather short. We try each of the value of the sequence `3*$x**2+3*$x+1` in turn up to the value of 1000 (`$N`). +We output each value which in turn is prime. ```perl -sub is_brazilian { - OUTER: for my $b (2..$_[0]/2-1) { - my $last = (my $n=$_[0]) % $b; - $n % $b == $last || next OUTER while $n = int( $n/$b ); - return 1; - } - 0; -} +(is_prime $_) && say while $N >= ($_ = 3*$x*++$x+1); +``` +## Output +``` +7, 19, 37, 61, 127, 271, 331, 397, 547, 631, 919 ``` +## Notes + * As we use `$_` as our temporary variable we can use `say` by itself to output it. + * We use our common trick of `(condition) && (command)` to work as an `command if(condition)` which can be embedded in a postfix loop. + * There is a "trick" as we increment `$x` half way through the calculation of `$_`. + * `$_ = 3*$x**2 + 3*$x + 1` => `$_ = 3 * $x * ($x+1) + 1` => `$_ = 3 * $x * ++$x + 1` + * We can replace the `$x+1` by the pre increment operator `++$x` so this becomes `3 * $x * ++$x + 1`. -### Notes - * `{condition} || {command}` inside a `for` or `while` loop is the same as `unless( {condition} ) {command}` - it is often used when it makes a multi-line block into a single lined block with a postfix loop. This is useful to keep the overall code length shorter and therefore more-readable. Similarly can use `&&` for `if` and `?:` for `if`/`else`. - * We do not need to loop up to `$N-2` as the brazilian number will always be less than half this. So the `$b` loop is shorter - and makes the code run around 40-50% faster. - * `next {label}` is useful in many examples to jump out of inner loop without using *flag* variables to know whether the inner loop returned a *true* or *false* value. - * Conway frowns on this in PBP - but with such a short loop it is easy at a glance to see what the `next OUTER` does. - ( If the code was longer it may no longer be possible to see the outside of the loop when looking at in a "normal" terminal window. ) +## Aside + +Second series cuban primes have the form `((x+2)^3-x^3)/(x+2-x)` = `3x^2+3.2x+4`. We can tweak the code to give: + +```perl +(is_prime $_) && say while $N >= ($_ = 3 * $x * (2 + $x++) + 4); +``` + +which outputs: +``` +13, 109, 193, 433, 769 +``` diff --git a/challenge-158/james-smith/blog.txt b/challenge-158/james-smith/blog.txt new file mode 100644 index 0000000000..7e8d6837df --- /dev/null +++ b/challenge-158/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-158/james-smith diff --git a/challenge-158/james-smith/perl/ch-1.pl b/challenge-158/james-smith/perl/ch-1.pl new file mode 100644 index 0000000000..dd43aa3bc6 --- /dev/null +++ b/challenge-158/james-smith/perl/ch-1.pl @@ -0,0 +1,62 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say); +use Math::Prime::Util qw(next_prime is_prime); +use Benchmark qw(cmpthese); +use List::Util qw(sum0); + +my $N = shift || 100; +my $I = 1e7/$N; +$I = 100 if $I<100; +say join ', ', additive_primes_div(); +say join ', ', additive_primes_div_expanded(); +say join ', ', additive_primes_split(); +say join ', ', additive_primes_split_sum0(); + +cmpthese( $I, { + 'split' => sub { additive_primes_split(); }, + 'sum0' => sub { additive_primes_split_sum0(); }, + 'div' => sub { additive_primes_div(); }, + 'div_exp' => sub { additive_primes_div_expanded(); }, +} ); + +sub additive_primes_div_expanded { + my @res; + for( + my $p = 2 ; + my $s = 0, ( my $q = $p ) <= $N; + (is_prime $s) && (push @res, $p), $p = next_prime $p + ) { + do { $s += $q % 10 } while $q = int $q / 10; + } + @res; +} + +sub additive_primes_div { + my @res; + for( my $p = 2; my $s = 0, ( my $q = $p ) <= $N; (is_prime $s) && (push @res, $p), $p = next_prime $p ) { + do { $s += $q % 10 } while $q = int $q / 10; + } + @res; +} + + +sub additive_primes_split { + my @res; + for( my $p = 2; my $s = 0, $p <= $N ; $p = next_prime $p ) { + $s+=$_ for split //, $p; + push @res, $p if is_prime $s; + } + @res; +} +sub additive_primes_split_sum0 { + my @res; + for( my $p = 2; $p <= $N ; $p = next_prime $p ) { + push @res, $p if is_prime sum0 split //, $p; + } + @res; +} + diff --git a/challenge-158/james-smith/perl/ch-2.pl b/challenge-158/james-smith/perl/ch-2.pl new file mode 100644 index 0000000000..9a7f86ad2b --- /dev/null +++ b/challenge-158/james-smith/perl/ch-2.pl @@ -0,0 +1,19 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say); +use Math::Prime::Util qw(is_prime); + +my ($N,$x) = (shift || 1000,1); + +say "\nFirst series"; +(is_prime $_) && say while $N >= ($_ = 3*$x*++$x+1); + +$x=1; +say "\nSecond series"; + +(is_prime $_) && say while $N >= ($_ = 3 * $x * ( 2 + $x++ ) + 4); + +say ''; |