Is this a truncated triangular number?

Question

Related OEIS sequence: A008867

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:

0
1
3
6
7
10
12
15
18
19

Falsy:

2
4
5
8
9
11
13
14
16
17
20

Test cases for all integers up to 50: TIO Link

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

Answer 1

Haskell, 46 45 bytes

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

Try it online!

Answer 2

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!

Answer 3

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!

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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!

Answer 8

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?

Answer 9

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

Answer 10

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

Answer 11

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!

Answer 12

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.

Answer 13

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

Answer 14

Add++, 36 bytes

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

Try it online!