Pythagoras multiplied

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.

Examples

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

Analysis

There are lots of ways to do this, but I have chosen a boring, but hopefully fast one.

Let's confine the search initially to $a < $b, because for every $a, $b, $c answer, $b, $a, $c is clearly also an answer. Also, for integer $c, $a cannot equal $b.

We are going to be interested in knowing whether $a ** 2 + $b ** 2 is a perfect square, so I set up a hash such that $square{$j} is defined if $j is a square.

That enables me to code the challenge without using sqrt() or int(), both of which are likely to be quite costly on the microsecond scale. On the other hand a hash lookup is a lot slower than an array lookup, so perhaps a sparse array @squares would have been even faster.

But my solution finds the 730 triplets for $n == 1000 in next to no time, so I deem it to be good enough.

Try it 

Your input:

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-09-28
use utf8;     # Week 393 - task 1 - Pythagoras multiplied
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

pythagoras_multiplied(20);
pythagoras_multiplied(1);
pythagoras_multiplied(50);
pythagoras_multiplied(1000);

sub pythagoras_multiplied {
    
    my ($n, $n2, $max_a, $count, $b2, $explain, $c, $a2, %square);
    
    # initialise
    $n = $_[0];
    $count = 0;
    $explain = '';
    $n2 = $n ** 2;
    $max_a = int($n2 / 2);
    
    # make list of squares
    $square{$_ ** 2} = 1 for 3 .. $n;
    
    # loop over possible $a ($a < $b)
    A: for $a (3 .. $max_a) {
        $a2 = $a ** 2;
        
        # loop over possible $b
        B: for $b ($a + 1 .. $n - 3) {
            $b2 = $b ** 2;
            
            # $b is too big for this $a
            next A if $a2 + $b2 > $n2;
            
            # $c isn't a square
            next B unless $square{$a2 + $b2};
            
            # we have 2 solutions
            $count += 2;
            $c = sqrt($a ** 2 + $b ** 2);
            $explain .= qq[($a, $b, $c), ($b, $a, $c), ];
            next A;
        }
            
    }
    say qq[\nInput:  $n];
    say qq[Output: $count];
    say substr($explain, 0, -2) if $count;
}

21 lines of code
Completed after the closing date and not submitted to GitHub

Output from script

Input:  20
Output: 12
(3, 4, 5), (4, 3, 5), (5, 12, 13), (12, 5, 13), (6, 8, 10), (8, 6,
   10), (8, 15, 17), (15, 8, 17), (9, 12, 15), (12, 9, 15), (12, 16,
   20), (16, 12, 20)

Input:  1
Output: 0

Input:  50
Output: 32
(3, 4, 5), (4, 3, 5), (5, 12, 13), (12, 5, 13), (6, 8, 10), (8, 6,
   10), (7, 24, 25), (24, 7, 25), (8, 15, 17), (15, 8, 17), (9, 12,
   15), (12, 9, 15), (10, 24, 26), (24, 10, 26), (12, 16, 20), (16,
   12, 20), (15, 20, 25), (20, 15, 25), (16, 30, 34), (30, 16, 34),
   (18, 24, 30), (24, 18, 30), (20, 21, 29), (21, 20, 29), (21, 28,
   35), (28, 21, 35), (24, 32, 40), (32, 24, 40), (27, 36, 45), (36,
   27, 45), (30, 40, 50), (40, 30, 50)

Input:  1000
Output: 730
(3, 4, 5), (4, 3, 5), (5, 12, 13), (12, 5, 13), (6, 8, 10), (8, 6,
   10), (7, 24, 25), (24, 7, 25), (8, 15, 17), (15, 8, 17), (9, 12,
   15), (12, 9, 15), (10, 24, 26), (24, 10, 26), (11, 60, 61), (60,
   11, 61), (12, 16, 20), (16, 12, 20), (13, 84, 85), (84, 13, 85),
   (14, 48, 50), (48, 14, 50), (15, 20, 25), (20, 15, 25), (16, 30,
   34), (30, 16, 34), (17, 144, 145), (144, 17, 145), (18, 24, 30),
   (24, 18, 30), (19, 180, 181), (180, 19, 181), (20, 21, 29), (21,
   20, 29), (21, 28, 35), (28, 21, 35), (22, 120, 122), (120, 22,
   122), (23, 264, 265), (264, 23, 265), (24, 32, 40), (32, 24, 40),
   (25, 60, 65), (60, 25, 65), (26, 168, 170), (168, 26, 170), (27,
   36, 45), (36, 27, 45), (28, 45, 53), (45, 28, 53), (29, 420, 421),
   (420, 29, 421), (30, 40, 50), (40, 30, 50), (31, 480, 481), (480,
   31, 481), (32, 60, 68), (60, 32, 68), (33, 44, 55), (44, 33, 55),
   (34, 288, 290), (288, 34, 290), (35, 84, 91), (84, 35, 91), (36,
   48, 60), (48, 36, 60), (37, 684, 685), (684, 37, 685), (38, 360,
   362), (360, 38, 362), (39, 52, 65), (52, 39, 65), (40, 42, 58),
   (42, 40, 58), (41, 840, 841), (840, 41, 841), (42, 56, 70), (56,
   42, 70), (43, 924, 925), (924, 43, 925), (44, 117, 125), (117, 44,
   125), (45, 60, 75), (60, 45, 75), (46, 528, 530), (528, 46, 530),
   (48, 55, 73), (55, 48, 73), (49, 168, 175), (168, 49, 175), (50,
   120, 130), (120, 50, 130), (51, 68, 85), (68, 51, 85), (52, 165,
   173), (165, 52, 173), (54, 72, 90), (72, 54, 90), (55, 132, 143),
   (132, 55, 143), (56, 90, 106), (90, 56, 106), (57, 76, 95), (76,
   57, 95), (58, 840, 842), (840, 58, 842), (60, 63, 87), (63, 60,
   87), (62, 960, 962), (960, 62, 962), (63, 84, 105), (84, 63, 105),
   (64, 120, 136), (120, 64, 136), (65, 72, 97), (72, 65, 97), (66,
   88, 110), (88, 66, 110), (68, 285, 293), (285, 68, 293), (69, 92,
   115), (92, 69, 115), (70, 168, 182), (168, 70, 182), (72, 96, 120),
   (96, 72, 120), (75, 100, 125), (100, 75, 125), (76, 357, 365),
   (357, 76, 365), (77, 264, 275), (264, 77, 275), (78, 104, 130),
   (104, 78, 130), (80, 84, 116), (84, 80, 116), (81, 108, 135), (108,
   81, 135), (84, 112, 140), (112, 84, 140), (85, 132, 157), (132, 85,
   157), (87, 116, 145), (116, 87, 145), (88, 105, 137), (105, 88,
   137), (90, 120, 150), (120, 90, 150), (91, 312, 325), (312, 91,
   325), (92, 525, 533), (525, 92, 533), (93, 124, 155), (124, 93,
   155), (95, 168, 193), (168, 95, 193), (96, 110, 146), (110, 96,
   146), (98, 336, 350), (336, 98, 350), (99, 132, 165), (132, 99,
   165), (100, 105, 145), (105, 100, 145), (102, 136, 170), (136, 102,
   170), (104, 153, 185), (153, 104, 185), (105, 140, 175), (140, 105,
   175), (108, 144, 180), (144, 108, 180), (110, 264, 286), (264, 110,
   286), (111, 148, 185), (148, 111, 185), (112, 180, 212), (180, 112,
   212), (114, 152, 190), (152, 114, 190), (115, 252, 277), (252, 115,
   277), (116, 837, 845), (837, 116, 845), (117, 156, 195), (156, 117,
   195), (119, 120, 169), (120, 119, 169), (120, 126, 174), (126, 120,
   174), (121, 660, 671), (660, 121, 671), (123, 164, 205), (164, 123,
   205), (124, 957, 965), (957, 124, 965), (125, 300, 325), (300, 125,
   325), (126, 168, 210), (168, 126, 210), (128, 240, 272), (240, 128,
   272), (129, 172, 215), (172, 129, 215), (130, 144, 194), (144, 130,
   194), (132, 176, 220), (176, 132, 220), (133, 156, 205), (156, 133,
   205), (135, 180, 225), (180, 135, 225), (136, 255, 289), (255, 136,
   289), (138, 184, 230), (184, 138, 230), (140, 147, 203), (147, 140,
   203), (141, 188, 235), (188, 141, 235), (143, 780, 793), (780, 143,
   793), (144, 165, 219), (165, 144, 219), (145, 348, 377), (348, 145,
   377), (147, 196, 245), (196, 147, 245), (150, 200, 250), (200, 150,
   250), (152, 285, 323), (285, 152, 323), (153, 204, 255), (204, 153,
   255), (154, 528, 550), (528, 154, 550), (155, 372, 403), (372, 155,
   403), (156, 208, 260), (208, 156, 260), (159, 212, 265), (212, 159,
   265), (160, 168, 232), (168, 160, 232), (161, 240, 289), (240, 161,
   289), (162, 216, 270), (216, 162, 270), (165, 220, 275), (220, 165,
   275), (168, 224, 280), (224, 168, 280), (170, 264, 314), (264, 170,
   314), (171, 228, 285), (228, 171, 285), (174, 232, 290), (232, 174,
   290), (175, 288, 337), (288, 175, 337), (176, 210, 274), (210, 176,
   274), (177, 236, 295), (236, 177, 295), (180, 189, 261), (189, 180,
   261), (182, 624, 650), (624, 182, 650), (183, 244, 305), (244, 183,
   305), (184, 345, 391), (345, 184, 391), (185, 444, 481), (444, 185,
   481), (186, 248, 310), (248, 186, 310), (189, 252, 315), (252, 189,
   315), (190, 336, 386), (336, 190, 386), (192, 220, 292), (220, 192,
   292), (195, 216, 291), (216, 195, 291), (196, 315, 371), (315, 196,
   371), (198, 264, 330), (264, 198, 330), (200, 210, 290), (210, 200,
   290), (201, 268, 335), (268, 201, 335), (203, 396, 445), (396, 203,
   445), (204, 253, 325), (253, 204, 325), (205, 492, 533), (492, 205,
   533), (207, 224, 305), (224, 207, 305), (208, 306, 370), (306, 208,
   370), (210, 280, 350), (280, 210, 350), (213, 284, 355), (284, 213,
   355), (215, 516, 559), (516, 215, 559), (216, 288, 360), (288, 216,
   360), (217, 456, 505), (456, 217, 505), (219, 292, 365), (292, 219,
   365), (220, 231, 319), (231, 220, 319), (222, 296, 370), (296, 222,
   370), (224, 360, 424), (360, 224, 424), (225, 272, 353), (272, 225,
   353), (228, 304, 380), (304, 228, 380), (230, 504, 554), (504, 230,
   554), (231, 308, 385), (308, 231, 385), (232, 435, 493), (435, 232,
   493), (234, 312, 390), (312, 234, 390), (235, 564, 611), (564, 235,
   611), (237, 316, 395), (316, 237, 395), (238, 240, 338), (240, 238,
   338), (240, 252, 348), (252, 240, 348), (243, 324, 405), (324, 243,
   405), (245, 588, 637), (588, 245, 637), (246, 328, 410), (328, 246,
   410), (248, 465, 527), (465, 248, 527), (249, 332, 415), (332, 249,
   415), (250, 600, 650), (600, 250, 650), (252, 275, 373), (275, 252,
   373), (255, 340, 425), (340, 255, 425), (256, 480, 544), (480, 256,
   544), (258, 344, 430), (344, 258, 430), (259, 660, 709), (660, 259,
   709), (260, 273, 377), (273, 260, 377), (261, 348, 435), (348, 261,
   435), (264, 315, 411), (315, 264, 411), (265, 636, 689), (636, 265,
   689), (266, 312, 410), (312, 266, 410), (267, 356, 445), (356, 267,
   445), (270, 360, 450), (360, 270, 450), (272, 510, 578), (510, 272,
   578), (273, 364, 455), (364, 273, 455), (275, 660, 715), (660, 275,
   715), (276, 368, 460), (368, 276, 460), (279, 372, 465), (372, 279,
   465), (280, 294, 406), (294, 280, 406), (282, 376, 470), (376, 282,
   470), (285, 380, 475), (380, 285, 475), (287, 816, 865), (816, 287,
   865), (288, 330, 438), (330, 288, 438), (290, 696, 754), (696, 290,
   754), (291, 388, 485), (388, 291, 485), (294, 392, 490), (392, 294,
   490), (295, 708, 767), (708, 295, 767), (296, 555, 629), (555, 296,
   629), (297, 304, 425), (304, 297, 425), (300, 315, 435), (315, 300,
   435), (301, 900, 949), (900, 301, 949), (303, 404, 505), (404, 303,
   505), (304, 570, 646), (570, 304, 646), (305, 732, 793), (732, 305,
   793), (306, 408, 510), (408, 306, 510), (308, 435, 533), (435, 308,
   533), (309, 412, 515), (412, 309, 515), (310, 744, 806), (744, 310,
   806), (312, 416, 520), (416, 312, 520), (315, 420, 525), (420, 315,
   525), (318, 424, 530), (424, 318, 530), (319, 360, 481), (360, 319,
   481), (320, 336, 464), (336, 320, 464), (321, 428, 535), (428, 321,
   535), (322, 480, 578), (480, 322, 578), (324, 432, 540), (432, 324,
   540), (325, 360, 485), (360, 325, 485), (327, 436, 545), (436, 327,
   545), (328, 615, 697), (615, 328, 697), (330, 440, 550), (440, 330,
   550), (333, 444, 555), (444, 333, 555), (335, 804, 871), (804, 335,
   871), (336, 377, 505), (377, 336, 505), (339, 452, 565), (452, 339,
   565), (340, 357, 493), (357, 340, 493), (341, 420, 541), (420, 341,
   541), (342, 456, 570), (456, 342, 570), (344, 645, 731), (645, 344,
   731), (345, 460, 575), (460, 345, 575), (348, 464, 580), (464, 348,
   580), (350, 576, 674), (576, 350, 674), (351, 468, 585), (468, 351,
   585), (352, 420, 548), (420, 352, 548), (354, 472, 590), (472, 354,
   590), (355, 852, 923), (852, 355, 923), (357, 360, 507), (360, 357,
   507), (360, 378, 522), (378, 360, 522), (363, 484, 605), (484, 363,
   605), (364, 585, 689), (585, 364, 689), (365, 876, 949), (876, 365,
   949), (366, 488, 610), (488, 366, 610), (368, 465, 593), (465, 368,
   593), (369, 492, 615), (492, 369, 615), (370, 888, 962), (888, 370,
   962), (372, 496, 620), (496, 372, 620), (375, 500, 625), (500, 375,
   625), (376, 705, 799), (705, 376, 799), (378, 504, 630), (504, 378,
   630), (380, 399, 551), (399, 380, 551), (381, 508, 635), (508, 381,
   635), (384, 440, 584), (440, 384, 584), (385, 552, 673), (552, 385,
   673), (387, 516, 645), (516, 387, 645), (390, 432, 582), (432, 390,
   582), (392, 630, 742), (630, 392, 742), (393, 524, 655), (524, 393,
   655), (396, 403, 565), (403, 396, 565), (399, 468, 615), (468, 399,
   615), (400, 420, 580), (420, 400, 580), (402, 536, 670), (536, 402,
   670), (405, 540, 675), (540, 405, 675), (406, 792, 890), (792, 406,
   890), (407, 624, 745), (624, 407, 745), (408, 506, 650), (506, 408,
   650), (411, 548, 685), (548, 411, 685), (414, 448, 610), (448, 414,
   610), (416, 612, 740), (612, 416, 740), (417, 556, 695), (556, 417,
   695), (420, 441, 609), (441, 420, 609), (423, 564, 705), (564, 423,
   705), (424, 795, 901), (795, 424, 901), (425, 660, 785), (660, 425,
   785), (426, 568, 710), (568, 426, 710), (429, 460, 629), (460, 429,
   629), (432, 495, 657), (495, 432, 657), (435, 580, 725), (580, 435,
   725), (438, 584, 730), (584, 438, 730), (440, 462, 638), (462, 440,
   638), (441, 588, 735), (588, 441, 735), (444, 592, 740), (592, 444,
   740), (447, 596, 745), (596, 447, 745), (448, 720, 848), (720, 448,
   848), (450, 544, 706), (544, 450, 706), (451, 780, 901), (780, 451,
   901), (453, 604, 755), (604, 453, 755), (455, 504, 679), (504, 455,
   679), (456, 608, 760), (608, 456, 760), (459, 612, 765), (612, 459,
   765), (460, 483, 667), (483, 460, 667), (462, 616, 770), (616, 462,
   770), (464, 777, 905), (777, 464, 905), (465, 620, 775), (620, 465,
   775), (468, 595, 757), (595, 468, 757), (471, 628, 785), (628, 471,
   785), (473, 864, 985), (864, 473, 985), (474, 632, 790), (632, 474,
   790), (475, 840, 965), (840, 475, 965), (476, 480, 676), (480, 476,
   676), (477, 636, 795), (636, 477, 795), (480, 504, 696), (504, 480,
   696), (481, 600, 769), (600, 481, 769), (483, 644, 805), (644, 483,
   805), (486, 648, 810), (648, 486, 810), (489, 652, 815), (652, 489,
   815), (492, 656, 820), (656, 492, 820), (495, 660, 825), (660, 495,
   825), (498, 664, 830), (664, 498, 830), (500, 525, 725), (525, 500,
   725), (501, 668, 835), (668, 501, 835), (504, 550, 746), (550, 504,
   746), (507, 676, 845), (676, 507, 845), (510, 680, 850), (680, 510,
   850), (513, 684, 855), (684, 513, 855), (516, 688, 860), (688, 516,
   860), (519, 692, 865), (692, 519, 865), (520, 546, 754), (546, 520,
   754), (522, 696, 870), (696, 522, 870), (525, 700, 875), (700, 525,
   875), (528, 605, 803), (605, 528, 803), (531, 708, 885), (708, 531,
   885), (532, 624, 820), (624, 532, 820), (533, 756, 925), (756, 533,
   925), (534, 712, 890), (712, 534, 890), (537, 716, 895), (716, 537,
   895), (540, 567, 783), (567, 540, 783), (543, 724, 905), (724, 543,
   905), (546, 728, 910), (728, 546, 910), (549, 732, 915), (732, 549,
   915), (552, 736, 920), (736, 552, 920), (555, 572, 797), (572, 555,
   797), (558, 744, 930), (744, 558, 930), (560, 588, 812), (588, 560,
   812), (561, 748, 935), (748, 561, 935), (564, 752, 940), (752, 564,
   940), (567, 756, 945), (756, 567, 945), (570, 760, 950), (760, 570,
   950), (573, 764, 955), (764, 573, 955), (576, 660, 876), (660, 576,
   876), (579, 772, 965), (772, 579, 965), (580, 609, 841), (609, 580,
   841), (582, 776, 970), (776, 582, 970), (585, 648, 873), (648, 585,
   873), (588, 784, 980), (784, 588, 980), (591, 788, 985), (788, 591,
   985), (594, 608, 850), (608, 594, 850), (595, 600, 845), (600, 595,
   845), (597, 796, 995), (796, 597, 995), (600, 630, 870), (630, 600,
   870), (612, 759, 975), (759, 612, 975), (615, 728, 953), (728, 615,
   953), (616, 663, 905), (663, 616, 905), (620, 651, 899), (651, 620,
   899), (621, 672, 915), (672, 621, 915), (624, 715, 949), (715, 624,
   949), (638, 720, 962), (720, 638, 962), (640, 672, 928), (672, 640,
   928), (650, 720, 970), (720, 650, 970), (660, 693, 957), (693, 660,
   957), (680, 714, 986), (714, 680, 986), (696, 697, 985), (697, 696,
   985)