Truncated triangular number

A common property of triangular numbers is that they can be arranged in a triangle. For instance, take 21 and arrange into a triangle of os:

     o 
    o o
   o o o
  o o o o
 o o o o o
o o o o o o

Let's define a "truncation:" cutting triangles of the same size from each corner. One way to truncate 21 is as follows:

     . 
    . .
   o o o
  o o o o
 . o o o .
. . o o . .

(The triangles of . are cut from the original).

There are 12 os remaining, so 12 is a truncated triangle number.

Task

Your job is to write a program or a function (or equivalent) that takes an integer and returns (or use any of the standard output methods) whether a number is a truncated triangle number.

Rules

No standard loopholes.
The input is a non-negative integer.
A cut cannot have a side length exceeding the half of that of the original triangle (i.e. cuts cannot overlap)
A cut can have side length zero.

Test cases

Truthy:

Falsy:

Test cases for all integers up to 50: TIO Link

This is code-golf, so submissions with shortest byte counts in each language win!

JungHwan Min

Posted 2018-03-05T19:05:43.213

Reputation: 13 290

1Are we to output truthy and falsy outputs or is two consistent values ok? – Post Rock Garf Hunter – 2018-03-05T19:49:59.477

@WheatWizard two consistent values are acceptable. – JungHwan Min – 2018-03-05T19:51:00.087

However much the truncations overlap, the result is equivalent to a smaller triangle with smaller truncations (if truncations can have side length 0). – Asone Tuhid – 2018-03-05T22:33:01.350

Answers

Haskell, 46 45 bytes

f n|t<-scanl(+)0[1..n]=or[x-3*y==n|x<-t,y<-t]

Try it online!

nimi

Posted 2018-03-05T19:05:43.213

Reputation: 34 639

Haskell, 46 bytes

f n=or[mod(gcd(p^n)(4*n-1)-5)12<3|p<-[1..4*n]]

Try it online!

Having thrown a bunch of number theory at the problem (thanks @flawr), I found this characterization:

n is a truncated triangular number exactly if in the prime factorization of 4n-1, any prime of the form 5 mod 12 or 7 mod 12 appears an even number of times.

This means, for instance, that 4n-1 may not be divisible by 5 unless it's further divisible by 5²=25 and the total number of 5 factors is even.

Haskell doesn't have a factorization-built-in, but we can improvise. If we work with factorizations into primes powers like 12=3*4, we can use the equivalent statement:

n is a truncated triangular number exactly if the factorization of 4n-1 into prime powers has no terms of form 5 mod 12 or 7 mod 12.

We can extract the power of a prime p appearing in k as gcd(p^k)k. We then check that the result r is not 5 or 7 modulo 12 as mod(r-5)12>2. Note that r is odd. We also check composites as p, lacking a way to tell them from primes, but the check will pass as long as its factors do.

Finally, negating >2 to <3 and switching True/False in output saves a byte by letting us use or instead of and.

A related characterization is that the divisors of 4n-1 taken modulo 12 have more total 1's and 11's than 5's and 7's.

53 bytes

f n=sum[abs(mod k 12-6)-3|k<-[1..4*n],mod(4*n)k==1]<0

Try it online!

xnor

Posted 2018-03-05T19:05:43.213

Reputation: 115 687

Really nice explanation! – Amphibological – 2018-07-10T17:07:27.323

Python 2, 52 bytes

f=lambda n,b=1:b>n+1or(8*n-2+3*b*b)**.5%1>0<f(n,b+1)

Try it online!

Outputs True/False flipped. Uses this characterization:

n is a truncated triangular number exactly if 8n-2 has form a²-3b² for some integers a,b.

We check whether any 8*n-2+3*b*b is a perfect square for any b from 1 to n+1. We avoid b=0 because it gives an error for a square root of a negative when n==0, but this can't hurt because only odd b can work.

Done non-recursively:

Python 2, 53 bytes

lambda n:0in[(8*n-2+3*b*b)**.5%1for b in range(~n,0)]

Try it online!

xnor

Posted 2018-03-05T19:05:43.213

Reputation: 115 687

Are recursive and non-recursive solutions usually so competitive with each other in python? – boboquack – 2018-03-06T06:24:56.190

@boboquack Usually the recursive solution wins by a few bytes over range. Here it's close because b>n+1 is a lengthy base case and 0in is short. – xnor – 2018-03-06T06:29:57.430

R, 45 43 bytes

-2 bytes thanks to Vlo

(n=scan())%in%outer(T<-cumsum(0:n),3*T,"-")

Try it online!

I'm fairly sure we only need to check the first n triangular numbers for this; brute force checks if n is in the pairwise differences of the triangular numbers and their triples.

Giuseppe

Posted 2018-03-05T19:05:43.213

Reputation: 21 077

scan() n<-scan();n%in%outer(T<-cumsum(0:n),3*T,"-") – Vlo – 2018-03-05T19:33:03.240

@Vlo facepalm I got into the habit of using functions everywhere... – Giuseppe – 2018-03-05T19:34:58.670

And I just got into the habit of using <- assignment instead of (n=scan())...tsk tsk – Vlo – 2018-03-05T19:44:18.670

Jelly, 10 bytes

0r+\ð_÷3f⁸

A monadic link accepting an integer and returning a truthy value (a non empty list) or a falsey value (an empty list).

Try it online! (footer performs Python representation to show the [0] results as they are)
...or see a test-suite (runs for 0 to 20 inclusive)

How?

Given N, forms the first N triangle numbers, subtracts N from each, divides each result by 3 and keeps any results that are one of the first N triangle numbers.

0r+\ð_÷3f⁸ - Link: integer, N             e.g. 7
0r         - zero inclusive range N            [    0, 1, 2,   3,    4, 5,   6,   7]
  +\       - cumulative reduce with addition   [    0, 1, 3,   6,   10,15,  21,  28]
    ð      - start a new dyadic link with that, t, on the left and N on the right
     _     - t subtract N (vectorises)         [   -7,-6,-3,  -1,    3, 8,  14,  21]
      ÷3   - divivde by three (vectorises)     [-2.33,-2,-1.33,-0.33,1,2.67,4.67, 7]
         ⁸ - chain's left argument, t          [    0, 1, 3,   6,   10,15,  21,  28]
        f  - filter keep                       [                     1             ]
                                               - a non-empty list, so truthy

Jonathan Allan

Posted 2018-03-05T19:05:43.213

Reputation: 67 804

Pyt, 10 bytes

Đř△Đ3*ɐ-Ƒ∈

Try it online!

Explanation:

        Implicit input
Đ       Duplicate input
ř       Push [1,2,...,input]
△       For each element k in the array, get the kth triangle number
Đ       Duplicate the top of the stack
3*      Multiply by 3
ɐ       ɐ - All possible:
 -                       subtractions between elements of the two arrays  
Ƒ       Flatten the nested array
∈       Is the input in the array

mudkip201

Posted 2018-03-05T19:05:43.213

Reputation: 833

You beat me too it, +1 GG – FantaC – 2018-03-05T20:12:16.057

@tfbninja I wish I had a nicer explanation for what ɐ- does – mudkip201 – 2018-03-05T20:15:38.847

1added, you can rollback if you want though – FantaC – 2018-03-05T20:17:22.883

Haskell, 48 bytes

f a|u<-[0..a]=or[x^2+x-3*(y^2+y)==2*a|x<-u,y<-u]

Try it online!

Post Rock Garf Hunter

Posted 2018-03-05T19:05:43.213

Reputation: 55 382

Looks like your check is overlooking a==1. – xnor – 2018-03-05T20:22:42.620

@xnor I see why. It has been fixed now. – Post Rock Garf Hunter – 2018-03-05T20:32:24.347

J, 22 bytes

e.[:,@(-/3*])2![:i.2+]

Try it online!

Straightforward and somewhat-poorly-golfed approach.

Explanation

e.[:,@(-/3*])2![:i.2+]
             2![:i.2+]  Range of triangular numbers up to N
      (-/3*])           All possible subtractions of 3T from T 
                        where T is triangular up to the Nth triangular number
    ,@                  Flattened into a single list
e.                      Is N in the list?

cole

Posted 2018-03-05T19:05:43.213

Reputation: 3 526

e.2,@(!-/3*!)[:i.2+] – FrownyFrog – 2018-04-28T11:09:22.807

e.2,@(!-/3*!)1+i.,] maybe – FrownyFrog – 2018-05-25T16:35:35.063

MATL, 12 bytes

tQ:qYst!3*-m

Outputs 1 for truthy, 0 for falsy.

Try it online! Or verify all test cases.

How it works, with example

Consider input 6

t      % Implicit input. Duplicate
       % STACK: 6, 6
Q:q    % Increase, range, decrease element-wise. Gives [0 1 ... n]
       % STACK: 6, [0 1 ... 6]
Ys     % Cumulative sum
       % STACK: 6, [0 1 3 6 10 15]
t!     % Duplicate, transpose
       % STACK: 6, [0 1 3 6 10 15], [0;
                                     1;
                                     3;
                                     6;
                                     10;
                                     15]
3*     % Times 3, element-wise
       % STACK: 6, [0 1 3 6 10 15 21 28 36 45 55], [0;
                                                    3;
                                                    9;
                                                    18;
                                                    30;
                                                    45]
-      % Subtract, element-wise with broadcast
       % STACK: 6, [  0   1   3   6  10  15  21;
                     -3  -2   0   3   7  12  18;
                     -9  -8  -6  -3   1   6  12;
                    -18 -17 -15 -12  -8  -3   3;
                    -30 -29 -27 -24 -20 -15  -9;
                    -45 -44 -42 -39 -35 -30 -24;
                     -63 -62 -60 -57 -53 -48 -42]
m      % Ismember. Implicit display
       % STACK: 1

Luis Mendo

Posted 2018-03-05T19:05:43.213

Reputation: 87 464

Ruby, 65 57 52 48 bytes

->n,b=0{b+=1;(8*n-2+3*b*b)**0.5%1==0||b<n&&redo}

Try it online!

Inspired by xnor's python answer

Asone Tuhid

Posted 2018-03-05T19:05:43.213

Reputation: 1 944

Python 3, 84 bytes

lambda n:1in set([((8*(n+(i*(i+1)/2)*3)+1)**0.5)%4==1for i in range(n)])or n in[0,1]

Try it online!

Dat

Posted 2018-03-05T19:05:43.213

Reputation: 879

05AB1E, 11 bytes

ÅT3*+8*>Å²Z

Try it online!

Explanation

ÅT            # get a list of triangle numbers upto input
  3*          # multiply each by 3
    +         # add input to each
     8*       # multiply each by 8
       >      # increment each
        Å²    # check each for squareness
          Z   # max

This is based on the fact that a number T is triangular if 8T+1 is an odd perfect square.
We start on the list of triangles we could truncate, calculate the possible larger triangles based on them and check if it in fact is triangular.

Emigna

Posted 2018-03-05T19:05:43.213

Reputation: 50 798

Japt, 16 bytes

ò å+ d@Zd_-3*X¶U

Try it | Check all test cases

Explanation

                     :Implicit input of integer U
ò                    :Range [0,U]
  å+                 :Cumulative reduction by addition
     d@              :Does any X in array Z return true when passed through this function?
       Zd_           :  Does any element in Z return true when passe through this function?
          -3*X       :    Subtract 3*X
              ¶U     :    Check for equality with U

Alternative

ò å+ £Zm-3*XÃdøU

Try it

Shaggy

Posted 2018-03-05T19:05:43.213

Reputation: 24 623

Add++, 36 bytes

D,g,@,.5^di=
L,ßR¬+A↑>3€*A€+8€*1€+ºg

Try it online!

caird coinheringaahing

Posted 2018-03-05T19:05:43.213

Reputation: 13 702

Is this a truncated triangular number?

Truncated triangular number

Task

Rules

Test cases

Answers

Haskell, 46 45 bytes

Haskell, 46 bytes

Python 2, 52 bytes

R, 45 43 bytes

Jelly, 10 bytes

How?

Pyt, 10 bytes

Haskell, 48 bytes

J, 22 bytes

Explanation

MATL, 12 bytes

How it works, with example

Ruby, 65 57 52 48 bytes

Python 3, 84 bytes

05AB1E, 11 bytes

Japt, 16 bytes

Explanation

Alternative

Add++, 36 bytes