use strict; use warnings; use Math::Prime::Util ':all'; no warnings 'recursion'; my $start = time; my $ReturnCode = 0; my $smallest_prime = 7; my $max_number = 2000;#500000;#0; my @prime_factors; my %results = (); my @gamma_values; # Find the set of prime numbers less than $max_number when multiplied by 7 my $primes = primes( $smallest_prime, $max_number ); # Find the subset of primes where : prime mod 8 = +/-1 print "\nSet of primes in the range : $smallest_prime to $max_number\n"; foreach my $prime (@$primes) { print "$prime "; my $mod_8 = $prime % 8; print "($mod_8)\n"; if ($mod_8 == 1 || $mod_8 == 7 ) { push @prime_factors, $prime } } print "\nSet of primes matching: prime mod 8 = 1 or 7\n"; foreach my $prime (@prime_factors) { print "$prime\n"; } # Calculate the combinations of prime numbers which give a result <= $max_number my @initial_contributing_primes = (1); my $initial_product = 1; my $initial_prime_index = 0; print "\nProducts of the prime numbers which give a result <= $max_number\n"; find_valid_products(\@initial_contributing_primes, $initial_product, $initial_prime_index); print "\nSet of calculated gamma values (sum of two short sides of a Pythagorian triple):\n"; print "a+b, (a, b, c)\n"; triple(3, 4, 5, $max_number); print "\nGamma values in ascending order:\n"; my @sorted_gamma_values = sort { $a <=> $b } @gamma_values; foreach my $gamma (@sorted_gamma_values) { print "$gamma\n"; } my %gamma_hash = (); my $fail1 = 0; my $fail2 = 0; # Compare the two sets of data and display differences print "\nChecking whether all triangle gamma values are present in primes set:\n"; foreach my $gamma (@sorted_gamma_values) { if (exists($results{$gamma})) { $gamma_hash{$gamma} = "Y"; print "Found: $gamma\n"; } else { $gamma_hash{$gamma} = "N"; print "Didn't find: $gamma\n"; $fail1 = 1; } } print "\nChecking whether all prime values are present in triangle gamma set:\n"; foreach (sort { $a <=> $b } keys(%results) ) { if (exists($gamma_hash{$_})) { print "Found: $_\n"; } else { print "Didn't find: $_\n"; $fail2 = 1; } } if ($fail1 == 0) { print "All triangle values found in primes set.\n"; } else { print "Didn't find all triangle values in primes set.\n"; } if ($fail2 == 0) { print "All prime values found in triangles set.\n"; } else { print "Didn't find all prime values in triangles set.\n"; } my $stop = time; my $elapsed = $stop - $start; print "\n\n=============================================================\n\n"; print "Total runtime: $elapsed seconds\n"; print "\n=============================================================\n"; exit $ReturnCode; # From: http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple sub triple { my ($a, $b, $c, $max) = @_; my $G = $a + $b; if ($G < $max) { print "$G, ($a, $b, $c)\n"; push @gamma_values, $G; my $a1 = $a - 2 * $b + 2 * $c; my $b1 = 2 * $a - $b + 2 * $c; my $c1 = 2 * $a - 2 * $b + 3 * $c; triple($a1, $b1, $c1, $max); my $a2 = $a + 2 * $b + 2 * $c; my $b2 = 2 * $a + $b + 2 * $c; my $c2 = 2 * $a + 2 * $b + 3 * $c; triple($a2, $b2, $c2, $max); my $a3 = -$a + 2 * $b + 2 * $c; my $b3 = -2 * $a + $b + 2 * $c; my $c3 = -2 * $a + 2 * $b + 3 * $c; triple($a3, $b3, $c3, $max); } } sub find_valid_products { my ($primes_ref, $product, $prime_index) = @_; return if ($prime_index >= scalar(@prime_factors)); my @contributing_primes = @$primes_ref; my $prime = $prime_factors[$prime_index]; find_valid_products(\@contributing_primes, $product, $prime_index + 1); $product *= $prime; if ($product <= $max_number) { push @contributing_primes, $prime; print "Product: $product Contributed: @contributing_primes\n"; $results{$product} = "@contributing_primes"; find_valid_products(\@contributing_primes, $product, $prime_index); } }