Square Triangles

23

2

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

Post Rock Garf Hunter

Posted 2018-01-11T16:05:43.593

Reputation: 55 382

6

This is OEIS A242445.

– Mr. Xcoder – 2018-01-11T16:06:48.500

@Mr.Xcoder Thanks! I probably should have checked the OEIS first. I'll add that to the body to make it more searchable. – Post Rock Garf Hunter – 2018-01-11T16:07:25.053

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é – 2018-01-11T16:19:21.557

2@J.Sallé The former – Post Rock Garf Hunter – 2018-01-11T16:20:48.833

Here test case with input and output are absent – RosLuP – 2018-01-13T11:01:26.577

What does it mean:"You should output one of two distinct values, one if the input is a square triangle number and the other otherwise."? Perhaps it has to return true false... – RosLuP – 2018-01-13T11:37:13.153

Answers

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!

H.PWiz

Posted 2018-01-11T16:05:43.593

Reputation: 10 962

7

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.

Dennis

Posted 2018-01-11T16:05:43.593

Reputation: 196 637

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!

Rod

Posted 2018-01-11T16:05:43.593

Reputation: 17 588

7

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

Fatalize

Posted 2018-01-11T16:05:43.593

Reputation: 32 976

4

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.

AdmBorkBork

Posted 2018-01-11T16:05:43.593

Reputation: 41 581

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>

Neil

Posted 2018-01-11T16:05:43.593

Reputation: 95 035

Seems like you ninja'd me by 2 minutes. :) Ours answers are very close, so shall I delete mine? – Arnauld – 2018-01-11T17:14:10.763

@Arnauld No, I'm sure you arrived at your solution independently. – Neil – 2018-01-11T17:32:22.527

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!

user1472751

Posted 2018-01-11T16:05:43.593

Reputation: 1 511

4

05AB1E, 18 bytes

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

Try it online!

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

Mr. Xcoder

Posted 2018-01-11T16:05:43.593

Reputation: 39 774

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. – Emigna – 2018-01-12T07:04:17.853

@Emigna Thank you! (BTW I did need €O and that’s why the previous approach did work with \º`) – Mr. Xcoder – 2018-01-12T07:14:48.867

It didn't work though. Check for example 45, that should return false. – Emigna – 2018-01-12T07:16:00.210

Um huh, ok. Anyway, updated now. Thanks – Mr. Xcoder – 2018-01-12T07:17:17.347

@Sanchises Fixed. Thanks – Mr. Xcoder – 2018-01-12T16:12:06.730

3

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.

Giuseppe

Posted 2018-01-11T16:05:43.593

Reputation: 21 077

3

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

mercator

Posted 2018-01-11T16:05:43.593

Reputation: 359

2

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.

Mr. Xcoder

Posted 2018-01-11T16:05:43.593

Reputation: 39 774

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

Arnauld

Posted 2018-01-11T16:05:43.593

Reputation: 111 334

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!

Steadybox

Posted 2018-01-11T16:05:43.593

Reputation: 15 798

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? – MD XF – 2018-01-12T03:16:51.410

@MDXF Type cast has higher precedence than ==, so the expression is parsed as ((int)sqrt(n))==sqrt(n) like you guessed.

– Steadybox – 2018-01-12T07:51:48.923

2

APL (Dyalog), 49 bytes

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

Try it online!

Uriel

Posted 2018-01-11T16:05:43.593

Reputation: 11 708

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!

gggg

Posted 2018-01-11T16:05:43.593

Reputation: 1 715

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!

Οurous

Posted 2018-01-11T16:05:43.593

Reputation: 7 916

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!

G B

Posted 2018-01-11T16:05:43.593

Reputation: 11 099

1

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.

Sanchises

Posted 2018-01-11T16:05:43.593

Reputation: 8 530

@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 – 2018-01-12T23:27:25.617

1https://qchu.wordpress.com/2009/07/02/square-roots-have-no-unexpected-linear-relationships/ here you go – mudkip201 – 2018-01-13T15:06:50.417

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!

mudkip201

Posted 2018-01-11T16:05:43.593

Reputation: 833

-1

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

RosLuP

Posted 2018-01-11T16:05:43.593

Reputation: 3 036

Asked: 2018-01-11T16:05:43.593

Viewed: 2 614 times

Active: 2018-12-17T12:03:10.910