diff options
43 files changed, 3285 insertions, 2149 deletions
diff --git a/challenge-145/pokgopun/README b/challenge-145/pokgopun/README new file mode 100644 index 0000000000..33dfd303a4 --- /dev/null +++ b/challenge-145/pokgopun/README @@ -0,0 +1 @@ +Solution by PokGoPun diff --git a/challenge-145/pokgopun/go/ch-1.go b/challenge-145/pokgopun/go/ch-1.go new file mode 100644 index 0000000000..d39063d4ef --- /dev/null +++ b/challenge-145/pokgopun/go/ch-1.go @@ -0,0 +1,53 @@ +// You are given 2 arrays of same size, @a and @b. +// Write a script to implement Dot Product. +// Usage: go run ch-1.go 1,2,3 4,5,6 +package main + +import ( + "fmt" + "log" + "os" + "strconv" + "strings" +) + +func main() { + var sample [][]int + if len(os.Args) > 2 { + m := map[int]struct{}{} + for _, v := range os.Args[1:] { + strs := strings.Split(v, ",") + m[len(strs)] = struct{}{} + nums := make([]int, len(strs)) + for i, v := range strs { + n, err := strconv.Atoi(v) + if err != nil { + log.Fatal(err) + } + nums[i] = n + } + sample = append(sample, nums) + } + if len(m) > 1 { + log.Fatal("Arrays are not in the same size") + } + } else { + sample = [][]int{ + []int{1, 2, 3}, + []int{4, 5, 6}, + } + } + fmt.Println(sample, "=>", dp(sample)) +} + +func dp(ss [][]int) (r int) { + l := len(ss[0]) + for i := 0; i < l; i++ { + n := 1 + for j := 0; j < len(ss); j++ { + n *= ss[j][i] + } + r += n + } + return r +} diff --git a/challenge-145/pokgopun/go/ch-2.go b/challenge-145/pokgopun/go/ch-2.go new file mode 100644 index 0000000000..9f75a558ec --- /dev/null +++ b/challenge-145/pokgopun/go/ch-2.go @@ -0,0 +1,84 @@ +// Write a script to create a Palindromic Tree for the given string. +// All examples do not have a case that a letter happens more than twice in given words but we will handle the case as well +// Here additional examples for the case: banana, redeemable, deterministic, heterogeneity, initiation, monopolous, honolulu +package main + +import ( + "fmt" + "os" + "sort" + "strings" +) + +func main() { + var sample []string + if len(os.Args) > 1 { + sample = os.Args[1:] + } else { + sample = []string{ + "redivider", + "deific", + "rotors", + "challenge", + "champion", + "christmas", + "banana", + "redeemable", + "deterministic", + "heterogeneity", + "initiation", + "monopolous", + "honolulu", + } + } + for _, v := range sample { + p := newPldt(v) + fmt.Println(p) + } +} + +type pldt struct { + word string + seen map[string]bool + cpos map[byte][]int + vals []string +} + +func newPldt(s string) (p pldt) { + p.word = s + p.seen = make(map[string]bool) + p.cpos = make(map[byte][]int) + for i, v := range []byte(p.word) { + p.cpos[v] = append(p.cpos[v], i) + } + for _, c := range []byte(p.word) { + if p.seen[string(c)] { + continue + } + p.seen[string(c)] = true + p.vals = append(p.vals, string(c)) + for i, pos1 := range p.cpos[c] { + for _, pos2 := range p.cpos[c][i+1:] { + o := p.word[pos1 : pos2+1] + if p.seen[o] { + continue + } + r := []byte(o) + sort.SliceStable(r, func(i, j int) bool { + return true + }) + if o == string(r) { + p.vals = append(p.vals, o) + p.seen[o] = true + } + } + } + } + return p +} + +func (p pldt) String() string { + var b strings.Builder + b.WriteString("Input: '" + p.word + "'\nOutput: " + strings.Join(p.vals, " ") + "\n") + return b.String() +} diff --git a/challenge-146/pokgopun/go/ch-2.go b/challenge-146/pokgopun/go/ch-2.go index b8aea49f0f..a8545314f3 100644 --- a/challenge-146/pokgopun/go/ch-2.go +++ b/challenge-146/pokgopun/go/ch-2.go @@ -2,35 +2,22 @@ package main import ( "fmt" - "log" "os" ) func main() { - samples := [][2]uint{ - [2]uint{3, 5}, - [2]uint{4, 3}, - } + var sample []string if len(os.Args) > 1 { - var sample [2]uint - _, err := fmt.Sscanf(os.Args[1], "%d/%d", &sample[0], &sample[1]) - if err != nil { - log.Fatal(err) + sample = os.Args[1:] + } else { + sample = []string{ + "redivider", + "deific", + "rotors", + "challenge", + "champion", + "christmas", } - samples = [][2]uint{sample} - } - for _, v := range samples { - p := parent(v) - gp := parent(p) - fmt.Printf("Input: member = '%d/%d'\nOutput: parent ='%d/%d' and grandparent = '%d/%d'\n", v[0], v[1], p[0], p[1], gp[0], gp[1]) - } -} - -func parent(s [2]uint) [2]uint { - if s[0] > s[1] { - return [2]uint{s[0] - s[1], s[1]} - } else if s[0] < s[1] { - return [2]uint{s[0], s[1] - s[0]} } - return [2]uint{1, 1} + fmt.Println(sample) } diff --git a/challenge-168/e-choroba/perl/ch-1.pl b/challenge-168/e-choroba/perl/ch-1.pl new file mode 100755 index 0000000000..4f1355475d --- /dev/null +++ b/challenge-168/e-choroba/perl/ch-1.pl @@ -0,0 +1,24 @@ +#!/usr/bin/perl +use warnings; +use strict; +use Syntax::Construct qw{ // }; + +use Math::Prime::Util qw{ is_prime }; + +sub perrin_prime { + my ($length) = @_; + my @perrin_sliding = (3, 0, 2); + my @perrin_primes; + while (@perrin_primes < $length) { + push @perrin_sliding, shift(@perrin_sliding) + $perrin_sliding[0]; + push @perrin_primes, $perrin_sliding[1] + if $perrin_sliding[1] > ($perrin_primes[-1] // 0) + && is_prime($perrin_sliding[1]); + } + return @perrin_primes +} + +use Test::More tests => 1; + +is_deeply [perrin_prime(13)], [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, + 43721, 1442968193, 792606555396977]; diff --git a/challenge-168/e-choroba/perl/ch-2.pl b/challenge-168/e-choroba/perl/ch-2.pl new file mode 100755 index 0000000000..f53c124f35 --- /dev/null +++ b/challenge-168/e-choroba/perl/ch-2.pl @@ -0,0 +1,17 @@ +#!/usr/bin/perl +use warnings; +use strict; + +use Math::Prime::Util qw{ factor is_prime }; + +sub home_prime { + my ($i) = @_; + my $concat = join "", sort { $a <=> $b } factor($i); + + return $concat if is_prime($concat); + + return home_prime($concat) +} + +use Test::More tests => 1; +is home_prime(10), 773; diff --git a/challenge-168/eric-cheung/python/ch-1.py b/challenge-168/eric-cheung/python/ch-1.py new file mode 100755 index 0000000000..df5ae80e8e --- /dev/null +++ b/challenge-168/eric-cheung/python/ch-1.py @@ -0,0 +1,39 @@ +
+## Remarks
+## https://en.wikipedia.org/wiki/Perrin_number
+
+import math
+
+def IsPrime(nInput):
+
+ for nDiv in range(2, int(math.sqrt(nInput)) + 1):
+ if nInput % nDiv == 0:
+ return False
+
+ return True
+
+arrPerrinPrime = []
+arrPerrinNum = []
+
+arrPerrinNum.append(3)
+arrPerrinNum.append(0)
+arrPerrinNum.append(2)
+
+arrPerrinPrime.append(2)
+arrPerrinPrime.append(3)
+
+while len(arrPerrinPrime) < 13:
+ nNuNum = arrPerrinNum[-2] + arrPerrinNum[-3]
+ arrPerrinNum.append(nNuNum)
+
+ if not IsPrime(nNuNum):
+ continue
+
+ nCount = arrPerrinPrime.count(nNuNum)
+
+ if nCount > 0:
+ continue
+
+ arrPerrinPrime.append(nNuNum)
+
+print (arrPerrinPrime)
diff --git a/challenge-168/eric-cheung/python/ch-2.py b/challenge-168/eric-cheung/python/ch-2.py new file mode 100755 index 0000000000..4bcd6f1e3a --- /dev/null +++ b/challenge-168/eric-cheung/python/ch-2.py @@ -0,0 +1,57 @@ +
+## Remarks
+## https://en.wikipedia.org/wiki/Home_prime
+
+import math
+
+def IsPrime(nInput):
+
+ for nDiv in range(2, int(math.sqrt(nInput)) + 1):
+ if nInput % nDiv == 0:
+ return False
+
+ return True
+
+
+def PrimeFact(nOrigInput):
+
+ nInput = nOrigInput
+ arrPrimeFact = []
+
+ for nDiv in range(2, nOrigInput):
+
+ while nInput % nDiv == 0 and nInput > 0:
+
+ nInput = nInput / nDiv
+ arrPrimeFact.append(nDiv)
+
+ if nInput == 0:
+ break
+
+ return arrPrimeFact
+
+
+def ConcatArray(arrInput):
+
+ strResult = ""
+
+ for arrElem in arrInput:
+ strResult = strResult + str(arrElem)
+
+ return int(strResult)
+
+
+## print (PrimeFact(511))
+## print (ConcatArray(PrimeFact(511)))
+## print (ConcatArray(PrimeFact(8)))
+
+
+nOrigInputNum = 10
+
+nInputNum = nOrigInputNum
+
+while not IsPrime(nInputNum):
+ nInputNum = ConcatArray(PrimeFact(nInputNum))
+
+print ("HP(" + str(nOrigInputNum) + ") = " + str(nInputNum))
+
diff --git a/challenge-168/jo-37/perl/ch-1.pl b/challenge-168/jo-37/perl/ch-1.pl new file mode 100755 index 0000000000..8351305463 --- /dev/null +++ b/challenge-168/jo-37/perl/ch-1.pl @@ -0,0 +1,155 @@ +#!/usr/bin/perl -s + +use v5.16; +use Test2::V0 '!array'; +use bigint; +use List::Gen qw(:iterate :zip :source); +use List::Util qw(product); +use Math::Prime::Util qw(is_prime gcd); +use experimental qw(signatures postderef); + +our ($tests, $examples, $iv, $f); +$iv ||= '3, 0, 2'; +$f ||= '1, 1'; + +run_tests() if $tests || $examples; # does not return + +die <<EOS unless @ARGV; +usage: $0 [-examples] [-tests] [-f=F1,...,Fl] [-iv=S1,...Sk] [N] + +-examples + run the examples from the challenge + +-tests + run some tests + +-f=F1,...,Fl + Coefficients for the linear recurrence relation. + +-iv=S1,...,Sk + Starting values for the generated sequence. + +N + Print the first N prime numbers from the generated sequence. + + The sequence starts with the values S1,...,Sk and has the + linear recurrence relation: + S(n) = F(1) * S(n - k) + ... + F(k) * S(n - 1) for n > k. + Selecting unique primes from this sequence. + +Some known prime sequences: +IV=0,1 F=1,1: Fibonacci +IV=2,1 F=1,1: Lucas +IV=1,1,1 F=1,1: Padovan +IV=3,0,2 F=1,1: Perrin (default) +IV=0,1 F=1,2: Pell +IV=0,1 F=2,1: Jacobsthal + +CAUTION: Improper choice of IV and F will cause an endless loop! + +EOS + + +### Input and Output + +main: { + # Explicit conversion to Math::BigInt is required for a set of + # variables so that all newly generated values inherit therefrom. + # Linear factors: + my $f = [map Math::BigInt->new($_), split /, */, $f]; + # Initial values: + my $iv = [split /, */, $iv]; + + # "say(n)" prints the first n generated elements. + lin_recur_primes($iv, $f)->say(shift); +} + + +### Implementation + +# The solution to task 2 from challenge 154 with different starting +# values could be reused to solve this task. But this would by boring +# and thus the task will be generalized here. +# +# The excellent Math::Prime::Util ennobles List::Gen by referencing it in +# the "SEE ALSO" section. Indeed, it looks very cool but comes with a +# serious flaw: There has not been any development for over 10 years and +# one of the tests is broken. Needed "--force" to install. IMHO the +# test result is ok, but the expected outcome is not. +# "Failed test 'map & \(1 .. 3), 1 .. 2'" +# +# Building a generator for a sequence having the initial values +# S(1),...,S(k) and a recurrence relation defined by a linear +# combination of preceding elements: +# S(n) = F(1) * S(n - k) + ... + F(k) * S(n - 1) for n > k. +# and taking unique primes thereof. +# +sub lin_recur_primes ($s, $f) { + + # Lazily extend the initial sequence using the recurrence relation. + ($s + iterate {($s = [$s->@[1 .. $#$s], + tuples($f, $s)->map('product @$_')->sum])->[-1] + })->uniq->filter(sub {is_prime $_}); +} + + +### Examples and tests + +sub run_tests { + SKIP: { + skip "examples" unless $examples; + + # "take" returns the given number of elements. + is lin_recur_primes([3, 0, 2], [1, 1])->take(13), + [3, 2, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, + 792606555396977], 'task 1'; + } + + SKIP: { + skip "tests" unless $tests; + + # "get" accesses elements by a zero-based index. Thus "get(15)" + # is *three* behind the last from "take(13)". + is lin_recur_primes([3, 0, 2], [1, 1])->get(15), + '22584751787583336797527561822649328254745329', + 'Perrin prime from http://oeis.org/A074788'; + + is lin_recur_primes([0, 1], [1, 1])->take(11), + [2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, + 2971215073], + 'Fibonacci primes from Wiki'; + + is lin_recur_primes([1, 1, 1], [1, 1])->take(12), + [2, 3, 5, 7, 37, 151, 3329, 23833, 13091204281, 3093215881333057, + 1363005552434666078217421284621279933627102780881053358473, + 1558877695141608507751098941899265975115403618621811951868598809164180630185566719], + 'Padovan primes from Wiki'; + + is lin_recur_primes([2, 1], [1, 1])->take(15), + [2, 3, 7, 11, 29, 47, 199, 521, 2207, 3571, 9349, 3010349, + 54018521, 370248451, 6643838879], + 'Lucas primes from Wiki'; + + is lin_recur_primes([3, 1], [1, 1])->take(20), + [3, 5, 23, 37, 97, 157, 1741, 11933, 50549, 214129, 560597, + 16276621, 180510493, 398386576261, 1042989597313, + 41305516996050613, 174972977841043309, 13300248193487978669, + 238663270054423392193, 624828552868675407173], + 'A091157'; + + is lin_recur_primes([0, 1], [1, 2])->take(8), + [2, 5, 29, 5741, 33461, 44560482149, 1746860020068409, + 68480406462161287469], + 'Pell primes from Wiki'; + + is lin_recur_primes([0, 1], [2, 1])->take(15), + [3, 5, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, + 2932031007403, 768614336404564651, 201487636602438195784363, + 845100400152152934331135470251, + 56713727820156410577229101238628035243], + 'Jacobsthal primes from Wiki'; + } + + done_testing; + exit; +} diff --git a/challenge-168/julien-fiegehenn/perl/ch-1.pl b/challenge-168/julien-fiegehenn/perl/ch-1.pl new file mode 100644 index 0000000000..2e331a2415 --- /dev/null +++ b/challenge-168/julien-fiegehenn/perl/ch-1.pl @@ -0,0 +1,48 @@ +#!/usr/bin/perl +use strict; +use warnings; +use feature 'say'; + +# Task 1: Perrin Prime +# Submitted by: Roger Bell_West +# 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. + +# f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977] + +sub is_prime { + my $n = shift; + return 0 if $n < 2; + return 1 if $n == 2; + return 0 if $n % 2 == 0; + for (my $i = 3; $i <= sqrt($n); $i += 2) { + return 0 if $n % $i == 0; + } + return 1; +} + +sub perrin_primes { + my $n = shift; + my %primes = map { $_ => 1 } 2, 3; + my @perrin = (3, 0, 2); + my $i = 3; + while (keys %primes < $n) { + $perrin[$i] = $perrin[$i - 2] + $perrin[$i - 3]; + if (is_prime($perrin[$i])) { + $primes{$perrin[$i]} = 1; + } + $i++; + } + return sort { $a <=> $b } keys %primes; +} + +my @primes = perrin_primes(13); +say "@primes"; + +__END__ +use Test::More; +is_deeply \@primes, [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977]; +done_testing;
\ No newline at end of file diff --git a/challenge-168/julien-fiegehenn/perl/ch-2.pl b/challenge-168/julien-fiegehenn/perl/ch-2.pl new file mode 100644 index 0000000000..9e9812d039 --- /dev/null +++ b/challenge-168/julien-fiegehenn/perl/ch-2.pl @@ -0,0 +1,78 @@ +#!/usr/bin/perl +use strict; +use warnings; +use feature 'say'; + +# Task 2: Home Prime +# Submitted by: Mohammad S Anwar +# 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. + +# Further information can be found on Wikipedia and OEIS. + +# Example +# As given in the Wikipedia page, + +# HP(10) = 773, as 10 factors as 2×5 yielding HP10(1) = 25, 25 factors as 5×5 yielding HP10(2) = HP25(1) = 55, 55 = 5×11 implies HP10(3) = HP25(2) = HP55(1) = 511, and 511 = 7×73 gives HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773, a prime number. + +# written with github copilot + +# calculate the prime factors of a number +sub prime_factors { + my $n = shift; + my @factors = (); + my $i = 2; + while ($n > 1) { + while ($n % $i == 0) { + push @factors, $i; + $n /= $i; + } + $i++; + } + return @factors; +} + +sub is_prime { + my $n = shift; + return 0 if $n < 2; + return 1 if $n == 2; + return 0 if $n % 2 == 0; + for (my $i = 3; $i <= sqrt($n); $i += 2) { + return 0 if $n % $i == 0; + } + return 1; +} + +# calculate the home prime of a 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. +sub home_prime { + my $n = shift; + + return $n if is_prime($n); + return home_prime(join '', prime_factors($n)); +} + +# a version of home_prime that produces debug output at every step +sub home_prime_debug { + my $n = shift; + + say "n = $n"; + return $n if is_prime($n); + my @factors = prime_factors($n); + say "factors = @factors"; + return home_prime_debug(join '', @factors); +} + +__END__ + +use Test::More; +is_deeply [prime_factors(10)], [2, 5]; +is_deeply [prime_factors(13)], [13]; +is_deeply [prime_factors(14)], [2, 7]; + +is home_prime(10), 773; +is home_prime_debug(10), 773; +done_testing;
\ No newline at end of file diff --git a/challenge-168/lubos-kolouch/perl/ch-1.pl b/challenge-168/lubos-kolouch/perl/ch-1.pl new file mode 100644 index 0000000000..956d2822e4 --- /dev/null +++ b/challenge-168/lubos-kolouch/perl/ch-1.pl @@ -0,0 +1,33 @@ +package main; +use strict; +use warnings; +use Math::Prime::Util qw(is_prime); + +sub generate_perrin_sequence { + my $n = shift; + my @perrin_sequence = ( 3, 0, 2 ); + + my %perrin_primes; + + while ( scalar keys %perrin_primes < $n ) { + my $next_number = $perrin_sequence[-3] + $perrin_sequence[-2]; + push @perrin_sequence, $next_number; + $perrin_primes{$next_number} = 1 if is_prime($next_number); + } + + my @primes = sort { $a <=> $b } keys %perrin_primes; + + return \@primes; +} + +use Test::More; + +is_deeply( + generate_perrin_sequence(13), + [ 2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, + 792606555396977 + ] +); + +done_testing; +1; diff --git a/challenge-168/lubos-kolouch/python/ch-1.py b/challenge-168/lubos-kolouch/python/ch-1.py new file mode 100644 index 0000000000..8c8790c5dc --- /dev/null +++ b/challenge-168/lubos-kolouch/python/ch-1.py @@ -0,0 +1,39 @@ +""" Challenge 168 Task 1 LK Python """ + +from sympy import isprime + + +def generate_perrin_primes(n: int) -> list: + """ + Generate all primes up to n using the Perrin sequence. + """ + perrin_sequence = [3, 0, 2] + + perrin_primes: dict = {} + + while len(perrin_primes.keys()) < n: + + next_number = perrin_sequence[-3] + perrin_sequence[-2] + perrin_sequence.append(next_number) + + if isprime(next_number): + perrin_primes[next_number] = True + + return sorted(perrin_primes.keys()) + + +assert generate_perrin_primes(13) == [ + 2, + 3, + 5, + 7, + 17, + 29, + 277, + 367, + 853, + 14197, + 43721, + 1442968193, + 792606555396977, +] diff --git a/challenge-168/massa/raku/ch-1.raku b/challenge-168/massa/raku/ch-1.raku new file mode 100644 index 0000000000..2fbde00b8c --- /dev/null +++ b/challenge-168/massa/raku/ch-1.raku @@ -0,0 +1,2 @@ +use v6; +(3, 0, 2, * + * + 0 * * ... *).grep(*.is-prime).unique.head(13).sort.say diff --git a/challenge-168/massa/raku/ch-2.raku b/challenge-168/massa/raku/ch-2.raku new file mode 100644 index 0000000000..535eaa16fa --- /dev/null +++ b/challenge-168/massa/raku/ch-2.raku @@ -0,0 +1,28 @@ +use v6; + +my sub factors(int \x is copy) { + my int $possible-factor = 2; + gather { + while x > 1 { + if $possible-factor.is-prime && x %% $possible-factor { + take $possible-factor; + x div= $possible-factor + } else { + Nil until is-prime ++$possible-factor + } + } + } +} + +my sub hp(int \x is copy) { + loop { + given +[~] factors x { + .return if .is-prime; + x = $_ + } + } +} + +sub MAIN(Int() \n where * > 1) { + say hp n +} diff --git a/challenge-168/robert-dicicco/julia/ch-1.jl b/challenge-168/robert-dicicco/julia/ch-1.jl new file mode 100644 index 0000000000..45d1bbcd64 --- /dev/null +++ b/challenge-168/robert-dicicco/julia/ch-1.jl @@ -0,0 +1,37 @@ +#!julia.exe + +# AUTHOR: Robert DiCicco +# DATE: 2022-06-06 +# Challenge 168 Perrin Primes ( Julia ) + +using Primes + +perrin = [3,0,2] + +results = [] + +PRIME_COUNT = 13 + +i = 0 + +while i <= PRIME_COUNT + + slots = size(perrin,1) + + calc_val = perrin[slots - 1] + perrin[slots - 2] # since julia arrays are option base 1 + + push!(perrin,calc_val) + + if isprime(calc_val) + + push!(results,calc_val) + + global i += 1 + + end + +end + +results = unique!(sort(results)) + +println(results) diff --git a/challenge-168/robert-dicicco/julia/ch-2.jl b/challenge-168/robert-dicicco/julia/ch-2.jl new file mode 100644 index 0000000000..e486810da1 --- /dev/null +++ b/ |