diff options
Diffstat (limited to 'challenge-169')
| -rw-r--r-- | challenge-169/james-smith/README.md | 285 | ||||
| -rw-r--r-- | challenge-169/james-smith/blog.txt | 2 | ||||
| -rw-r--r-- | challenge-169/james-smith/perl/ch-1.pl | 22 | ||||
| -rw-r--r-- | challenge-169/james-smith/perl/ch-2.pl | 35 |
4 files changed, 225 insertions, 119 deletions
diff --git a/challenge-169/james-smith/README.md b/challenge-169/james-smith/README.md index e5e368c7c4..3e9971e507 100644 --- a/challenge-169/james-smith/README.md +++ b/challenge-169/james-smith/README.md @@ -1,7 +1,7 @@ -[< 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) +[< Previous 168](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-168/james-smith) | +[Next 170 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-170/james-smith) -# The Weekly Challenge 168 +# The Weekly Challenge 169 You can find more information about this weeks, and previous weeks challenges at: @@ -13,147 +13,194 @@ 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-168/james-smith +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-169/james-smith -# Challenge 1 - Perrin Prime +# Challenge 1 - Brilliant numbers -***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*** +***Write a script to generate first 20 Brilliant Numbers. Brilliant numbers are numbers with two prime factors of the same length. The number should have exactly two prime factors, i.e. it’s the product of two primes of the same length.*** ## Solution -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`. +Again our favoured prime package `Math::Prime::Util` has the method we need `factor` which returns a list of prime factors, and its fast - especially for the magnitude of numbers we are looking at. -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.... +We loop through all numbers, checking to see if (a) the number has exactly 2 prime factors and they are the same length. + +For flexibility we define the max count `$MAX` as the command-line argument if one is supplied (or 100 if not). ```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; +for( my( $n, $c, $MAX, @f ) = ( 0, 0, @ARGV ? $ARGV[0] : 1e2 ); $c<$MAX; $n++ ) { + say sprintf '%7d: %10d = %5d x %d', ++$c, $n, @f if 2 == ( @f = factor $n ) && length $f[0] == length $f[1]; +} ``` -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. +This logic is wrapped up int the single `if`. As we check the number of factors, we store these in an array, so that we can check the 2nd condition. -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. +The output in each row is the brilliant number and the two primes which are it's factors. + +**Note:** Both in this and the next challenge we utilise a classic "c-style" `for`-loop. This construct allows us to combine the variable initialized (and declaration), the end condition, and the increment of the number into a single statement. We code rewrite this a postfix `for(each)` in this case, but would need an declaration/initialisation statement for `$n` and `@f` anyway. Also in challenge 2 it isn't possible to use a postfix for `for` as this doesn't allow us to use the `next` trick to short cut the `grep` inside the `gcd` call. + +**Note:** to make the code easier to read we use a *Yoda* condition, where we reverse the value and the code evaluation - so instead if say `$a == 2` we say `2 == $a`. + +**Moan:** Why is there no `sayf` function similar to `printf` - using `say sprintf` seems a bit "messy" each time... -```perl -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 + 1: 4 = 2 x 2 + 2: 6 = 2 x 3 + 3: 9 = 3 x 3 + 4: 10 = 2 x 5 + 5: 14 = 2 x 7 + 6: 15 = 3 x 5 + 7: 21 = 3 x 7 + 8: 25 = 5 x 5 + 9: 35 = 5 x 7 + 10: 49 = 7 x 7 + 11: 121 = 11 x 11 + 12: 143 = 11 x 13 + 13: 169 = 13 x 13 + 14: 187 = 11 x 17 + 15: 209 = 11 x 19 + 16: 221 = 13 x 17 + 17: 247 = 13 x 19 + 18: 253 = 11 x 23 + 19: 289 = 17 x 17 + 20: 299 = 13 x 23 + 21: 319 = 11 x 29 + 22: 323 = 17 x 19 + 23: 341 = 11 x 31 + 24: 361 = 19 x 19 + 25: 377 = 13 x 29 + 26: 391 = 17 x 23 + 27: 403 = 13 x 31 + 28: 407 = 11 x 37 + 29: 437 = 19 x 23 + 30: 451 = 11 x 41 + 31: 473 = 11 x 43 + 32: 481 = 13 x 37 + 33: 493 = 17 x 29 + 34: 517 = 11 x 47 + 35: 527 = 17 x 31 + 36: 529 = 23 x 23 + 37: 533 = 13 x 41 + 38: 551 = 19 x 29 + 39: 559 = 13 x 43 + 40: 583 = 11 x 53 + 41: 589 = 19 x 31 + 42: 611 = 13 x 47 + 43: 629 = 17 x 37 + 44: 649 = 11 x 59 + 45: 667 = 23 x 29 + 46: 671 = 11 x 61 + 47: 689 = 13 x 53 + 48: 697 = 17 x 41 + 49: 703 = 19 x 37 + 50: 713 = 23 x 31 ``` -# Challenge 2 - Home Prime +### Removing pretty print -***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.*** +If we remove the pretty print this reduces to: -**Example: ** -``` - 10 = 2 x 5 -> 25 - 25 = 5 x 5 -> 55 - 55 = 5 x 11 -> 511 - 511 = 7 x 73 -> 773 - 773 = 773 +```perl +for( my( $n, $c, $MAX, @f ) = ( 0, 0, @ARGV ? $ARGV[0] : 1e2 ); $c<$MAX; $n++ ) { + $c++, say $n if 2 == ( @f = factor $n ) && length $f[0] == length $f[1]; +} ``` -So `HP(10) = HP(25) = HP(55) = HP(511) = HP(773) = 773`. +# Challenge 2 - Achilles Number + +***Write a script to generate first 20 Achilles Numbers. An Achilles number is a number that is powerful but imperfect (not a perfect power). Named after Achilles, a hero of the Trojan war, who was also powerful but imperfect.*** + +*A positive integer `n` is a powerful number if, for every prime factor `p` of `n`, `p^2` is also a divisor.* + +*A number is a perfect power if it has any integer ropts ( square, cube, ... ) i.e. can be written in the form `n^m`.* + +*An imperfect number is one which can't be - now this means that if we make a prime factorization of the form `p1^k1 . p2^k2 . p3^k3 ....` then the greatest common divisor is 1. As if greater than 1 then we could write this as `( p1^k1/gcd . p2^k2/gcd . p3^k3/gcd . ... )^gcd` and so would be perfect. ## Solution -Our favourite prime libray also has a `factor` function which returns a list of sorted prime factors (including duplicates). This simplfies the problem... +Again `Math::Prime::Util` has the two methods we need `factor_exp` and `gcd`. The former a modification to `factor` returns a list of tuples, each containing the prime and its exponent so rather than returning say `2, 2, 2, 3, 3` it returns `[2, 3], [3, 2]`. The latter a function we haven't used before takes a list of numbers and computes there greatest common divisor. This simplfies the problem... for each value we generate a hash of their prime factors, the key being the prime and the value the power (using `factor`) + +We then check to see if any of the factors does not have its square as a factor. We do this in the grep - by using `next` we jump out of the `map` back to the next entry in the `for` loop. + +We then compute the `gcd` of these powers - if it is 1 then we display the result - our output is index, value and the prime factorisation, most of the loop is for the pretty print. + +```perl +for( my( $n, $c, $MAX, @f ) = ( 2, 0, @ARGV ? $ARGV[0] : 1e2 ); $c < $MAX; $n++ ) { + say sprintf '%6d: %15d = %s', ++$c, $n, join ' . ', map { "$_->[0]^$_->[1]" } @f + if 1 == gcd map { $_->[1] < 2 ? next : $_->[1] } @f = factor_exp $n; +} +``` + +The following are the first 50 achilles numbers. +``` + 1: 72 = 2^3 . 3^2 + 2: 108 = 2^2 . 3^3 + 3: 200 = 2^3 . 5^2 + 4: 288 = 2^5 . 3^2 + 5: 392 = 2^3 . 7^2 + 6: 432 = 2^4 . 3^3 + 7: 500 = 2^2 . 5^3 + 8: 648 = 2^3 . 3^4 + 9: 675 = 3^3 . 5^2 + 10: 800 = 2^5 . 5^2 + 11: 864 = 2^5 . 3^3 + 12: 968 = 2^3 . 11^2 + 13: 972 = 2^2 . 3^5 + 14: 1125 = 3^2 . 5^3 + 15: 1152 = 2^7 . 3^2 + 16: 1323 = 3^3 . 7^2 + 17: 1352 = 2^3 . 13^2 + 18: 1372 = 2^2 . 7^3 + 19: 1568 = 2^5 . 7^2 + 20: 1800 = 2^3 . 3^2 . 5^2 + 21: 1944 = 2^3 . 3^5 + 22: 2000 = 2^4 . 5^3 + 23: 2312 = 2^3 . 17^2 + 24: 2592 = 2^5 . 3^4 + 25: 2700 = 2^2 . 3^3 . 5^2 + 26: 2888 = 2^3 . 19^2 + 27: 3087 = 3^2 . 7^3 + 28: 3200 = 2^7 . 5^2 + 29: 3267 = 3^3 . 11^2 + 30: 3456 = 2^7 . 3^3 + 31: 3528 = 2^3 . 3^2 . 7^2 + 32: 3872 = 2^5 . 11^2 + 33: 3888 = 2^4 . 3^5 + 34: 4000 = 2^5 . 5^3 + 35: 4232 = 2^3 . 23^2 + 36: 4500 = 2^2 . 3^2 . 5^3 + 37: 4563 = 3^3 . 13^2 + 38: 4608 = 2^9 . 3^2 + 39: 5000 = 2^3 . 5^4 + 40: 5292 = 2^2 . 3^3 . 7^2 + 41: 5324 = 2^2 . 11^3 + 42: 5400 = 2^3 . 3^3 . 5^2 + 43: 5408 = 2^5 . 13^2 + 44: 5488 = 2^4 . 7^3 + 45: 6075 = 3^5 . 5^2 + 46: 6125 = 5^3 . 7^2 + 47: 6272 = 2^7 . 7^2 + 48: 6728 = 2^3 . 29^2 + 49: 6912 = 2^8 . 3^3 + 50: 7200 = 2^5 . 3^2 . 5^2 +``` +### Removing pretty print + +If we remove the pretty print this reduces to: ```perl -sub home_prime { - return if (my$t=shift)<2; - is_prime($t)?(return$t):($t=join'',factor$t)while 1; +for( my( $n, $c, $MAX, @f ) = ( 2, 0, @ARGV ? $ARGV[0] : 1e2 ); $c<$MAX; $n++ ) { + $c++, say $n if 1 == gcd map { $_->[1] < 2 ? next : $_->[1] } @f = factor_exp $n; } ``` -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` +# Note - product vs factor + +There is a different method which is to generate a list of numbers for both problems from a list of primes. + +For both challenges I looked at this "product" version of the code (generate a list of primes) and multiplying - rather the factor method. This proved to be slower than the loop through all values of `$n` and filter by factoring. Whether this continues for larger values of `$n` I don't know by I know that producing the first 1 million of each number it was slower, and at that point the product methods then started to hit memory problems. + +One of the memory issues is the `sort` a list issue - having to keep multiple large lists in memory. There are work arounds (like using a modified merge sort) but again these have their coding overheads. + +If I had to roll my own "factor" code it would almost certainly have been a better option - but the `Math::Prime::Util` methods are plenty fast enough. diff --git a/challenge-169/james-smith/blog.txt b/challenge-169/james-smith/blog.txt new file mode 100644 index 0000000000..5be06bbe88 --- /dev/null +++ b/challenge-169/james-smith/blog.txt @@ -0,0 +1,2 @@ +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-169/james-smith + diff --git a/challenge-169/james-smith/perl/ch-1.pl b/challenge-169/james-smith/perl/ch-1.pl new file mode 100644 index 0000000000..029bc36c6c --- /dev/null +++ b/challenge-169/james-smith/perl/ch-1.pl @@ -0,0 +1,22 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say); +use Math::Prime::Util qw(factor); +use Time::HiRes qw(time); + +my $time = time; + +# Within each loop we get a factorisation +# must have preciesely 2 prime factors +# THEN each factor must be the same length; + +for( my( $n, $c, $MAX, @f ) = ( 0, 0, @ARGV ? $ARGV[0] : 1e2 ); $c<$MAX; $n++ ) { + say sprintf '%8d: %10d = %5d x %d', ++$c, $n, @f + if 2 == ( @f = factor $n ) && length $f[0] == length $f[1]; +} + +warn 'Time taken: ', time-$time, "\n"; + diff --git a/challenge-169/james-smith/perl/ch-2.pl b/challenge-169/james-smith/perl/ch-2.pl new file mode 100644 index 0000000000..62a7e91631 --- /dev/null +++ b/challenge-169/james-smith/perl/ch-2.pl @@ -0,0 +1,35 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say); +use Math::Prime::Util qw(factor_exp gcd); +use Time::HiRes qw(time); + +my $time = time; + +# Factorise $n into prime factors, and count for each factor... +# +# e.g. 10800 has factors ( 2, 2, 2, 2, 3, 3, 3, 5, 5 ) or 2^4 3^3 5^2 +# +# factor_exp returns a list of tuples - [ prime, exponent ] + +# If any of the 2nd entries in each tuple are 1 then we skip to the next number +# as it isn't brilliant.. +# +# To rule out perfect numbers we find the gcd of these values and if it is +# greater than one we have a perfect number and skip to the next +# +# We have a brilliant imperfect (or archilles) number.... so display it.. +# +# To pretty print the archilles numbers - we use our counter, and display +# it alongside the number and the factorisation. + +for( my( $n, $c, $MAX, @f ) = ( 2, 0, @ARGV ? $ARGV[0] : 1e2 ); $c<$MAX; $n++ ) { + say sprintf '%6d: %15d = %s', ++$c, $n, join ' . ', map { "$_->[0]^$_->[1]" } @f + if 1 == gcd map { $_->[1] < 2 ? next : $_->[1] } @f = factor_exp $n; +} + +warn 'Time taken: ', time-$time, "\n"; + |