23
\$\begingroup\$

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 = 62

30 + 19 = 72

6 + 19 = 52


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 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

\$\endgroup\$
  • 6
    \$\begingroup\$ This is OEIS A242445. \$\endgroup\$ – Mr. Xcoder Jan 11 '18 at 16:06
  • \$\begingroup\$ @Mr.Xcoder Thanks! I probably should have checked the OEIS first. I'll add that to the body to make it more searchable. \$\endgroup\$ – Sriotchilism O'Zaic Jan 11 '18 at 16:07
  • \$\begingroup\$ 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? \$\endgroup\$ – J. Sallé Jan 11 '18 at 16:19
  • 2
    \$\begingroup\$ @J.Sallé The former \$\endgroup\$ – Sriotchilism O'Zaic Jan 11 '18 at 16:20
  • \$\begingroup\$ Here test case with input and output are absent \$\endgroup\$ – RosLuP Jan 13 '18 at 11:01

20 Answers 20

8
\$\begingroup\$

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!

\$\endgroup\$
7
\$\begingroup\$

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.
\$\endgroup\$
7
\$\begingroup\$

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!

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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>

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

05AB1E, 18 bytes

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

Try it online!

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

\$\endgroup\$
  • \$\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 '18 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 '18 at 7:14
  • \$\begingroup\$ It didn't work though. Check for example 45, that should return false. \$\endgroup\$ – Emigna Jan 12 '18 at 7:16
  • \$\begingroup\$ Um huh, ok. Anyway, updated now. Thanks \$\endgroup\$ – Mr. Xcoder Jan 12 '18 at 7:17
  • \$\begingroup\$ @Sanchises Fixed. Thanks \$\endgroup\$ – Mr. Xcoder Jan 12 '18 at 16:12
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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).

\$\endgroup\$
2
\$\begingroup\$

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)
}

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\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 '18 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 '18 at 7:51
2
\$\begingroup\$

APL (Dyalog), 49 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.    
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ @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... \$\endgroup\$ – Sanchises Jan 12 '18 at 23:27
  • 1
    \$\begingroup\$ qchu.wordpress.com/2009/07/02/… here you go \$\endgroup\$ – mudkip201 Jan 13 '18 at 15:06
-1
\$\begingroup\$

APL NARS, 340 bytes

r←h n;i;j;k
   r←¯1⋄→0×⍳(n≤0)∨n≥9E9
   l←(-n)+2*⍨(⌈√n)..⌊√¯1+2×n
   l←(l>0)/l
   r←1⋄i←0⋄k←⍴l
A: →C×⍳k≤i+←1⋄j←i+1
B: →A×⍳j>k⋄→0×⍳0=1∣√(i⊃l)+j⊃l⋄j+←1⋄→B
C: r←0

test

      :for i :in ⍳100⋄k←h i⋄:if 1=k⋄⍞←' ',i⋄:endif⋄:endfor⋄⎕←' '
  30  44  47  48  60  66  69  70  78  86  90  92  94  95  96  98 
      (¯5..5),¨h¨¯5..5
 ¯5 ¯1  ¯4 ¯1  ¯3 ¯1  ¯2 ¯1  ¯1 ¯1  0 ¯1  1 0  2 0  3 0  4 0  5 0 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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