Advent Calendar - December 13, 2021

Monday, Dec 13, 2021| Tags: Perl

Advent Calendar 2021

| Day 12 | Day 13 | Day 14 |


The gift is presented by W. Luis Mochan. Today he is talking about his solution to “The Weekly Challenge - 125”. This is re-produced for Advent Calendar 2021 from the original post by W. Luis Mochan.



Task #1: Pythagorean Triples


You are given a positive integer $N.

Write a script to print all Pythagorean Triples containing $N as a member. Print -1 if it can’t be a member of any.




Consider a complex number a+ib with integer real and imaginary parts a and b. Its square (a + i b)2=x+iy has real and imaginary parts x=a2-b2 and y=2ab. Notice that its squared modulus is |x+iy|2=x2+y2=(a2-b2)2+4a2b2=(a2+b2)2, so that (x, y, z) with z=|a+ib|2=a2+b2 form a Pythagorean Triplet, x2+y2=z2. It turns out that all Pythagorean triplets are integer multiples of triplets of this form. Thus, given N we can check if it is a multiple of some a2-b2, 2ab or a2+b2 for any pair of integers a,b and some multiplier k. If we succeed, a Pythagorean triplet would be k(a2-b2), k(2ab) and k(a2+b2). If we only consider positive numbers, then we can assume b<a. As a2-b2=(a-b)(a+b) is a positive multiple of a+b, a may not be larger than N, bounding our search. Thus, we can test all pairs such that 0<a<N and 0<b<a to get all the Pythagorean triplets that contain N, if there is any.


#!/usr/bin/env perl
# Perl weekly challenge 125
# Task 1:  Pythagorean triplets
#
# See https://wlmb.github.io/2021/08/10/PWC125/#task-1-pythagorean-triples
use warnings;
use strict;
use v5.12;
use POSIX qw(floor);
use List::Util qw(uniq);

die "Usage: ./ch-1.pl N1 N2... to search for pythagorean triplets containing Ni"
    unless @ARGV;

foreach(@ARGV){
    my $N=floor($_); # check non-negative integer arguments
    warn("Expected natural"), next unless $N>=0 and $N==$_;
    my @found=();
    foreach my $a(1..$N-1){
    foreach my $b (1..$a-1){
        push @found, [$a, $b, $_/($a**2-$b**2)] if $_%($a**2-$b**2)==0;
        push @found, [$a, $b, $_/(2*$a*$b)] if $_%(2*$a*$b)==0;
        push @found, [$a, $b, $_/($a**2+$b**2)] if $_%($a**2+$b**2)==0;
    }
    }
    say "Input; $_\nOutput:";
    say "\t$_" foreach uniq map { #remove duplicates
    my($A,$B,$K)=@$_; # careful not to confuse with $a and $b from sort
    my ($x, $y, $z)=sort {$a <=> $b} map {$K*$_} ($A**2-$B**2, 2*$A*$B, $A**2+$B**2);
    "\t($x, $y, $z)";
    } @found;
    say("\t-1, no result found") unless @found;
}

Output


$ perl ch-1.pl 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Input; 1
Output:
        -1, no result found
Input; 2
Output:
        -1, no result found
Input; 3
Output:
                (3, 4, 5)
Input; 4
Output:
                (3, 4, 5)
Input; 5
Output:
                (3, 4, 5)
                (5, 12, 13)
Input; 6
Output:
                (6, 8, 10)
Input; 7
Output:
                (7, 24, 25)

Input; 8
Output:
                (6, 8, 10)
                (8, 15, 17)
Input; 9
Output:
                (9, 12, 15)
                (9, 40, 41)
Input; 10
Output:
                (6, 8, 10)
                (10, 24, 26)
Input; 11
Output:
                (11, 60, 61)
Input; 12
Output:
                (12, 16, 20)
                (9, 12, 15)
                (5, 12, 13)
                (12, 35, 37)
Input; 13
Output:
                (5, 12, 13)
                (13, 84, 85)

Input; 14
Output:
                (14, 48, 50)
Input; 15
Output:
                (15, 20, 25)
                (9, 12, 15)
                (15, 36, 39)
                (8, 15, 17)
                (15, 112, 113)

To my surprise, it seems that most numbers are part of a Pythagorean triplet, if not all numbers beyond 2. I tested up to 1000 and found no non-Phytagorean number N>2. Then I found a reason for that (thanks to Elías Mochán): Any even number N>2 is clearly of the form 2ab (take a=N/2, b=1). Any odd number is of the form a2-b2 (take a=(N+1)/2 and b=(N-1)/2). Thus, either ((N/2)2-1, N, (N/2)2+1/ or (N, (N2-1)/2,(N2+1)/2) form a Pythagorean triplet that contains N for any N>2.



If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.

Advent Calendar 2021

SO WHAT DO YOU THINK ?

If you have any suggestions or ideas then please do share with us.

Contact with me