From 76fb2113ab5563b3d142fc1f66ffc1b64fced916 Mon Sep 17 00:00:00 2001 From: Adam Russell Date: Sun, 12 Jun 2022 12:37:18 -0400 Subject: initial commit --- challenge-168/adam-russell/blog.txt | 1 + challenge-168/adam-russell/blog1.txt | 1 + challenge-168/adam-russell/java/ch-1.java | 83 ++++++++++++++++++++++++++++ challenge-168/adam-russell/java/ch-2.java | 89 +++++++++++++++++++++++++++++++ challenge-168/adam-russell/perl/ch-1.pl | 25 +++++++++ challenge-168/adam-russell/perl/ch-2.pl | 37 +++++++++++++ challenge-168/adam-russell/prolog/ch-1.p | 11 ++++ challenge-168/adam-russell/prolog/ch-2.p | 41 ++++++++++++++ 8 files changed, 288 insertions(+) create mode 100644 challenge-168/adam-russell/blog.txt create mode 100644 challenge-168/adam-russell/blog1.txt create mode 100644 challenge-168/adam-russell/java/ch-1.java create mode 100644 challenge-168/adam-russell/java/ch-2.java create mode 100644 challenge-168/adam-russell/perl/ch-1.pl create mode 100644 challenge-168/adam-russell/perl/ch-2.pl create mode 100644 challenge-168/adam-russell/prolog/ch-1.p create mode 100644 challenge-168/adam-russell/prolog/ch-2.p diff --git a/challenge-168/adam-russell/blog.txt b/challenge-168/adam-russell/blog.txt new file mode 100644 index 0000000000..82830c3290 --- /dev/null +++ b/challenge-168/adam-russell/blog.txt @@ -0,0 +1 @@ +http://www.rabbitfarm.com/cgi-bin/blosxom/perl/2022/06/12 diff --git a/challenge-168/adam-russell/blog1.txt b/challenge-168/adam-russell/blog1.txt new file mode 100644 index 0000000000..d9c877c79a --- /dev/null +++ b/challenge-168/adam-russell/blog1.txt @@ -0,0 +1 @@ +http://www.rabbitfarm.com/cgi-bin/blosxom/prolog/2022/06/12 diff --git a/challenge-168/adam-russell/java/ch-1.java b/challenge-168/adam-russell/java/ch-1.java new file mode 100644 index 0000000000..f028a2ba2f --- /dev/null +++ b/challenge-168/adam-russell/java/ch-1.java @@ -0,0 +1,83 @@ +import java.util.Random; +import java.util.ArrayList; +import java.math.BigInteger; +import java.util.Collections; + +/** Class MillerRabin **/ +/* Slightly modified version of code taken from + https://www.sanfoundry.com/java-program-miller-rabin-primality-test-algorithm/ */ +class MillerRabin{ + private static final int ITERATIONS = 7; + /** Function to check if prime or not **/ + public static boolean isPrime(long n){ + /** base case **/ + if (n == 0 || n == 1) + return false; + /** base case - 2 is prime **/ + if (n == 2) + return true; + /** an even number other than 2 is composite **/ + if (n % 2 == 0) + return false; + long s = n - 1; + while (s % 2 == 0) + s /= 2; + Random rand = new Random(); + for (int i = 0; i < ITERATIONS; i++){ + long r = Math.abs(rand.nextLong()); + long a = r % (n - 1) + 1, temp = s; + long mod = modPow(a, temp, n); + while (temp != n - 1 && mod != 1 && mod != n - 1){ + mod = mulMod(mod, mod, n); + temp *= 2; + } + if (mod != n - 1 && temp % 2 == 0) + return false; + } + return true; + } + /** Function to calculate (a ^ b) % c **/ + public static long modPow(long a, long b, long c){ + long res = 1; + for (int i = 0; i < b; i++){ + res *= a; + res %= c; + } + return res % c; + } + /** Function to calculate (a * b) % c **/ + public static long mulMod(long a, long b, long mod){ + return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(mod)).longValue(); + } +} + +class PerrinPrimes{ + private static ArrayList nPerrinPrimesR(int n, ArrayList perrins, ArrayList perrinPrimes){ + if(perrinPrimes.size() == n){ + return perrinPrimes; + } + else{ + perrins.add(new Integer(((Integer)perrins.get(perrins.size() - 3)).intValue() + ((Integer)perrins.get(perrins.size() - 2)).intValue())); + if(MillerRabin.isPrime(((Integer)perrins.get(perrins.size() - 1)).intValue())) + perrinPrimes.add(perrins.get(perrins.size() - 1)); + } + return nPerrinPrimesR(n, perrins, perrinPrimes); + } + + public static ArrayList nPerrinPrimes(int n){ + ArrayList perrins = new ArrayList(); + perrins.add(new Integer(3)); + perrins.add(new Integer(0)); + perrins.add(new Integer(2)); + return nPerrinPrimesR(n, perrins, new ArrayList()); + } + + public static void main(String[] args){ + ArrayList perrinPrimes = PerrinPrimes.nPerrinPrimes(13); + Collections.sort(perrinPrimes); + for(int i = 0; i < perrinPrimes.size() - 1; i++){ + System.out.print(perrinPrimes.get(i) + ", "); + } + System.out.println(perrinPrimes.get(perrinPrimes.size() - 1)); + } +} \ No newline at end of file diff --git a/challenge-168/adam-russell/java/ch-2.java b/challenge-168/adam-russell/java/ch-2.java new file mode 100644 index 0000000000..ed2906c49f --- /dev/null +++ b/challenge-168/adam-russell/java/ch-2.java @@ -0,0 +1,89 @@ +import java.util.Random; +import java.util.ArrayList; +import java.math.BigInteger; +import java.util.Collections; + +/** Class MillerRabin **/ +/* Slightly modified version of code taken from + https://www.sanfoundry.com/java-program-miller-rabin-primality-test-algorithm/ */ +class MillerRabin{ + private static final int ITERATIONS = 7; + /** Function to check if prime or not **/ + public static boolean isPrime(long n){ + /** base case **/ + if (n == 0 || n == 1) + return false; + /** base case - 2 is prime **/ + if (n == 2) + return true; + /** an even number other than 2 is composite **/ + if (n % 2 == 0) + return false; + long s = n - 1; + while (s % 2 == 0) + s /= 2; + Random rand = new Random(); + for (int i = 0; i < ITERATIONS; i++){ + long r = Math.abs(rand.nextLong()); + long a = r % (n - 1) + 1, temp = s; + long mod = modPow(a, temp, n); + while (temp != n - 1 && mod != 1 && mod != n - 1){ + mod = mulMod(mod, mod, n); + temp *= 2; + } + if (mod != n - 1 && temp % 2 == 0) + return false; + } + return true; + } + /** Function to calculate (a ^ b) % c **/ + public static long modPow(long a, long b, long c){ + long res = 1; + for (int i = 0; i < b; i++){ + res *= a; + res %= c; + } + return res % c; + } + /** Function to calculate (a * b) % c **/ + public static long mulMod(long a, long b, long mod){ + return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(mod)).longValue(); + } +} + +class HomePrime{ + private static ArrayList primeFactors(long n){ + ArrayList factors = new ArrayList(); + while (n % 2 == 0){ + factors.add(new Long(2)); + n = n / 2; + } + for(long i = 3; i <= Math.sqrt(n); i = i + 2){ + while (n % i == 0){ + factors.add(new Long(i)); + n = n / i; + } + } + if(n > 2) + factors.add(new Long(n)); + return factors; + } + + public static long homePrime(long n){ + ArrayList primeFactors = primeFactors(n); + String s = ""; + for(int i = 0; i < primeFactors.size(); i++){ + s += ((Long) primeFactors.get(i)).toString(); + } + if(MillerRabin.isPrime(Long.valueOf(s).longValue())){ + return Long.valueOf(s).longValue(); + } + return homePrime(Long.valueOf(s).longValue()); + } + + public static void main(String[] args){ + System.out.println(HomePrime.homePrime(10)); + System.out.println(HomePrime.homePrime(16)); + System.out.println(HomePrime.homePrime(48)); + } +} \ No newline at end of file diff --git a/challenge-168/adam-russell/perl/ch-1.pl b/challenge-168/adam-russell/perl/ch-1.pl new file mode 100644 index 0000000000..b726a67f63 --- /dev/null +++ b/challenge-168/adam-russell/perl/ch-1.pl @@ -0,0 +1,25 @@ +use strict; +use warnings; +no warnings q/recursion/; +## +# Calculate the first 13 Perrin Primes. +## +use boolean; +use Math::Primality qw/is_prime/; + +sub n_perrin_prime_r{ + my($n, $perrins, $perrin_primes) = @_; + return $perrin_primes if keys %{$perrin_primes} == $n; + my $perrin = $perrins->[@{$perrins} - 3] + $perrins->[@{$perrins} - 2]; + push @{$perrins}, $perrin; + $perrin_primes->{$perrin} = -1 if is_prime($perrin); + n_perrin_prime_r($n, $perrins, $perrin_primes); +} + +sub perrin_primes{ + return n_perrin_prime_r(13, [3, 0, 2], {}); +} + +MAIN:{ + print join(", ", sort {$a <=> $b} keys %{perrin_primes()}) . "\n"; +} \ No newline at end of file diff --git a/challenge-168/adam-russell/perl/ch-2.pl b/challenge-168/adam-russell/perl/ch-2.pl new file mode 100644 index 0000000000..1c3f034e65 --- /dev/null +++ b/challenge-168/adam-russell/perl/ch-2.pl @@ -0,0 +1,37 @@ +use strict; +use warnings; +## +# You are given an integer greater than 1. Write a script to find the home prime of the +# given number. +## +use bigint; +use Math::Primality qw/is_prime/; + +sub prime_factor{ + my $x = shift(@_); + my @factors; + for (my $y = 2; $y <= $x; $y++){ + next if $x % $y; + $x /= $y; + push @factors, $y; + redo; + } + return @factors; +} + +sub home_prime{ + my($n) = @_; + return $n if is_prime($n); + my $s = $n; + { + $s = join("", prime_factor($s)); + redo if !is_prime($s); + } + return $s; +} + +MAIN:{ + print home_prime(10) . "\n"; + print home_prime(16) . "\n"; + print home_prime(48) . "\n"; +} \ No newline at end of file diff --git a/challenge-168/adam-russell/prolog/ch-1.p b/challenge-168/adam-russell/prolog/ch-1.p new file mode 100644 index 0000000000..ad4dc6b771 --- /dev/null +++ b/challenge-168/adam-russell/prolog/ch-1.p @@ -0,0 +1,11 @@ +perrin_primes(A, B, C) --> {D is B + A, fd_not_prime(D)}, + perrin_primes(B, C, D). +perrin_primes(A, B, C) --> {D is B + A, fd_prime(D), D \== C}, + [D], perrin_primes(B, C, D). +perrin_primes(A, B, C) --> {D is B + A, fd_prime(D), D == C}, + [], perrin_primes(B, C, D). +perrin_primes(_, _, _) --> [], !. + +n_perrin_primes(N, PerrinPrimes):- + length(PerrinPrimes, N), + phrase(perrin_primes(3, 0, 2), PerrinPrimes). \ No newline at end of file diff --git a/challenge-168/adam-russell/prolog/ch-2.p b/challenge-168/adam-russell/prolog/ch-2.p new file mode 100644 index 0000000000..1dd62d9911 --- /dev/null +++ b/challenge-168/adam-russell/prolog/ch-2.p @@ -0,0 +1,41 @@ +prime_factors(N, L):- + N > 0, + prime_factors(N, L, 2). +prime_factors(1, [], _):- + !. +prime_factors(N, [F|L], F):- + R is N // F, + N =:= R * F, + !, + prime_factors(R, L, F). +prime_factors(N, L, F):- + next_factor(N, F, NF), + prime_factors(N, L, NF). +next_factor(_, 2, 3):- + !. +next_factor(N, F, NF):- + F * F < N, + !, + NF is F + 2. +next_factor(N, _, N). + +factor_concat(Factors, Atom):- + factor_concat(Factors, '', Atom). +factor_concat([], Atom, Atom). +factor_concat([H|T], AtomAccum, Atom):- + number_atom(H, A), + atom_concat(AtomAccum, A, UpdatedAtomAccum), + factor_concat(T, UpdatedAtomAccum, Atom). + +home_prime(N, HomePrime):- + prime_factors(N, Factors), + factor_concat(Factors, A), + number_atom(Number, A), + fd_not_prime(Number), + home_prime(Number, HomePrime). +home_prime(N, HomePrime):- + prime_factors(N, Factors), + factor_concat(Factors, A), + number_atom(Number, A), + fd_prime(Number), + HomePrime = Number. \ No newline at end of file -- cgit