Merge pull request #6215 from drbaggy/master

first soln

4 files changed, 227 insertions, 65 deletions

diff --git a/challenge-168/james-smith/README.md b/challenge-168/james-smith/README.md
index 5c08199913..e5e368c7c4 100644
--- a/challenge-168/james-smith/README.md
+++ b/challenge-168/james-smith/README.md
@@ -1,7 +1,7 @@
-[< Previous 166](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-166/james-smith) |
-[Next 168 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-168/james-smith)
+[< Previous 167](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-167/james-smith) |
+[Next 169 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-169/james-smith)
 
-# The Weekly Challenge 167
+# The Weekly Challenge 168
 
 You can find more information about this weeks, and previous weeks challenges at:
 
@@ -13,88 +13,147 @@ 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-167/james-smith
+https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-168/james-smith
 
-# Challenge 1 - Circular Prime
+# Challenge 1 - Perrin Prime
 
-***Write a script to find out first 10 circular primes having at least 3 digits (base 10). A circular prime is a prime number with the property that the number generated at each intermediate step when cyclically permuting its (base 10) digits will also be prime.***
+***The Perrin sequence is defined to start with [3, 0, 2]; after that, term N is the sum of terms N-2 and N-3. (So it continues 3, 2, 5, 5, 7, ...) A Perrin prime is a number in the Perrin sequence which is also a prime number. Calculate the first 13 Perrin primes***
 
-## Solution
 
-*We are going to slightly extend this to find the first 19 circular primes - includes 4 1-digit primes and 5 2-digit circular primes and the 10 3+-digit ciruclar primes < one-million - After the largest 6-digit circular prime the next circular prime is the 19 digit prime - 1,111,111,111,111,111,111*
+## Solution
 
-We use `Math::Prime::Util`s `next_prime` function to loop through the primes. Before we check for primality of each of the permutations we can remove trivial cases:
- 
- * We know all 1-digit primes are circular so we take these out first `#1` - in fact the remaining logic does not work as we assume there are other rotations - and the regex we see next would remove `2` & `5` the only primes that contain either of these digits;
- * We then remove numbers containing `0`, `2`, `4`, `5`, `6` or `8` as at least one rotation would end in this digit and therefore the number sould not be prime;
- * As we are looking for an exemplar for each rotation we take the lowest one - we just check that the supplied prime is less than any of the rotations.
+Using our favourite is_prime library we loop through the Perrin numbers and checking to see if they are prime, if they are we display them - if not we restart the loop with `redo`.
 
-   **Note** we use next here to short cut the map and jump to the next loop element.
+Rather than keep the whole array we only need the last 3 numbers in the sequence to generate the next so we have: `$s -> $r`, `$t -> $s` and `$r+$s -> $t`. Once nice feature of perl is that you can do multiple parallel definitions inside a list. The final quirk you see here is `$t!=$` - there is one duplicate value in the list (5) which would mean we saw 5 twice in our output which we don't want....
 
-   To rotate the digits we use the 4 parameter version of `substr` - `substr $string, $start, $length, $replacement` returns the substring from `$start`, but replaces the section returned with the contents of the fourth parameter...
+```perl
+my ($r,$s,$t)=(3,0,2);
+($r,$s,$t)=($s,$t,$r+$s), is_prime($t) && $t!=$s ? (say $t) : (redo) for 1..13;
+```
 
-   In this case we do `substr $a, 0, 0, substr $a, -1, 1, ''`. Firstly the right hand `substr` is evaluated - which takes the last element of `$a` and returns it, and replaces this with an empty string so if `$a` was `1234` then it has becomes `123` and returns `4`. We now then evaluate the first `substr` which returns the `0` character string from the start of `$a` (*i.e.* an empty string) and replaces it with the `4` from before so we end up with `4123` and sunsequent class give `3412` and `2341`.
-   
- * Now we look to see if we have any non-primes in the rotation using `is_prime`.. If we do then we skip the loop
+This gives us the first 13 as: 2; 3; 5; 7; 17; 29; 277; 367; 853; 14,197; 43,721; 1,442,968,193; 792,606,555,396,977.
 
- * Finally if we have got through all the filters we push the prime `$p` on to the results array.>
+The prime method is_prime can already handle big integers. So we can extend the range by forcing `$t` to be a big int. As it gets rotated around the other variables they all eventually become big ints.
 
 ```perl
-use Math::Prime::Util qw(next_prime is_prime);
-my( $p, $N, @q, @res ) = ( 1, 19 );
-
-while( @res < $N ) {
-  ( ( $t = $p = next_prime $p ) < 10
-    || $p !~ /[024568]/
-    && ( ! grep { !is_prime( $_ )                             && (next)      }
-           map  { ( substr$t,0,0,substr$t,-1,1,'' ) || $t < $p ? (next) : $t }
-           2 .. length $p )
-  ) && ( push @res, $p )
-}
-
-say for @res;
+my ($r,$s,$t)=(3,0,Math::BigInt->new(2));
+($r,$s,$t)=($s,$t,$r+$s), is_prime($t) && $t!=$s ? (say $t) : (redo) for 1..25
+```
+This gives us the following numbers - the large values may not be correct as
+the algorithm does best efforts and doesn't use an exhaustive scan of all
+possible factors, the 25th one has 1,111 digits
+```
+  2
+  3
+  5
+  7
+ 17
+ 29
+277
+367
+853
+ 14,197
+ 43,721
+  1,442,968,193
+792,606,555,396,977
+187,278,659,180,417,234,321
+ 66,241,160,488,780,141,071,579,864,797
+ 22,584,751,787,583,336,797,527,561,822,649,328,254,745,329
+ 29,918,426,252,927,024,136,988,188,355,201,180,399,482,197
+375,650,352,810,749,628,391,658,393,147,651,164,149,079,195,002,314,045,
+    738,061,982,119,710,039,976,648,976,965,060,598,469,931,973,177,804,
+    611,901,813
+ 17,889,871,724,792,219,792,241,402,014,701,050,416,254,403,054,909,819,
+    082,963,323,121,939,408,639,274,412,767,017,724,313,639,101,409,409,
+    795,922,319,558,694,157,739,957
+ 18,106,564,606,349,058,350,871,445,556,416,183,706,383,627,605,153,862,
+    231,876,341,960,946,635,847,221,883,756,661,544,295,450,957,270,512,
+    362,655,785,866,338,801,138,896,957,806,303,459,431,839,801
+ 26,443,665,126,671,039,192,963,010,650,954,408,309,392,693,422,822,076,
+    064,578,125,303,560,832,561,672,888,722,088,906,692,033,449,248,344,
+    378,194,605,701,099,265,071,815,485,284,432,217,750,405,098,433,434,
+    144,179,485,693,746,031,340,517
+  1,213,927,704,065,079,865,017,068,478,668,276,043,626,477,148,780,514,
+    011,765,015,731,886,286,159,454,983,721,480,068,033,892,046,357,328,
+    417,429,372,450,987,777,059,793,416,910,075,913,180,181,245,051,185,
+    193,201,551,033,755,831,307,534,780,351,082,477,949,347,441
+ 10,157,009,252,817,374,963,867,100,949,951,608,928,714,862,242,745,008,
+    993,013,668,540,854,184,107,874,570,804,968,501,397,570,379,041,274,
+    564,782,116,665,400,515,007,185,872,727,535,557,633,044,532,545,504,
+    298,417,513,460,010,708,859,590,624,519,737,577,132,699,128,528,530,
+    905,048,976,280,744,785,692,707,368,299,964,909,111,445,284,217,209,
+    819,026,508,401,682,969,213,029,773,502,708,330,316,828,337,469,827,
+    393,737,449,858,748,826,727,773,566,201,071,908,906,567,992,775,961,
+    863,663,250,545,199,702,810,339,801,764,180,200,620,104,056,601,639,
+    153,965,055,826,816,646,056,412,891,949,330,608,030,933,040,756,303,
+    987,388,596,508,709,113,305,229,398,404,925,505,186,056,022,798,817,
+    893,091,541,647,706,591,557,044,644,581
+  3,631,640,163,992,448,158,050,321,979,101,634,523,424,467,070,532,989,
+    940,589,376,200,895,999,542,521,324,121,865,744,873,084,026,078,365,
+    592,113,103,829,057,044,319,371,093,458,267,314,150,632,770,247,926,
+    037,880,226,504,980,936,257,910,602,481,948,018,841,362,454,143,562,
+    440,537,190,514,898,173,776,176,693,598,426,395,086,189,616,722,660,
+    098,879,586,330,664,613,823,090,197,360,409,779,437,591,689,520,837,
+    492,830,513,163,054,777,061,491,401,259,817,572,546,197,753,109,857,
+    199,993,236,881,971,656,255,401,039,799,820,579,630,315,398,215,866,
+    349,742,611,432,329,007,353,997,352,494,443,986,017,317,922,833,363,
+    523,351,835,711,663,212,252,398,827,126,207,580,953,779,469,798,265,
+    218,514,506,497,114,067,477,064,259,789,799,733,135,324,524,166,520,
+    280,952,689,291,443,318,735,365,943,242,441,087,374,207,019,201,381,
+    566,622,887,361,047,383,284,786,893,087,439,845,660,097,204,995,566,
+    088,460,835,424,395,601,898,782,600,822,606,786,314,286,293
+  2,219,044,107,563,366,280,125,882,554,584,749,275,765,334,696,920,954,
+    707,908,016,835,306,595,717,633,852,868,322,311,975,692,852,664,517,
+    100,196,388,216,185,466,256,781,811,629,490,339,018,476,958,341,423,
+    474,211,703,736,695,517,844,284,835,529,838,650,317,818,556,051,258,
+    418,641,466,473,522,496,581,011,902,709,035,886,778,717,452,108,700,
+    155,970,126,389,875,329,986,734,382,348,653,211,376,368,344,688,390,
+    461,606,168,880,878,403,666,028,447,970,631,164,159,760,593,687,145,
+    545,886,396,290,330,053,367,251,405,062,861,688,751,190,590,145,302,
+    902,036,352,069,892,640,867,792,281,047,623,995,380,029,998,885,072,
+    389,834,691,845,180,458,330,031,190,164,195,835,720,970,532,382,904,
+    375,909,996,290,964,537,793,186,771,320,552,080,008,575,799,336,721,
+    259,794,322,290,929,553,980,616,543,051,782,912,060,889,838,405,225,
+    710,047,974,384,273,630,158,925,203,871,673,773,377,987,293,309,129,
+    339,404,395,731,429,013,268,854,882,845,620,367,126,605,068,300,392,
+    529,925,817,814,239,701,362,999,633,802,539,696,168,715,197,247,149,
+    129,309,343,328,693,492,609,154,962,326,446,655,316,407,662,545,173,
+    312,263,693,868,901,442,507,821,627,007,923,602,173,657,448,415,818,
+    836,881,970,741,894,299,422,830,356,726,700,391,358,661,731,817,186,
+    882,034,993,006,807,831,454,673,264,747,496,927,244,085,026,523,852,
+    798,867,657,837,248,743,977,858,010,507,439,069,833,507,207,554,629,
+    542,720,934,827,351,494,206,895,735,690,852,994,106,560,067,899,320,
+    290,685,428,051,387,821,434,771,363,835,714,805,717
 ```
 
-Now some notes on efficiency.
+# Challenge 2 - Home Prime
 
- * To generate the 19 exemplars - we loop through 17,981 primes. The regex filter (and the <10) filters out 18,422 of these to leave just 559 primes
-   that go through the rotation code.
- * This filters our another 347 primes leaving just 212 sets of primes to check for primality.
- * We then just do 346 prime checks on these sets to rule in/rule out the number
+***You are given an integer greater than 1. Write a script to find the home prime of the given number. In number theory, the home prime HP(n) of an integer n greater than 1 is the prime number obtained by repeatedly factoring the increasing concatenation of prime factors including repetitions.***
 
-# Challenge 2 - Gamma function
+**Example: **
+```
+  10 = 2 x  5  ->   25
+  25 = 5 x  5  ->   55
+  55 = 5 x 11  ->  511
+ 511 = 7 x 73  ->  773
+ 773 =    773
+```
 
-***Implement subroutine gamma() using the Lanczos approximation method.***
+So `HP(10) = HP(25) = HP(55) = HP(511) = HP(773) = 773`.
 
 ## Solution
 
-The gamma function is the genaralisation of the factorial function `Gamma(n) = (n-1)!` for positive integers.
-
-We will use Lanczos approximation...
+Our favourite prime libray also has a `factor` function which returns a list of sorted prime factors (including duplicates). This simplfies the problem...
 
- * If z is an integer and less than or equal to 0 - we return the special string 'inf' as the value is infinite.
- * If z is less than 0.5 - we use the calulation beased on `gamma(1-z)` multiplied the the factor `PI/sin(PI * z)`
- * Finally we use the lanczos approximation.
-   * This starts by computing the sum in the map, then computing the value based on this sum
-   * we use `( map( {} @PV ), fn(z,x) )[-1]` to put this all in one line, we also re-use `$i` after the loop, to store the value of `$z+@PV-1.5` which is used twice AND again to store the final value - so we can decide to round it back down to an integer if we are close to integer value. This I agree is nasty!!!
-   * `$RP` is `sqrt(2*$PI)` but evaluated for speed 
- 
 ```perl
-const my $PI => 3.1415926535897932384626433832;
-const my $RP => 2.5066282746310002416123552393;
-const my $EP => 0.000000000001;
-const my $X  => 0.99999999999980993;
-const my @PV => (
-  676.5203681218851,  -1259.1392167224028,    771.32342877765313,     -176.61502916214059,
-   12.507343278686905,   -0.13857109526572012,  9.9843695780195716e-6,   1.5056327351493116e-7,
-);
-
-sub gamma {
-  my($i,$x,$z)=(0,$X,$_[0]);
-  ( $z<=0 && abs($z-int$z) < $EP ) ? 'inf'
-  : $z < 0.5 ? $PI / sin($PI*$z) * gamma(1-$z)
-  : ( map( {$x+=$_/($z+$i++)} @PV ),
-      abs( ( $i = $RP*( $i = $z+@PV-1.5 )**($z-0.5) * $x / exp $i ) - int $i ) < $EP ? int $i : $i
-    )[-1]
+sub home_prime {
+  return if (my$t=shift)<2;
+  is_prime($t)?(return$t):($t=join'',factor$t)while 1;
 }
 ```
+
+We first check to see if the parameter passed in is `0` or `1` in which case we return nothing.
+Otherwise if the value of the parameter is prime we return that and don't do anything else. o/w
+we update it via the rule above and repeat. With the big int support in the prime library we can
+compute the home prime for all positive integer between 2 and 100 (with the exception of 49/77
+which has yet to be solved!! - they both have the same home prime as `49 = 7x7 -> 77`
diff --git a/challenge-168/james-smith/blog.txt b/challenge-168/james-smith/blog.txt
new file mode 100644
index 0000000000..623068f8e5
--- /dev/null
+++ b/challenge-168/james-smith/blog.txt
@@ -0,0 +1,2 @@
+https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-168/james-smith
+
diff --git a/challenge-168/james-smith/perl/ch-1.pl b/challenge-168/james-smith/perl/ch-1.pl
new file mode 100644
index 0000000000..2f25fc5369
--- /dev/null
+++ b/challenge-168/james-smith/perl/ch-1.pl
@@ -0,0 +1,28 @@
+#!/usr/local/bin/perl
+
+use strict;
+use warnings;
+use feature qw(say);
+use Math::Prime::Util qw(is_prime);
+use Math::BigInt;
+
+## This is straight forward.
+## In each interation of the loop, we remove the lowest number of the triple,
+## and at the same time set the highest number to the sum of the previous 2
+## lowest numbers
+##
+## If the number isn't prime OR the number is the same as the previous number
+## then we restart the loop with redo, if not we display the number and
+## continue until we have displayed the first 13 perrin primes.
+
+say "\nWith normal ints (first 25)\n\n";
+my ($r,$s,$t)=(3,0,2);
+($r,$s,$t)=($s,$t,$r+$s), is_prime($t) && $t!=$s ? (say $t) : (redo) for 1..13;
+
+## Now with big ints...
+say "\n\nWith big ints (first 25)\n\n";
+
+($r,$s,$t)=(3,0,Math::BigInt->new(2));
+($r,$s,$t)=($s,$t,$r+$s), is_prime($t) && $t!=$s ? (say $t) : (redo) for 1..25;
+
+say "\n";
diff --git a/challenge-168/james-smith/perl/ch-2.pl b/challenge-168/james-smith/perl/ch-2.pl
new file mode 100644
index 0000000000..a81a68d340
--- /dev/null
+++ b/challenge-168/james-smith/perl/ch-2.pl
@@ -0,0 +1,73 @@
+#!/usr/local/bin/perl
+
+use strict;
+
+use warnings;
+use feature qw(say);
+use Test::More;
+use Math::Prime::Util qw(factor is_prime);
+
+## The array is the list of home primes between 2 and 100
+## {we pad the list with 0 0 so the index lines up with
+## its home prime}.
+##
+## We skip 49 and 77 as their home prime is very large
+## (and hasn't been discovered yet!) - they are the same
+## number as 49 = 7x7 -> 77
+##
+## We are going to use the factor function of Math::Prime::Util
+## which does the factoring for us - and is quick....
+##
+## Finally we use qw for the tests as we do a string comparison of the
+## numbers - the Math::Prime::Util uses "bigint"s to store the primes,
+## but unless we explicitly include a bigint library the values in the
+## tests array are treated a floating point of 2^64... and so you are
+## comparing different values. Keeping as a string we are comparing
+## the integer string with the stringified big int.
+
+my @TESTS = qw( 0  0
+                                               2                                             3           211
+                                               5                                            23             7
+                             3331113965338635107                                           311           773
+                                              11                                           223            13
+                                           13367                                          1129      31636373
+                                              17                                           233            19
+                             3318308475676071413                                            37           211
+                                              23                                        331319           773
+                                            3251                                         13367           227
+                                              29                                           547            31
+                                          241271                                           311         31397
+                                            1129                                         71129            37
+                                             373                                           313 3314192745739
+                                              41                                           379            43
+                                     22815088913                                       3411949           223
+                                              47                        6161791591356884791277             0
+                                            3517                                           317          2213
+                                              53                                          2333           773
+                                           37463                                          1129           229
+                                              59                                         35149            61
+                                           31237                                           337 1272505013723
+              1381321118321175157763339900357651                                          2311            67
+                                            3739                                         33191           257
+                                              71                                       1119179            73
+                                             379                                           571        333271
+                                               0                                    3129706267            79
+313169138727147145210044974146858220729781791489                               193089459713411           241
+                                              83                                          2237          3137
+                       6012903280474189529884459                    41431881512748629379008933        719167
+                                              89                                         71171     236122171
+                                          331319                                           331          1319
+                                           36389 172929671097972226356946608292031596899264419            97
+                                             277                                         71143        317047
+);
+
+## Skip 1 (no prime factors), 49, 77 (large value for home prim)
+is( home_prime($_), $TESTS[$_] ) for 2..48,50..76,78..100;
+
+done_testing();
+
+sub home_prime {
+  return if (my$t=shift)<2;  ## Skip in t is 0 or 1 which would loop infinitely...
+  is_prime($t)?(return$t):($t=join'',factor$t)while 1; ## If prime we return o/w we compute sum of factors
+}
+