Square Triangles

Question

A positive integer x is a square triangle number iff there are two different positive integers, y and z, which are smaller than x such that all of the sums

x + y

x + z

y + z

are perfect squares.

For example 30 is a square triangle number because

30 + 6 = 6²

30 + 19 = 7²

6 + 19 = 5²

Your task is to write some code that takes a positive integer as input and determines whether or not it is a square triangle number. You should output one of two distinct values, one if the input is a square triangle number and the other otherwise.

This is code-golf so answers will be scored in bytes with fewer bytes being better.

Testcases

Here are all of the square triangle numbers under 1000

30,44,47,48,60,66,69,70,78,86,90,92,94,95,96,98,108,113,116,118,120,122,124,125,126,132,138,142,147,150,152,154,156,157,158,159,160,165,170,176,180,182,185,186,188,190,192,194,195,196,197,198,200,207,212,214,216,218,221,222,224,227,230,232,234,236,237,238,239,240,246,248,253,258,260,264,266,267,268,270,273,274,275,276,278,280,281,282,283,284,285,286,290,296,298,302,303,306,308,310,312,314,317,318,320,322,323,324,326,328,329,330,331,332,333,334,335,336,338,340,344,347,350,351,352,356,357,360,362,364,368,370,371,372,374,376,377,378,380,382,384,385,386,387,388,389,390,392,394,396,402,405,408,410,413,414,415,418,420,422,423,424,426,429,430,432,434,435,436,438,440,442,443,444,445,446,447,448,449,452,456,458,462,464,466,467,468,470,472,476,477,479,480,482,484,485,488,490,491,492,494,496,497,498,500,501,502,503,504,505,506,507,508,509,510,512,515,516,518,522,523,524,527,528,530,533,536,538,540,542,543,546,548,549,550,551,552,554,557,558,560,562,563,564,566,568,569,570,571,572,573,574,575,576,578,579,582,585,588,590,592,593,594,598,600,602,603,604,605,606,608,610,612,613,614,615,616,618,620,621,623,624,626,627,628,630,632,633,634,636,638,639,640,641,642,643,644,645,646,650,652,656,657,658,659,660,662,666,667,668,670,672,674,677,678,680,682,683,686,687,689,690,692,694,695,696,698,700,701,702,704,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,722,723,726,728,730,734,737,739,740,742,744,745,746,750,752,755,756,758,760,762,764,765,767,768,770,772,773,774,776,778,779,780,782,783,784,785,786,788,789,790,791,792,793,794,795,796,797,798,800,802,803,804,805,810,812,814,816,817,818,819,820,822,825,826,827,828,829,830,832,833,834,836,837,838,840,842,846,847,848,849,850,851,852,854,855,856,858,860,861,862,863,864,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,882,884,888,890,891,893,896,897,898,902,903,904,905,908,912,913,914,915,916,918,920,923,924,926,927,928,929,931,932,933,935,936,938,940,941,942,944,946,947,948,950,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,970,972,974,976,978,980,981,984,986,987,988,992,993,995,996,998

OEIS A242445

@Mr.Xcoder Thanks! I probably should have checked the OEIS first. I'll add that to the body to make it more searchable. — Wheat Wizard, Jan 11, 2018 at 16:07
For clarification purposes, "...iff there are two different positive integers, y and z, which are smaller than x..." means that y < x and z < x or that y+z < x? — J. Sallé, Jan 11, 2018 at 16:19

H.PWiz · Accepted Answer · 2018-12-17 12:03:10Z

8

Haskell, 62 bytes

f x|l<-(^2)<$>[1..x]=or[b>x|c<-l,b<-l,a<-l,a-x+b-x==c,c<b,b<a]

Try it online!

edited Dec 17, 2018 at 12:03

answered Jan 11, 2018 at 17:45

H.PWiz

11.6k2 gold badges20 silver badges56 bronze badges

Add a comment |

Dennis · Accepted Answer · 2018-01-11 16:58:58Z

Jelly, 12 bytes

R²_fṖŒcS€Æ²Ẹ

Try it online!

How it works

R²_fṖŒcS€Æ²Ẹ  Main link. Argument: x

R             Range; yield [1, 2, ..., x].
 ²            Square; yield [1², 2², ..., x²].
  _           Subtract; yield [1²-x, 2²-x, ..., x²-x].
    Ṗ         Pop; yield [1, 2, ..., x-1].
   f          Filter; keep those values of n²-x that lie between 1 and x-1.
              This list contains all integers n such that n+x is a perfect square.
              We'll try to find suitable values for y and z from this list.
     Œc       Yield all 2-combinations [y, z] of these integers.
       S€     Take the sum of each pair.
         Æ²   Test each resulting integer for squareness.
           Ẹ  Any; check is the resulting array contains a 1.

Rod · Accepted Answer · 2018-01-11 18:53:16Z

7

Python 2, 93 87 86 bytes

^{-1 byte thanks to Dennis}

lambda n:{0}in[{m**.5%1for m in[x+y,n+x,n+y]}for x in range(1,n)for y in range(1+x,n)]

Try it online!

edited Jan 11, 2018 at 18:53

answered Jan 11, 2018 at 16:57

Rod

18.4k4 gold badges30 silver badges89 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Brachylog, 19 bytes

~hṪ>₁ℕ₁ᵐ≜¬{⊇Ċ+¬~^₂}

Try it online!

Also 19 bytes: ~hṪ>₁ℕ₁ᵐ≜{⊇Ċ+}ᶠ~^₂ᵐ

Explanation

~hṪ                    Ṫ = [Input, A, B]
  Ṫ>₁                  Ṫ is strictly decreasing (i.e. Input > A > B)
  Ṫ  ℕ₁ᵐ               All members of Ṫ are in [1, +∞)
  Ṫ     ≜              Assign values to A and B that fit those constraints
  Ṫ      ¬{       }    It is impossible for Ṫ…
           ⊇Ċ            …that one of its 2-elements subset…
            Ċ+           …does not sum…
              ¬~^₂       …to a square

AdmBorkBork · Accepted Answer · 2018-01-11 16:49:02Z

PowerShell, 150 bytes

param($x)filter f($a,$b){($c=[math]::Sqrt($a+$b))-eq[math]::Floor($c)}1..($i=$x-1)|%{$y=$_;1..$i|%{$o+=+($y-ne$_)*(f $x $y)*(f $x $_)*(f $y $_)}};!!$o

Try it online! or Verify some test cases

Takes input $x. Establishes a filter (here equivalent to a function) on two inputs $a,$b, which returns a Boolean true iff the [math]::sqrt of $a+$b is -equal to the Floor of that square root (i.e., it's an integer square root).

The rest of it is the meat of the program. We double-for loop up from 1 to $x-1. Each iteration, we check whether $y is -notequal to $_ (i.e., $z), and whether the function is true for all combinations of $x, $y and $_. If it is, $o is incremented by one (which makes it non-zero).

Finally, at the end, we double-Boolean-negate $o, which turns 0 into False and non-zero into True. That's left on the pipeline and output is implicit.

colossus16 · Accepted Answer · 2018-01-11 17:25:17Z

4

Haskell, 75 69 bytes

f x=or[all(`elem`map(^2)[1..x])[x+y,x+z,y+z]|y<-[1..x-1],z<-[1..y-1]]

Try it online!

Could probably be improved if someone knows a shorter way to test if a number is square. I'm pretty sure using sqrt ends up being longer because floor turns the result into an integral type so you need to put fromIntegral in somewhere before you can compare to the original.

EDIT: Thanks @Wheat Wizard for taking off 6 bytes!

edited Jan 11, 2018 at 17:25

answered Jan 11, 2018 at 17:06

colossus16

1,6616 silver badges9 bronze badges

Add a comment |

Neil · Accepted Answer · 2018-01-11 17:36:17Z

4

JavaScript (ES7), 75 71 bytes

f=
n=>(g=i=>i?--j?[n+i,i+j,j+n].some(e=>e**.5%1)?g(i):1:g(j=i-1):0)(j=n-1)

<input type=number min=1 oninput=o.textContent=f(+this.value)><pre id=o>

edited Jan 11, 2018 at 17:36

answered Jan 11, 2018 at 16:56

Neil

166k12 gold badges69 silver badges273 bronze badges

\$\begingroup\$ Seems like you ninja'd me by 2 minutes. :) Ours answers are very close, so shall I delete mine? \$\endgroup\$
– Arnauld
Jan 11, 2018 at 17:14
\$\begingroup\$ @Arnauld No, I'm sure you arrived at your solution independently. \$\endgroup\$
– Neil
Jan 11, 2018 at 17:32

Add a comment |

Mr. Xcoder · Accepted Answer · 2018-01-13 15:44:23Z

4

05AB1E, 18 bytes

Lns-IL¨Ãæ2ù€OÅ²O0›

Try it online!

Thanks to Emigna for -3 -1 byte ~~and a fix~~!

edited Jan 13, 2018 at 15:44

answered Jan 11, 2018 at 17:10

Mr. Xcoder

42.3k9 gold badges79 silver badges214 bronze badges

\$\begingroup\$ You don't need the 2 €'s as both n and O vectorizes. This also doesn't work as the final 2 bytes will return true for any list with at least 1 value, even if only contains false values. This can be fixed (and shortened) by using Z instead. \$\endgroup\$
– Emigna
Jan 12, 2018 at 7:04
\$\begingroup\$ @Emigna Thank you! (BTW I did need €O and that’s why the previous approach did work with `º) \$\endgroup\$
– Mr. Xcoder
Jan 12, 2018 at 7:14
\$\begingroup\$ It didn't work though. Check for example 45, that should return false. \$\endgroup\$
– Emigna
Jan 12, 2018 at 7:16
\$\begingroup\$ Um huh, ok. Anyway, updated now. Thanks \$\endgroup\$
– Mr. Xcoder
Jan 12, 2018 at 7:17
\$\begingroup\$ @Sanchises Fixed. Thanks \$\endgroup\$
– Mr. Xcoder
Jan 12, 2018 at 16:12

Add a comment |

Giuseppe · Accepted Answer · 2018-01-11 19:58:11Z

R, 79 bytes

function(x){s=(1:x)^2
S=outer(y<-(z=s-x)[z>0&z<x],y,"+")
diag(S)=0
any(S%in%s)}

Try it online!

computes all the values of y,z with y<-(z=s-x)[z>0&z<x], then computes all their sums with outer(y,y,"+"). This yields a square matrix where off-diagonal entries are potentially squares, as y==z only if they are on the diagonal. Hence, diag(S)=0 sets the diagonals to zero, which are not perfect squares, and we test to see if any element of S is %in%s.

mercator · Accepted Answer · 2018-01-13 19:33:17Z

SWI-Prolog, 88 bytes

s(A,B,C):-between(A,B,C),C<B,between(1,B,X),B+C=:=X*X.
g(X):-s(1,X,Y),s(Y,X,Z),s(Y,Z,Y).

Try it online!

s(A, B, C) :-
    between(A, B, C), % Find an integer C between A and B (inclusive),
    C < B,            % which is less than B.
    between(1, B, X), % Find an integer X between 1 and B (inclusive),
    B+C =:= X*X.      % of which (B+C) is the square.
g(X) :-
    s(1, X, Y), % Find Y: 1 <= Y < X, and X+Y is a perfect square
    s(Y, X, Z), % Find Z: Y <= Z < X, and X+Z is a perfect square
    s(Y, Z, Y). % Make sure that Z > Y and Y+Z is a perfect square

g(X) is the rule that takes an integer as parameter and outputs whether it is a square triangle number (true/false).

Arnauld · Accepted Answer · 2018-01-11 16:58:42Z

2

JavaScript (ES7), 72 bytes

Returns 0 or 1.

x=>(g=y=>z?y>z?![x+y,x+z,y+z].some(n=>n**.5%1)|g(y-1):g(x-1,z--):0)(z=x)

Demo

let f=

x=>(g=y=>z?y>z?![x+y,x+z,y+z].some(n=>n**.5%1)|g(y-1):g(x-1,z--):0)(z=x)

for(n = 1; n < 150; n++) {
  f(n) && console.log(n)
}

answered Jan 11, 2018 at 16:58

Arnauld

188k20 gold badges171 silver badges630 bronze badges

Add a comment |

Steadybox · Accepted Answer · 2018-01-11 22:08:37Z

2

C, 113 bytes

p(n){return(int)sqrt(n)==sqrt(n);}f(x,y,z,r){for(r=y=0;++y<x;)for(z=y;++z<x;p(x+y)&p(x+z)&p(z+y)&&++r);return!r;}

Returns 0 if the number is square triangle, 1 otherwise.

Try it online!

answered Jan 11, 2018 at 22:08

Steadybox

16.5k5 gold badges40 silver badges84 bronze badges

\$\begingroup\$ I'm guessing the return(int)sqrt(n)==sqrt(n) is being parsed as return((int)sqrt(n))==sqrt(n) as opposed to the more obvious return(int)(sqrt(n)==sqrt(n))? If not can you explain what p is doing? \$\endgroup\$
– MD XF
Jan 12, 2018 at 3:16
\$\begingroup\$ @MDXF Type cast has higher precedence than ==, so the expression is parsed as ((int)sqrt(n))==sqrt(n) like you guessed. \$\endgroup\$
– Steadybox
Jan 12, 2018 at 7:51

Add a comment |

Uriel · Accepted Answer · 2018-01-11 22:35:47Z

2

APL (Dyalog), 49 bytes

{∨/{0=+/(⍺=⍵),1|.5*⍨(⍺+⍵)(⍺+k)(⍵+k)}/¨,⍳2⍴1-⍨k←⍵}

Try it online!

answered Jan 11, 2018 at 22:35

Uriel

13.1k4 gold badges16 silver badges44 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Jelly, 15 bytes

ṖŒc;€ŒcS€Æ²ẠƊ€Ẹ

Try it online!

How?

ṖŒc;€ŒcS€Æ²ẠƊ€Ẹ || Full program.
                ||
Ṗ               || Popped range. Yields [1, N) ∩ ℤ.
 Œc             || Pairs (two-element combinations).
   ;€           || Append N to each.
            Ɗ€  || For each of the lists, check whether:
           Ạ    || ... All ...
       S€       || ... The sums of each of their...
     Œc         || ... Disjoint Pairs
         Æ²     || ... Are perfect squares.
              Ẹ || Test whether there is any value that satisfies the above.

Οurous · Accepted Answer · 2018-01-12 06:08:14Z

1

Clean, 95 88 86 bytes

import StdEnv
@x#l=[1..x-1]
=or[all(\n=or[i^2==n\\i<-l])[x+y,y+z,z+x]\\y<-l,z<-l|y<>z]

Try it online!

edited Jan 12, 2018 at 6:08

answered Jan 12, 2018 at 4:46

Οurous

8,0961 gold badge15 silver badges37 bronze badges

Add a comment |

G B · Accepted Answer · 2018-01-12 07:32:27Z

1

Ruby, 73 bytes

->n{(1...n).any?{|b|(1...b).any?{|c|[n+b,b+c,n+c].all?{|r|r**0.5%1==0}}}}

Try it online!

answered Jan 12, 2018 at 7:32

G B

21.3k1 gold badge19 silver badges51 bronze badges

Add a comment |

gggg · Accepted Answer · 2018-01-12 16:19:27Z

1

Julia 0.6, 61 bytes

Start reading from the function all. The first argument is an anonymous function checking that the square root of a number is an integer, this is applied to each value in the second argument. The single argument to any is a Generator with two for loops, which for each iteration contains the output of the all function.

Thanks to Mr Xcoder for -2 bytes.

x->any(all(x->√x%1==0,[x+y,x+z,y+z])for y=1:x-1for z=1:y-1)

Try it online!

edited Jan 12, 2018 at 16:19

answered Jan 11, 2018 at 16:29

gggg

2,00510 silver badges9 bronze badges

Add a comment |

mudkip201 · Accepted Answer · 2018-01-13 15:10:46Z

1

Pyt, 63 bytes

0←Đ⁻Đ`⁻Đ3ȘĐ3Ș+√ĐƖ=4ȘĐ3ȘĐ3Ș+√ĐƖ=4ȘĐ3ȘĐ3Ș+√ĐƖ=4Ș6Ș**4Ș↔+↔łŕ⁻Đłŕŕŕ

Tests all possible combinations of y,z such that 1≤z<y<x

Returns 1 if x is a square triangle number, 0 otherwise

Try it online!

answered Jan 13, 2018 at 15:10

mudkip201

9731 gold badge6 silver badges10 bronze badges

Add a comment |

Sanchises · Accepted Answer · 2018-01-23 12:45:56Z

MATL, 20 19 18 bytes

q:2XN!tG+wsvX^1\aA

Try it online! Returns 1 for falsey, 0 for truthy.

Testcases up to 500: Try it online! (using H instead of G). Runtime is quadratic in the input size, so enumerating the testcases from 1 to n runs in O(n^3), which is why enumerating all testcases up to 1000 times out on TIO.

-1 byte and a conjecture less thanks to @LuisMendo
-1 byte by a more clever check of integer-ness.

Removing q generates a sequence with the desired sequence as a subset, but without the constraint that y and z be strictly smaller than x. An example is x=18, y=7, z=18.

q:    % Push 1...n-1
2XN   % Generate all permuations of choosing 2 numbers from the above.
!     % Transpose to take advantage of column-wise operators later on.
 G+   % Add n to these combinations, to have all combos of x+y and x+z
t  ws % Duplicate the combinations, swap to the top of the stack and sum to get y+z.
v     % Concatenate vertically. The array now contains columns of [x+y;x+z;y+z].
X^    % Element-wise square root of each element
1\    % Get remainder after division by 1.
a     % Check if any have remainders, columnwise. If so, it is not a square triangle.
A     % Check whether all combinations are not square triangle.

@LuisMendo Thanks. Too bad, I was hoping for an answer to my conjecture, but I can't just ask it at Math.SE without showing some effort for a proof... — Sanchises, Jan 12, 2018 at 23:27

Stack Exchange Network

Square Triangles

Testcases

19 Answers 19

Haskell, 62 bytes

Jelly, 12 bytes

How it works

Python 2, 93 87 86 bytes

Brachylog, 19 bytes

Explanation

PowerShell, 150 bytes

Haskell, 75 69 bytes

JavaScript (ES7), 75 71 bytes

05AB1E, 18 bytes

R, 79 bytes

SWI-Prolog, 88 bytes

JavaScript (ES7), 72 bytes

Demo

C, 113 bytes

APL (Dyalog), 49 bytes

Jelly, 15 bytes

How?

Clean, 95 88 86 bytes

Ruby, 73 bytes

Julia 0.6, 61 bytes

Pyt, 63 bytes

MATL, 20 19 18 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
number
decision-problem
or ask your own question.

Hot Network Questions

Square Triangles

Testcases

19 Answers 19

Haskell, 62 bytes

Jelly, 12 bytes

How it works

Python 2, 93 87 86 bytes

Brachylog, 19 bytes

Explanation

PowerShell, 150 bytes

Haskell, 75 69 bytes

JavaScript (ES7), 75 71 bytes

05AB1E, 18 bytes

R, 79 bytes

SWI-Prolog, 88 bytes

JavaScript (ES7), 72 bytes

Demo

C, 113 bytes

APL (Dyalog), 49 bytes

Jelly, 15 bytes

How?

Clean, 95 88 86 bytes

Ruby, 73 bytes

Julia 0.6, 61 bytes

Pyt, 63 bytes

MATL, 20 19 18 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfnumberdecision-problem or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
number
decision-problem
or ask your own question.