From 2f661f978631af53d9cb473cdef818b8833ca0e9 Mon Sep 17 00:00:00 2001 From: CY Fung Date: Tue, 7 Jun 2022 20:56:19 +0800 Subject: Week 168 First commit --- challenge-168/cheok-yin-fung/perl/ch-1.pl | 33 +++++++++++++++++ challenge-168/cheok-yin-fung/perl/ch-2.pl | 59 +++++++++++++++++++++++++++++++ 2 files changed, 92 insertions(+) create mode 100644 challenge-168/cheok-yin-fung/perl/ch-1.pl create mode 100644 challenge-168/cheok-yin-fung/perl/ch-2.pl diff --git a/challenge-168/cheok-yin-fung/perl/ch-1.pl b/challenge-168/cheok-yin-fung/perl/ch-1.pl new file mode 100644 index 0000000000..61ba32d69e --- /dev/null +++ b/challenge-168/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,33 @@ +#!/usr/bin/perl +# The Weekly Challenge 168 +# Task 1 Perrin Prime +use v5.24.0; +use warnings; +use List::Util qw/reduce none/; +use Math::BigInt::GMP; # [remark] +use Math::BigInt::Pari; # [remark] +use Math::Prime::Util::GMP qw/is_prime next_prime/; +use bigint try => 'GMP,Pari'; # [remark] +# remark: follow suggestions on POD of Math::Prime::Util + +my @perrin_primes = (2,3); +my ($ppnm3,$ppnm2,$ppnm1, $ppn) = (3,0,2,3); + +while (scalar @perrin_primes < 13) { + if (is_prime($ppn) == 2) { + push @perrin_primes, $ppn if none {$_ == $ppn} @perrin_primes; + say $ppn; + } + $ppnm3 = $ppnm2; + $ppnm2 = $ppnm1; + $ppnm1 = $ppn; + $ppn = $ppnm2 + $ppnm3; +} + +say join ", ", @perrin_primes; + +# time: +# real 0m0.078s +# user 0m0.056s +# sys 0m0.008s + diff --git a/challenge-168/cheok-yin-fung/perl/ch-2.pl b/challenge-168/cheok-yin-fung/perl/ch-2.pl new file mode 100644 index 0000000000..0518d1dbcd --- /dev/null +++ b/challenge-168/cheok-yin-fung/perl/ch-2.pl @@ -0,0 +1,59 @@ +#!/usr/bin/perl +# The Weekly Challenge 168 +# Task 2 Home Prime +# Usage: ch-2.pl [integer > 1] +use v5.24.0; +use warnings; +use List::Util qw/reduce/; +use Math::BigInt::GMP; # [remark] +use Math::BigInt::Pari; # [remark] +use Math::Prime::Util::GMP qw/is_prime next_prime/; +use bigint try => 'GMP,Pari'; # [remark] +# remark: follow suggestions on POD of Math::Prime::Util + + +say hp($ARGV[0]) if defined($ARGV[0]); + + + +sub hp { + my_hp($_[0],0); +} + + + +sub my_hp { + my $recur_depth = $_[1]; + + die "Walk so far but still cannot get result. :(\n" if $recur_depth > 10; + my $num = $_[0]; + if (is_prime($num) == 2) { + return $num; + } + + my @factors = (); + my $p = 2; + do { + if (!($num % $p)) { + push @factors, $p; + $num /= $p; + } + else { + $p = next_prime($p); + } + } while ($num != 1); + my $nxt = (reduce { $a . $b } @factors); + say " $nxt"; + return my_hp($nxt, ++$recur_depth); +} + +use Test::More tests => 5; +# test data from OEIS +ok hp(10) == 773; +ok hp(24) == 331_319; +ok hp(32) == 241_271; +ok hp(45) == 3_411_949; + +ok hp(44) == 22815088913; # this test spends approx 0.5 min (on CY's laptop). + +# ok hp(40) == 3314192745739; # this test spends approx. 2 min. -- cgit From 3cc61075c2564e35c4826d6431312e2b0dcf2179 Mon Sep 17 00:00:00 2001 From: CY Fung Date: Tue, 7 Jun 2022 21:17:33 +0800 Subject: to be improved within this week --- challenge-168/cheok-yin-fung/perl/ch-2.pl | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/challenge-168/cheok-yin-fung/perl/ch-2.pl b/challenge-168/cheok-yin-fung/perl/ch-2.pl index 0518d1dbcd..3289846cfe 100644 --- a/challenge-168/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-168/cheok-yin-fung/perl/ch-2.pl @@ -1,3 +1,5 @@ +# CAN BE IMPROVED + #!/usr/bin/perl # The Weekly Challenge 168 # Task 2 Home Prime @@ -39,7 +41,7 @@ sub my_hp { $num /= $p; } else { - $p = next_prime($p); + $p = next_prime($p); # CAN BE IMPROVED } } while ($num != 1); my $nxt = (reduce { $a . $b } @factors); -- cgit From ca71189e5959ea925a05c5b4412a64e5d10efe96 Mon Sep 17 00:00:00 2001 From: CY Fung Date: Sun, 12 Jun 2022 05:00:23 +0800 Subject: improve efficiency --- challenge-168/cheok-yin-fung/perl/ch-2.pl | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-) diff --git a/challenge-168/cheok-yin-fung/perl/ch-2.pl b/challenge-168/cheok-yin-fung/perl/ch-2.pl index 3289846cfe..7466f52b01 100644 --- a/challenge-168/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-168/cheok-yin-fung/perl/ch-2.pl @@ -27,7 +27,7 @@ sub hp { sub my_hp { my $recur_depth = $_[1]; - die "Walk so far but still cannot get result. :(\n" if $recur_depth > 10; + die "Walk so far but still cannot get result. :(\n" if $recur_depth > 20; my $num = $_[0]; if (is_prime($num) == 2) { return $num; @@ -35,27 +35,35 @@ sub my_hp { my @factors = (); my $p = 2; - do { + while ($num != 1) { if (!($num % $p)) { push @factors, $p; $num /= $p; } else { - $p = next_prime($p); # CAN BE IMPROVED + $p = next_prime($p); } - } while ($num != 1); + if ($p > sqrt $num) { + push @factors, $num; + last; + } + } my $nxt = (reduce { $a . $b } @factors); say " $nxt"; return my_hp($nxt, ++$recur_depth); } -use Test::More tests => 5; +use Test::More tests => 7; # test data from OEIS ok hp(10) == 773; ok hp(24) == 331_319; ok hp(32) == 241_271; +ok hp(40) == 3314192745739; +ok hp(44) == 22815088913; ok hp(45) == 3_411_949; +ok hp(8) == 3331113965338635107; -ok hp(44) == 22815088913; # this test spends approx 0.5 min (on CY's laptop). - -# ok hp(40) == 3314192745739; # this test spends approx. 2 min. +# time: +# real 0m1.963s +# user 0m1.946s +# sys 0m0.016s -- cgit From eb043eb2670bd851f4f237961dc12036927fc570 Mon Sep 17 00:00:00 2001 From: CY Fung Date: Sun, 12 Jun 2022 05:42:04 +0800 Subject: failed attempt: is_prime(BigInt) does not work --- challenge-168/cheok-yin-fung/perl/ch-2.pl | 27 +++++++++++++++++++-------- 1 file changed, 19 insertions(+), 8 deletions(-) diff --git a/challenge-168/cheok-yin-fung/perl/ch-2.pl b/challenge-168/cheok-yin-fung/perl/ch-2.pl index 7466f52b01..0f08ab3dc4 100644 --- a/challenge-168/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-168/cheok-yin-fung/perl/ch-2.pl @@ -28,7 +28,7 @@ sub my_hp { my $recur_depth = $_[1]; die "Walk so far but still cannot get result. :(\n" if $recur_depth > 20; - my $num = $_[0]; + my $num = Math::BigInt->new($_[0]); if (is_prime($num) == 2) { return $num; } @@ -36,24 +36,28 @@ sub my_hp { my @factors = (); my $p = 2; while ($num != 1) { - if (!($num % $p)) { + my $temp_num = $num; + if ( $num->bmod($p) == 0 ) { + say $p; push @factors, $p; - $num /= $p; + $num = $num->bdiv($p); } else { $p = next_prime($p); } - if ($p > sqrt $num) { + if ($p > $temp_num->bsqrt()) { push @factors, $num; last; } } - my $nxt = (reduce { $a . $b } @factors); + my $nxt = join "", @factors; say " $nxt"; return my_hp($nxt, ++$recur_depth); } -use Test::More tests => 7; + +=pod +use Test::More tests => 8; # test data from OEIS ok hp(10) == 773; ok hp(24) == 331_319; @@ -61,9 +65,16 @@ ok hp(32) == 241_271; ok hp(40) == 3314192745739; ok hp(44) == 22815088913; ok hp(45) == 3_411_949; -ok hp(8) == 3331113965338635107; +ok hp( 8) == 3331113965338635107; +ok hp(48) == 6161791591356884791277; -# time: +# time without the last hp(48) test case: # real 0m1.963s # user 0m1.946s # sys 0m0.016s +# +# time without the last hp(48) test case and use simply Math::Prime::Util : +# real 0m0.133s +# user 0m0.115s +# sys 0m0.011s + -- cgit From 87a49e0dde51ea6a342eaecef8820bf0b3bc5ead Mon Sep 17 00:00:00 2001 From: CY Fung Date: Sun, 12 Jun 2022 06:10:22 +0800 Subject: finalize Task 1 --- challenge-168/cheok-yin-fung/perl/ch-2.pl | 46 +++++++++++++------------------ 1 file changed, 19 insertions(+), 27 deletions(-) diff --git a/challenge-168/cheok-yin-fung/perl/ch-2.pl b/challenge-168/cheok-yin-fung/perl/ch-2.pl index 0f08ab3dc4..3e16406fbd 100644 --- a/challenge-168/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-168/cheok-yin-fung/perl/ch-2.pl @@ -1,5 +1,3 @@ -# CAN BE IMPROVED - #!/usr/bin/perl # The Weekly Challenge 168 # Task 2 Home Prime @@ -7,14 +5,10 @@ use v5.24.0; use warnings; use List::Util qw/reduce/; -use Math::BigInt::GMP; # [remark] -use Math::BigInt::Pari; # [remark] -use Math::Prime::Util::GMP qw/is_prime next_prime/; -use bigint try => 'GMP,Pari'; # [remark] -# remark: follow suggestions on POD of Math::Prime::Util - +use Math::Prime::Util qw/is_prime next_prime/; +use Math::BigInt; -say hp($ARGV[0]) if defined($ARGV[0]); +say hp($ARGV[0]) if defined($ARGV[0]) && $ARGV[0] != 1; @@ -27,8 +21,14 @@ sub hp { sub my_hp { my $recur_depth = $_[1]; + die "Number involed too large.\n" + if + Math::BigInt->new(18446744073709551616) # 2**64 + ->bcmp( Math::BigInt->new($_[0]) ) + == -1; + die "Walk so far but still cannot get result. :(\n" if $recur_depth > 20; - my $num = Math::BigInt->new($_[0]); + my $num = $_[0]; if (is_prime($num) == 2) { return $num; } @@ -36,27 +36,23 @@ sub my_hp { my @factors = (); my $p = 2; while ($num != 1) { - my $temp_num = $num; - if ( $num->bmod($p) == 0 ) { - say $p; + if (!($num % $p)) { push @factors, $p; - $num = $num->bdiv($p); + $num /= $p; } else { $p = next_prime($p); } - if ($p > $temp_num->bsqrt()) { + if ($p > sqrt $num) { push @factors, $num; last; } } - my $nxt = join "", @factors; + my $nxt = (reduce { $a . $b } @factors); say " $nxt"; return my_hp($nxt, ++$recur_depth); } - -=pod use Test::More tests => 8; # test data from OEIS ok hp(10) == 773; @@ -65,16 +61,12 @@ ok hp(32) == 241_271; ok hp(40) == 3314192745739; ok hp(44) == 22815088913; ok hp(45) == 3_411_949; + +# bigger cases; ok hp( 8) == 3331113965338635107; -ok hp(48) == 6161791591356884791277; +ok hp(20) == 3318308475676071413; -# time without the last hp(48) test case: -# real 0m1.963s -# user 0m1.946s +# real 0m5.553s +# user 0m5.535s # sys 0m0.016s -# -# time without the last hp(48) test case and use simply Math::Prime::Util : -# real 0m0.133s -# user 0m0.115s -# sys 0m0.011s -- cgit From a2d9f56f20f4773112b0656892fd4a0945fbe401 Mon Sep 17 00:00:00 2001 From: CY Fung Date: Sun, 12 Jun 2022 06:10:58 +0800 Subject: finalize Task 2 --- challenge-168/cheok-yin-fung/perl/ch-2.pl | 1 - 1 file changed, 1 deletion(-) diff --git a/challenge-168/cheok-yin-fung/perl/ch-2.pl b/challenge-168/cheok-yin-fung/perl/ch-2.pl index 3e16406fbd..ea156c4976 100644 --- a/challenge-168/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-168/cheok-yin-fung/perl/ch-2.pl @@ -4,7 +4,6 @@ # Usage: ch-2.pl [integer > 1] use v5.24.0; use warnings; -use List::Util qw/reduce/; use Math::Prime::Util qw/is_prime next_prime/; use Math::BigInt; -- cgit From 625339f89da8024a9de690f5ed163839989fa40a Mon Sep 17 00:00:00 2001 From: CY Fung Date: Sun, 12 Jun 2022 11:26:01 +0800 Subject: Task 2 big num --- challenge-168/cheok-yin-fung/perl/ch-2.pl | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/challenge-168/cheok-yin-fung/perl/ch-2.pl b/challenge-168/cheok-yin-fung/perl/ch-2.pl index ea156c4976..6986c4809a 100644 --- a/challenge-168/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-168/cheok-yin-fung/perl/ch-2.pl @@ -18,20 +18,20 @@ sub hp { sub my_hp { + my $num = $_[0]; my $recur_depth = $_[1]; - - die "Number involed too large.\n" + die "Number involved too large.\n" if - Math::BigInt->new(18446744073709551616) # 2**64 - ->bcmp( Math::BigInt->new($_[0]) ) - == -1; + Math::BigInt->new("18446744073709551616") # 2**64 + ->ble( Math::BigInt->new($num) ); + - die "Walk so far but still cannot get result. :(\n" if $recur_depth > 20; - my $num = $_[0]; if (is_prime($num) == 2) { return $num; } + die "Walk so far but still cannot get result. :(\n" if $recur_depth > 20; + my @factors = (); my $p = 2; while ($num != 1) { @@ -47,7 +47,7 @@ sub my_hp { last; } } - my $nxt = (reduce { $a . $b } @factors); + my $nxt = join "", @factors; say " $nxt"; return my_hp($nxt, ++$recur_depth); } -- cgit From 0d0f645575dc2177e765b1e4b64806f591663199 Mon Sep 17 00:00:00 2001 From: CY Fung Date: Sun, 12 Jun 2022 11:33:20 +0800 Subject: Task 1 final --- challenge-168/cheok-yin-fung/perl/ch-1.pl | 14 +++++--------- challenge-168/cheok-yin-fung/perl/ch-2.pl | 1 + 2 files changed, 6 insertions(+), 9 deletions(-) diff --git a/challenge-168/cheok-yin-fung/perl/ch-1.pl b/challenge-168/cheok-yin-fung/perl/ch-1.pl index 61ba32d69e..3f51cb4766 100644 --- a/challenge-168/cheok-yin-fung/perl/ch-1.pl +++ b/challenge-168/cheok-yin-fung/perl/ch-1.pl @@ -3,12 +3,8 @@ # Task 1 Perrin Prime use v5.24.0; use warnings; -use List::Util qw/reduce none/; -use Math::BigInt::GMP; # [remark] -use Math::BigInt::Pari; # [remark] -use Math::Prime::Util::GMP qw/is_prime next_prime/; -use bigint try => 'GMP,Pari'; # [remark] -# remark: follow suggestions on POD of Math::Prime::Util +use List::Util qw/none/; +use Math::Prime::Util qw/is_prime next_prime/; my @perrin_primes = (2,3); my ($ppnm3,$ppnm2,$ppnm1, $ppn) = (3,0,2,3); @@ -27,7 +23,7 @@ while (scalar @perrin_primes < 13) { say join ", ", @perrin_primes; # time: -# real 0m0.078s -# user 0m0.056s -# sys 0m0.008s +# real 0m0.025s +# user 0m0.017s +# sys 0m0.009s diff --git a/challenge-168/cheok-yin-fung/perl/ch-2.pl b/challenge-168/cheok-yin-fung/perl/ch-2.pl index 6986c4809a..00406d25ef 100644 --- a/challenge-168/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-168/cheok-yin-fung/perl/ch-2.pl @@ -43,6 +43,7 @@ sub my_hp { $p = next_prime($p); } if ($p > sqrt $num) { + say "useful"; push @factors, $num; last; } -- cgit From e66b82a635ca6306adf4b7d46e8b675159e47c8e Mon Sep 17 00:00:00 2001 From: CY Fung Date: Sun, 12 Jun 2022 11:34:11 +0800 Subject: Task 1 final --- challenge-168/cheok-yin-fung/perl/ch-1.pl | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-168/cheok-yin-fung/perl/ch-1.pl b/challenge-168/cheok-yin-fung/perl/ch-1.pl index 3f51cb4766..faf90a9bb3 100644 --- a/challenge-168/cheok-yin-fung/perl/ch-1.pl +++ b/challenge-168/cheok-yin-fung/perl/ch-1.pl @@ -4,7 +4,7 @@ use v5.24.0; use warnings; use List::Util qw/none/; -use Math::Prime::Util qw/is_prime next_prime/; +use Math::Prime::Util qw/is_prime/; my @perrin_primes = (2,3); my ($ppnm3,$ppnm2,$ppnm1, $ppn) = (3,0,2,3); -- cgit