From 658e60b76deb452bf572385355917a0c46c19853 Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 19 Jun 2022 21:19:30 +0100 Subject: oops! found a serious error in my PrimeFactors() function last week.. fixed --- challenge-168/duncan-c-white/perl/PrimeFactors.pm | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/challenge-168/duncan-c-white/perl/PrimeFactors.pm b/challenge-168/duncan-c-white/perl/PrimeFactors.pm index 5ec2210764..95c5043d15 100644 --- a/challenge-168/duncan-c-white/perl/PrimeFactors.pm +++ b/challenge-168/duncan-c-white/perl/PrimeFactors.pm @@ -40,7 +40,7 @@ fun prime_factors( $n ) { die "prime_factors: n ($n) must be >1\n" if $n<=1; my @result; - my $lim = int(sqrt($n)); + my $lim = $n; my $orign = $n; foreach my $f (2..$lim) { @@ -50,8 +50,6 @@ fun prime_factors( $n ) { say "pf($orign): n=$n, adding $f to result" if $debug; push @result, $f; - my $other = $orign / $f; - push @result, $other if isprime($other) && $other != $f; $n /= $f; say "pf($orign): n /= $f (so n=$n now)" if $debug; } -- cgit From 40792c9e5ba22d641a3dd8e5bcff9c42570f66fc Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 19 Jun 2022 22:54:54 +0100 Subject: imported my solutions to this week's tasks, two quite nice tasks (but note: I'm getting very bored with prime-based number theory tasks) --- challenge-169/duncan-c-white/README | 67 +++++++++------ challenge-169/duncan-c-white/perl/PrimeFactors.pm | 63 ++++++++++++++ challenge-169/duncan-c-white/perl/ch-1.pl | 55 ++++++++++++ challenge-169/duncan-c-white/perl/ch-2.pl | 100 ++++++++++++++++++++++ 4 files changed, 258 insertions(+), 27 deletions(-) create mode 100644 challenge-169/duncan-c-white/perl/PrimeFactors.pm create mode 100755 challenge-169/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-169/duncan-c-white/perl/ch-2.pl diff --git a/challenge-169/duncan-c-white/README b/challenge-169/duncan-c-white/README index 17fc15785c..de1ee5c051 100644 --- a/challenge-169/duncan-c-white/README +++ b/challenge-169/duncan-c-white/README @@ -1,43 +1,56 @@ -TASK 1: Perrin Prime +TASK 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, ....) +Write a script to generate first 20 Brilliant Numbers. -A Perrin prime is a number in the Perrin sequence which is also a prime number. + Brilliant numbers are numbers with two prime factors of the same length. -Calculate the first 13 Perrin Primes. +The number should have exactly two prime factors, i.e. it's the product +of two primes of the same length. -f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977] +For example, -MY NOTES: ok, sounds relatively easy, except that the 12th and 13th PP are -enormous. I normally reusing my old favourite MakePrimes.pm (Sieve of -Eratosthenes based) but this time I think I'll have to do it the old -fashioned "try all factors up to sqrt()" approach. +24287 = 149 x 163 +24289 = 107 x 227 +Therefore 24287 and 24289 are 2-brilliant numbers. These two brilliant +numbers happen to be consecutive as there are no even brilliant numbers +greater than 14. -Task 2: Home Prime +Output -You are given an integer greater than 1. +4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, 253, 289, 299 -Write a script to find the home prime of the given number. +MY NOTES: ok, sounds relatively easy, but I'm getting very bored of +"tasks to do with Number Theory and (especially) Primes". -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. -Further information can be found on Wikipedia +Task 2: Achilles Numbers -https://en.wikipedia.org/wiki/Home_prime +Write a script to generate first 20 Achilles Numbers. Please checkout +wikipedia for more information. -Example +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. -As given in the Wikipedia page: +A positive integer n is a powerful number if, for every prime factor p +of n, p^2 is also a divisor. -HP(10) = 773, as 10 factors as 2x5 yielding HP10(1) = 25, 25 factors -as 5x5 yielding HP10(2) = HP25(1) = 55, 55 = 5x11 implies HP10(3) -= HP25(2) = HP55(1) = 511, and 511 = 7x73 gives HP10(4) = HP25(3) = -HP55(2) = HP511(1) = 773, a prime number. +A number is a perfect power if it has any integer roots (square root, +cube root, etc.). -MY NOTES: Ok, yet another prime variant. I'll have a go, but I note that -the numbers get enormous, to the point where it's not even known if HP(49) -can be calculated. Again can't use MakePrimes.pm.. +For example 36 factors to (2, 2, 3, 3) - every prime factor (2, 3) also +has its square as a divisor (4, 9). But 36 has an integer square root, +6, so the number is a perfect power. + +But 72 factors to (2, 2, 2, 3, 3); it similarly has 4 and 9 as divisors, +but it has no integer roots. This is an Achilles number. + +Output + + 72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125, 1152, 1323, 1352, 1372, 1568, 1800 + + +MY NOTES: Ok, yet another prime variant. I can immediately see some mileage +in pre-computing a lookup table of all perfect-powers up to N. Perhaps N=1800 +as we know the answer:-) diff --git a/challenge-169/duncan-c-white/perl/PrimeFactors.pm b/challenge-169/duncan-c-white/perl/PrimeFactors.pm new file mode 100644 index 0000000000..129db6d3ae --- /dev/null +++ b/challenge-169/duncan-c-white/perl/PrimeFactors.pm @@ -0,0 +1,63 @@ +# +# Prime factors: +# compute the prime factors of a number, using the old fashioned +# isprime "try all the factors" +# + +use v5.10; # to get "say" +use strict; +use warnings; +use Function::Parameters; +#use Data::Dumper; + + +my $debug = 0; + + +# +# my $isprime = isprime( $n ); +# Return 1 iff $n is a prime. Return 0 otherwise. +# +sub isprime +{ + my( $n ) = @_; + my $lim = int(sqrt($n)); + foreach my $div (2..$lim) + { + return 0 if $n % $div == 0; + } + return 1; +} + + +# +# my @factors = prime_factors( $n ); +# Break $n>1 apart into it's PRIME FACTORS (excluding 1). +# Return the list of prime factors, smallest first. +# eg. prime_factors( 228 ) = 2,2,3,19 +# +fun prime_factors( $n ) +{ + die "prime_factors: n ($n) must be >1\n" if $n<=1; + my @result; + my $lim = $n; + my $orign = $n; + foreach my $f (2..$lim) + { + next unless isprime($f); + say "pf($orign): considering prime factor $f" if $debug; + while( $n>1 && $n % $f == 0 ) + { + say "pf($orign): n=$n, adding $f to result" if $debug; + push @result, $f; + $n /= $f; + say "pf($orign): n /= $f (so n=$n now)" if $debug; + } + last if $n==1; + } + say "pf($orign): prime factors are @result" if $debug; + return @result; +} + + +1; diff --git a/challenge-169/duncan-c-white/perl/ch-1.pl b/challenge-169/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..228e29cb7e --- /dev/null +++ b/challenge-169/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,55 @@ +#!/usr/bin/perl +# +# TASK 1: Brilliant Numbers +# +# 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. +# +# For example, +# +# 24287 = 149 x 163 +# 24289 = 107 x 227 +# +# Therefore 24287 and 24289 are 2-brilliant numbers. These two brilliant +# numbers happen to be consecutive as there are no even brilliant numbers +# greater than 14. +# +# Output +# +# 4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, 253, 289, 299 +# +# MY NOTES: ok, sounds relatively easy, but I'm getting very bored of +# "tasks to do with Number Theory and (especially) Primes". Reuse the +# PrimeFactors module from last week, the one that doesn't pre-compute +# primes up to X. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +#use Data::Dumper; + +use lib qw(.); +use PrimeFactors; + +my $debug=0; +die "Usage: brilliant-numebrs [--debug] [N default 20]\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV<2; +my $n = shift // 20; + +my @brillig; +for( my $x = 4; @brillig < $n; $x++ ) +{ + my @f = prime_factors( $x ); + next unless @f == 2; + next unless length($f[0]) == length($f[1]); + push @brillig, $x; + say "found briliant number $x, factors $f[0] x $f[1]" if $debug; +} + +say join(', ', @brillig ); diff --git a/challenge-169/duncan-c-white/perl/ch-2.pl b/challenge-169/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..d154f1112b --- /dev/null +++ b/challenge-169/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,100 @@ +#!/usr/bin/perl +# +# Task 2: Achilles Numbers +# +# Write a script to generate first 20 Achilles Numbers. Please checkout +# wikipedia for more information. +# +# 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 roots (square root, +# cube root, etc.). +# +# For example 36 factors to (2, 2, 3, 3) - every prime factor (2, 3) also +# has its square as a divisor (4, 9). But 36 has an integer square root, +# 6, so the number is a perfect power. +# +# But 72 factors to (2, 2, 2, 3, 3); it similarly has 4 and 9 as divisors, +# but it has no integer roots. This is an Achilles number. +# +# Output +# +# 72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, +# 1125, 1152, 1323, 1352, 1372, 1568, 1800 +# +# MY NOTES: Ok, yet another prime variant. I can immediately see some mileage +# in pre-computing a lookup table of all perfect-powers up to N. Perhaps N=1800 +# as we know the answer:-) +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Function::Parameters; +use Data::Dumper; + +use lib qw(.); +use PrimeFactors; + +my $debug=0; +die "Usage: achilles-numbers [--debug] [N default 20]\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV<2; +my $n = shift // 20; + +# +# my $ispowerful = ispowerful( $n ); +# A positive integer n is a powerful number if, for every prime factor p +# of n, p^2 is also a divisor. +# +fun ispowerful( $n ) +{ + my @f = prime_factors( $n ); + foreach my $pf (@f) + { + return 0 unless $n % ($pf*$pf) == 0; + } + return 1; +} + + +# +# my %perfpower = calc_perf_powers_up_to( $limit ); +# A number is a perfect power if it has any integer roots (square root, +# cube root, etc.). Precalc all perfectpowers up to $limit, as a set. +# +fun calc_perf_powers_up_to( $limit ) +{ + my %perfpower; + $perfpower{1}++; + my $l2 = $limit*$limit; + for( my $i=2; $i<=$l2; $i++ ) + { + for( my $pow = $i*$i; $pow <= $limit; $pow *= $i ) + { + $perfpower{$pow}++; + } + } + return %perfpower; +} + + +my %perfpower = calc_perf_powers_up_to( 2000 ); +#my @pp = sort { $a <=> $b } keys(%perfpower); +#die Dumper \@pp; + +my @ach; +for( my $x=4; @ach<$n; $x++ ) +{ + next unless ispowerful($x); + say "debug: $x is powerful" if $debug; + next if $perfpower{$x}; + say "debug: $x is powerful and not perfect power" if $debug; + push @ach, $x; +} +say "ach: ". join(', ', @ach ); -- cgit