| 04 October 2026 | Challenge 393 |
Pythagorean Primes
Task 1: Pythagoras Multiplied
Submitted by: Ulrich Rieke
You are given a positive integer n.
Find the number of all positive integer triplets (a, b, c) so that a^2 + b^2 = c^2 and a, b and c are integers <= n.
Example 1
Input: $n = 20
Output: 12
(3,4,5), (4,3,5), (5,12,13),(6,8,10),
(8,6,10), (8,15,17), (9,12,15),(12,5,13),
(12,9,15),(12,16,20),(15,8,17),(16,12,20)
Example 2
Input: $n = 7
Output: 2
(3,4,5),(4,3,5)
Example 3
Input: $n = 1
Output: 0
Example 4
Input: $n = 15
Output: 8
Example 5
Input: $n = 30
Output: 22
Solution
There are a number of formulas that can be used to generate Pythagorean triples. Choosing Dickson’s method for this task.
In short, for an even \(r\) and all \(s\), \(t\) such that \(r^2 = 2\,s\,t\), the triple \((a, b, c) = (r + s, r + t, r + s + t)\) is a Pythagorean triple and all Pythagorean triples can be generated this way.
Let \(\frac{r^2}{2} = q = s\,t\).
From
\[2 \sqrt{q} \le s + t\]it follows that
\[r(1 + \sqrt{2}) \le c\]This provides an upper limit for \(r\) depending on \(n\):
If \(r > \frac{n}{1 + \sqrt{2}}\), then \(c > n\) in all generated triples, i.e. these triples would be invalid.
Only triples generated from \(s^2 < q\) need to be considered, but they have to be counted twice. As \(c\) decreases with increasing \(s\), we know that all larger \(s < \sqrt{q}\) produce valid triples when we found the first \(s\) that generates a valid triple. We just need to count the number of valid values for \(s\) and add it to a counter.
This leads to the following implementations:
Perl
use strict;
use warnings;
use experimental 'signatures'
use Math::Prime::Util 'divisors';
sub pythagoras_multiplied ($n) {
my $count = 0;
for (my $r = 2; $r < $n / (1 + sqrt(2)); $r += 2) {
my $q = $r**2 / 2;
my @divisors = divisors($q);
while (my ($i, $s) = each @divisors) {
if ($r + $s + $q / $s <= $n) {
$count += @divisors - 2 * $i;
last;
}
}
}
$count;
}
See the full solution to task 1.
J
It is possible to use J in a procedural fashion, too. Here is a one-to-one port of the Perl solution.
pythagoras_multiplied =: verb define
NB. Taken from Wiki: https://code.jsoftware.com/wiki/Essays/Divisors
divisors =. /:~ @: , @: > @: (*/&.>/) @: ((^ i.@>:)&.>/) @: (__&q:)
count =. 0
for_r. +: >: i. <. -: y % >: %: 2 do.
q =. -: *: r
div =. divisors q
for_s. div do.
if. y >: r + s + q % s do.
count =. count + (# div) - +: s_index
break.
end.
end.
end.
count
)
pythagoras_multiplied 30
22
I don’t have the faintest idea if this approach is efficient or not.
It takes some seconds for n = 1000000:
$ time perl/ch-1.pl 1000000; time j/ch-1.ijs 1000000
3961284
real 0m2.413s
user 0m2.392s
sys 0m0.021s
3961284
real 0m2.861s
user 0m2.805s
sys 0m0.054s
See the full solution.
Task 2: Prime Step
Submitted by: Ulrich Rieke
You are given a string with English alphabetic characters only.
What is the absolute difference of the sum of the ASCII values of the characters in the string to the nearest prime number?
Example 1
Input: $str = "hello"
Output: 9
The ordinal values of "hello" are [104,101,108,108,111], summing up to 532.
The nearest prime number to 532 is 523, resulting in an absolute difference of 9.
Example 2
Input: $str = "football"
Output: 2
Starting with the values [102,111,111,116,98,97,108,108] and the sum 841.
We find 839 as the nearest prime number, so the difference is 2.
Example 3
Input: $str = "a"
Output: 0
Example 4
Input: $str = "challenge"
Output: 2
The ordinal values of "challenge" are [99, 104, 97, 108, 108, 101, 110, 103, 101], which sum up to 931.
The nearest prime number to 931 is 929, so the difference is 2.
Example 5
Input: $str = "perl"
Output: 2
The ordinal values of "perl" are [112, 101, 114, 108], summing up to 435.
Nearest prime is 433, so the difference is 2.
Solution
Basically, the solution is straightforward. In languages where neither “previous_prime” nor “next_prime” return their argument when called with a prime, the case of a prime character sum needs to be considered separately. Both Perl and J fall into this category.
Perl
use strict;
use warnings;
use Math::Prime::Util qw(vecsum vecmin is_prime next_prime prev_prime);
sub prime_step {
my $csum = vecsum map ord, split //, shift;
is_prime($csum) ?
0 :
vecmin $csum - prev_prime($csum), next_prime($csum) - $csum;
}
See the full solution to task 2.
J
Applying abs to the differences.
prime_step =: _(adverb define)
char_sum =. +/ @: (a.&i.)
is_prime =. 1&p:
prev_prime =. _4&p:
next_prime =. 4&p:
abs_min =. <./ @: |
(([: abs_min ] - prev_prime , next_prime)`0:@.is_prime @ char_sum) f. : [:
)
prime_step 'hello'
9
See the full solution.