recursive Pythagorian triples

[ccc31807]

Pythagorian triples are integers that form the sides of a right
triangle, e.g., 3, 4, 5. I've posted an iterative version below for
all triples less than 100. I'm having trouble coming up with a
recursive version. Any ideas?

CC

#! perl
use strict;
use warnings;
print "Pythagorian triples\n\n";

for(my $i = 1; $i < 101; $i++)
{
for(my $j = 1; $j < 101; $j++)
{
for(my $k = 1; $k < 101; $k++)
{
print "$i - $j - $k\n" if ($i * $i + $j * $j) == ($k * $k);
}
}
}
exit(0);

 

[George Mpouras]

Στις 15/3/2011 7:58 μμ, ο/η Glenn Jackman έγÏαψε:

Pythagorian triples are integers that form the sides of a right
triangle, e.g., 3, 4, 5. I've posted an iterative version below for
all triples less than 100. I'm having trouble coming up with a
recursive version. Any ideas?

CC

#! perl
use strict;
use warnings;
print "Pythagorian triples\n\n";

for(my $i = 1; $i< 101; $i++)
{
for(my $j = 1; $j< 101; $j++)
{
for(my $k = 1; $k< 101; $k++)
{
print "$i - $j - $k\n" if ($i * $i + $j * $j) == ($k * $k);
}
}
}
exit(0);

Not recursive, but the RosettaCode site
(http://rosettacode.org/wiki/List_comprehensions#Perl)
has this implementation

sub triples ($) {
my ($n) = @_;
map {
my $x = $_;
map {
my $y = $_;
map { [$x, $y, $_] }
grep { $x**2 + $y**2 == $_**2 } 1..$n
} 1..$n
} 1..$n;
}

this is the same as OP

 

[George Mpouras]

# This is pretty fast

my $iterator= &BuildIterator;

$iterator->(4);

sub BuildIterator {
return sub {
for (my $i=1; $i<=$_[0]; $i++) {
for (my $j=1; $j<$i; $j++) {
print STDOUT join(',', ($i**2 - $j**2) , 2*$i*$j , ($i**2 + $j**2))."\n" }}}
}

 

[Peter J. Holzer]

Pythagorian triples are integers that form the sides of a right
triangle, e.g., 3, 4, 5. I've posted an iterative version below for
all triples less than 100. I'm having trouble coming up with a
recursive version. Any ideas?

Not sure why you would want to do this, but here is a straightforward
solution:


#!/usr/bin/perl

use warnings;
use strict;

no warnings 'recursion';

test_c(100);

sub test_c {
my ($c) = @_;

if ($c > 1) {
test_c($c - 1);
}
test_b($c, $c);
}

sub test_b {
my ($b, $c) = @_;

if ($b > 1) {
test_b($b - 1, $c);
}

test_a($b, $b, $c);
}

sub test_a {
my ($a, $b, $c) = @_;

if ($a > 1) {
test_a($a - 1, $b, $c);
}

print "$a $b $c\n" if ($a * $a + $b * $b == $c * $c);
}
__END__

Note: If you don't care about the output order, this can easily be made
tail-recursive (doesn't help with perl, but usually does with functional
languages).

hp

 

[Peter J. Holzer]

# This is pretty fast

my $iterator= &BuildIterator;

$iterator->(4);

sub BuildIterator {
return sub {
for (my $i=1; $i<=$_[0]; $i++) {
for (my $j=1; $j<$i; $j++) {
print STDOUT join(',', ($i**2 - $j**2) , 2*$i*$j , ($i**2 + $j**2))."\n" }}}
}

But:

* No recursion.

* Doesn't print all pythogarean triples with a, b, c <= 100
(for example it doesn't print 6, 8, 10).

* It isn't obvious that the tupels it produces are indeed pythogarean
triples (yes, the proof is simple, but you need to do it).

* What's with the anonymous sub? That's completely unnecessary.

hp

 

[George Mpouras]

Στις 15/3/2011 9:22 μμ, ο/η Peter J. Holzer έγÏαψε:

* What's with the anonymous sub? That's completely unnecessary.

hp

Its beautiful !

 

[George Mpouras]

Στις 15/3/2011 9:22 μμ, ο/η Peter J. Holzer έγÏαψε:

# This is pretty fast

my $iterator=&BuildIterator;

$iterator->(4);

sub BuildIterator {
return sub {
for (my $i=1; $i<=$_[0]; $i++) {
for (my $j=1; $j<$i; $j++) {
print STDOUT join(',', ($i**2 - $j**2) , 2*$i*$j , ($i**2 + $j**2))."\n" }}}
}

But:

* No recursion.

* Doesn't print all pythogarean triples with a, b, c<= 100
(for example it doesn't print 6, 8, 10).

* It isn't obvious that the tupels it produces are indeed pythogarean
triples (yes, the proof is simple, but you need to do it).

* What's with the anonymous sub? That's completely unnecessary.

hp

Ah, the 6,8,10 is the second printed line !

 

[Peter Makholm]

Note: If you don't care about the output order, this can easily be made
tail-recursive (doesn't help with perl, but usually does with functional
languages).

You could implemt tail recursion using 'goto &func'. Not a very nice
syntax, but possible to emulate.

//Makholm

 

[ccc31807]

Not sure why you would want to do this,

Because of this, an Erlang program to find Pythagorian triples
recursively:

pythag(N) ->
[{A,B,C} ||
A <- seq(1,N),
B <- seq(1,N),
C <- seq(1,N),
A + B + C =< N,
(A * A) + (B * B) =:= C * C].

This says, given an integer N, for every permutation of A, B, and C
such that A+B+C is less than N, return A, B, C if the condition is
true.

I wondered if Perl could do the same in as few lines of code, taking
into account the function seq(N1,N2) which returns successive integers
from N1 to N2.

This isn't work related, as you might have guessed, but recreational.

CC.

 

[Peter J. Holzer]

Στις 15/3/2011 9:22 μμ, ο/η Peter J. Holzer έγÏαψε:

# This is pretty fast

my $iterator=&BuildIterator;

$iterator->(4);

sub BuildIterator {
return sub {
for (my $i=1; $i<=$_[0]; $i++) {
for (my $j=1; $j<$i; $j++) {
print STDOUT join(',', ($i**2 - $j**2) , 2*$i*$j , ($i**2 + $j**2))."\n" }}}
}

But:

* No recursion.

* Doesn't print all pythogarean triples with a, b, c<= 100
(for example it doesn't print 6, 8, 10).

* It isn't obvious that the tupels it produces are indeed pythogarean
triples (yes, the proof is simple, but you need to do it).

* What's with the anonymous sub? That's completely unnecessary.

Ah, the 6,8,10 is the second printed line !

Actually, 8,6,10 is the second printed line. I sorted the output to
check which triplets were missing, that's why the wrong order threw me
off.

It still doesn't print all the pythogarean triples with a, b, c <= 100.

So that brings us to a new problem:

For any value N, is there a value $x so that $iterator->($x) will
produce all pythogarean triples with a, b, c <= N?

There may be a simple proof for that but I admit that at the moment I
don't even have an idea how to start. So for me it is not a replacement
for Carter's program as I don't know which value to call $iterator with
to get all triples <= 100 (never mind that it will also print values >
100 before that).

hp

 

[Peter J. Holzer]

Στις 15/3/2011 9:22 μμ, ο/η Peter J. Holzer έγÏαψε:

Its beautiful !

It's ugly. It has extra code which serves no purpose.

hp

 

[sreservoir]

Στις 15/3/2011 7:58 μμ, ο/η Glenn Jackman έγÏαψε:

Pythagorian triples are integers that form the sides of a right
triangle, e.g., 3, 4, 5. I've posted an iterative version below for
all triples less than 100. I'm having trouble coming up with a
recursive version. Any ideas?

CC

#! perl
use strict;
use warnings;
print "Pythagorian triples\n\n";

for(my $i = 1; $i< 101; $i++)
{
for(my $j = 1; $j< 101; $j++)
{
for(my $k = 1; $k< 101; $k++)
{
print "$i - $j - $k\n" if ($i * $i + $j * $j) == ($k * $k);
}
}
}
exit(0);

Not recursive, but the RosettaCode site
(http://rosettacode.org/wiki/List_comprehensions#Perl)
has this implementation

sub triples ($) {
my ($n) = @_;
map {
my $x = $_;
map {
my $y = $_;
map { [$x, $y, $_] }
grep { $x**2 + $y**2 == $_**2 } 1..$n
} 1..$n
} 1..$n;
}

this is the same as OP

in the same way that 2+2 is the same as 2*2.

 

[sreservoir]

Not sure why you would want to do this,

Because of this, an Erlang program to find Pythagorian triples
recursively:

pythag(N) ->
[{A,B,C} ||
A<- seq(1,N),
B<- seq(1,N),
C<- seq(1,N),
A + B + C =< N,
(A * A) + (B * B) =:= C * C].

that's not recursive. that's a list comprehension.

 

[Ed]

Στις 15/3/2011 9:22 μμ, ο/η Peter J. Holzer έγÏαψε:

# This is pretty fast
my $iterator=&BuildIterator;
$iterator->(4);
sub BuildIterator {
return sub {
for (my $i=1; $i<=$_[0]; $i++) {
for (my $j=1; $j<$i; $j++)     {
print STDOUT join(',', ($i**2 - $j**2) , 2*$i*$j , ($i**2 + $j**2))."\n" }}}
}
But:
  * No recursion.
  * Doesn't print all pythogarean triples with a, b, c<= 100
    (for example it doesn't print 6, 8, 10).
  * It isn't obvious that the tupels it produces are indeed pythogarean
    triples (yes, the proof is simple, but you need to do it).
  * What's with the anonymous sub? That's completely unnecessary.

Ah, the 6,8,10 is the second printed line !

Actually, 8,6,10 is the second printed line. I sorted the output to
check which triplets were missing, that's why the wrong order threw me
off.

It still doesn't print all the pythogarean triples with a, b, c <= 100.

So that brings us to a new problem:

For any value N, is there a value $x so that $iterator->($x) will
produce all pythogarean triples with a, b, c <= N?

There may be a simple proof for that but I admit that at the moment I
don't even have an idea how to start. So for me it is not a replacement
for Carter's program as I don't know which value to call $iterator with
to get all triples <= 100 (never mind that it will also print values >
100 before that).

        hp

The code would need to iterate with a multiplier. See the brief
discussion here:

http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple

Note that 6, 8, 10 would come from a doubling of m = 2, n = 1 (a = 3,
b = 4, c = 5). The code as written won't provide that triplet (in
that specific order). 8, 6, 10 comes directly from m = 3, n = 1.

Ed

 

[George Mpouras]

Στις 15/3/2011 9:22 μμ, ο/η Peter J. Holzer έγÏαψε:

# This is pretty fast

my $iterator=&BuildIterator;

$iterator->(4);

sub BuildIterator {
return sub {
for (my $i=1; $i<=$_[0]; $i++) {
for (my $j=1; $j<$i; $j++) {
print STDOUT join(',', ($i**2 - $j**2) , 2*$i*$j , ($i**2 + $j**2))."\n" }}}
}

But:

* No recursion.

* Doesn't print all pythogarean triples with a, b, c<= 100
(for example it doesn't print 6, 8, 10).

* It isn't obvious that the tupels it produces are indeed pythogarean
triples (yes, the proof is simple, but you need to do it).

* What's with the anonymous sub? That's completely unnecessary.

Ah, the 6,8,10 is the second printed line !

Actually, 8,6,10 is the second printed line. I sorted the output to
check which triplets were missing, that's why the wrong order threw me
off.

It still doesn't print all the pythogarean triples with a, b, c<= 100.

So that brings us to a new problem:

For any value N, is there a value $x so that $iterator->($x) will
produce all pythogarean triples with a, b, c<= N?

There may be a simple proof for that but I admit that at the moment I
don't even have an idea how to start. So for me it is not a replacement
for Carter's program as I don't know which value to call $iterator with
to get all triples<= 100 (never mind that it will also print values>
100 before that).

hp

Did you find any missing triplet ?

 

[Willem]

ccc31807 wrote:
)> Not sure why you would want to do this,
)
) Because of this, an Erlang program to find Pythagorian triples
) recursively:
)
) pythag(N) ->
) [{A,B,C} ||
) A <- seq(1,N),
) B <- seq(1,N),
) C <- seq(1,N),
) A + B + C =< N,
) (A * A) + (B * B) =:= C * C].
)
) This says, given an integer N, for every permutation of A, B, and C
) such that A+B+C is less than N, return A, B, C if the condition is
) true.

And how is that recursion ?

) I wondered if Perl could do the same in as few lines of code, taking
) into account the function seq(N1,N2) which returns successive integers
) from N1 to N2.

for my $A (1..$N) {
for my $B (1..$N) {
for my $C (1..$N) {
print "$A,$B,$C\n" if $A+$B+$C<$N and ($A*$A)+($B*$B)==($C*$C);
}
}
}

Is the same in as few lines of code. 100% straightforward.

Iterating over the C variable is extremely silly, by the way.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Willem]

ccc31807 wrote:
) Pythagorian triples are integers that form the sides of a right
) triangle, e.g., 3, 4, 5. I've posted an iterative version below for
) all triples less than 100. I'm having trouble coming up with a
) recursive version. Any ideas?

Why would you want a recursive version anyway ?
Here's a balanced line version that only uses addition:

sub pythag {
my ($a, $b, $c, $a2b2, $c2) = @_;
while ($a < $b) {
while ($c2 < $a2b2) {
$c2 += $c + $c + 1;
$c++;
}
last if $c > 100;
print "$a - $b - $c\n" if ($c2 == $a2b2);
$a2b2 += $a + $a + 1;
$a++;
}
}

my $a2b2 = 2;
for my $b (1 .. 100) {
pythag (1, $b, 1, $a2b2, 1);
$a2b2 += $b + $b + 1;
}


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Justin C]

#! perl
use strict;
use warnings;
print "Pythagorian triples\n\n";

for(my $i = 1; $i < 101; $i++)
{
for(my $j = 1; $j < 101; $j++)
{
for(my $k = 1; $k < 101; $k++)
{
print "$i - $j - $k\n" if ($i * $i + $j * $j) == ($k * $k);
}
}
}

This isn't my strong point, but why would you do `$i = $j = $k = 1` when
they can never be the same. In addition, if you want $k < 101, then $i
cannot be > 99 and $j cannot be > 100, they're not pythagorean trips as
I understand them if any numbers are duplicated in a set.

Does the above not iterate over all matches even if done:

for (my $i = 3; $i < 99; $i++) {
for (my $j = $i + 1; $j < 100; $j++) {
for (my $k = $j + 1; $k < 101; $k++) {
print "$i - $j - $k\n" if ($i**2 + $j**2) == $k**2;
}
}
}

I think this avoids duplicates too.

What I don't understand is recursion in this context.

Justin.

 

[ccc31807]

pythag(N) ->
     [{A,B,C} ||
         A<- seq(1,N),
         B<- seq(1,N),
         C<- seq(1,N),
         A + B + C =<  N,
         (A * A) + (B * B) =:= C * C].

that's not recursive. that's a list comprehension.

Yes, it's a list comprehension. My question was, can you write a
Pythagorean triple function in Perl using recursion?

NOT my intent to start a language war, but simply a question that (for
some reason) I found interesting and perplexing, and thought I would
post it to c.l.p.m.

I understand recursion as solving a problem by calling either directly
or indirectly the original function with a smaller set of the original
data until it returns on some base case. Obviously, you can't have a
diminishing data set starting at 0 and increasing up a larger number,
but you CAN recurse starting at 0 until you get to a base case. Here
is a recursive implementation of a function seq() as might have been
used in the Erlang program.

#! perl
use strict;
use warnings;

my $n = $ARGV[0];
print "N is $n\n";
my @seq = ();

sub seq
{
my $n1 = shift;
if ($n == $n1) {return @seq;}
else { push @seq, $n1; seq(++$n1); }
}

seq(0);
print "@seq\n";;
exit(0);

 

[ccc31807]

What I don't understand is recursion in this context.

Neither do I, which was the point of the post!

CC.