# Is this a truncated triangular number?

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.

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 , so submissions with shortest byte counts in each language win!

• Are we to output truthy and falsy outputs or is two consistent values ok? – Sriotchilism O'Zaic Mar 5 '18 at 19:49
• @WheatWizard two consistent values are acceptable. – JungHwan Min Mar 5 '18 at 19:51
• 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 Mar 5 '18 at 22:33

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


Try it online!

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 52=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!

• Really nice explanation! – Amphibological Jul 10 '18 at 17:07

# 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 a2-3b2 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!

• Are recursive and non-recursive solutions usually so competitive with each other in python? – boboquack Mar 6 '18 at 6:24
• @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 Mar 6 '18 at 6:29

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

• scan() n<-scan();n%in%outer(T<-cumsum(0:n),3*T,"-") – Vlo Mar 5 '18 at 19:33
• @Vlo facepalm I got into the habit of using functions everywhere... – Giuseppe Mar 5 '18 at 19:34
• And I just got into the habit of using <- assignment instead of (n=scan())...tsk tsk – Vlo Mar 5 '18 at 19:44

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


# 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

• You beat me too it, +1 GG – FantaC Mar 5 '18 at 20:12
• @tfbninja I wish I had a nicer explanation for what ɐ- does – mudkip201 Mar 5 '18 at 20:15
• added, you can rollback if you want though – FantaC Mar 5 '18 at 20:17

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


Try it online!

• Looks like your check is overlooking a==1. – xnor Mar 5 '18 at 20:22
• @xnor I see why. It has been fixed now. – Sriotchilism O'Zaic Mar 5 '18 at 20:32

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

• e.2,@(!-/3*!)[:i.2+] – FrownyFrog Apr 28 '18 at 11:09
• e.2,@(!-/3*!)1+i.,] maybe – FrownyFrog May 25 '18 at 16:35

# MATL, 12 bytes

tQ:qYst!3*-m


Outputs 1 for truthy, 0 for falsy.

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


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

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

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

# Japt, 16 bytes

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


## Explanation

                     :Implicit input of integer U
ò                    :Range [0,U]
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

D,g,@,.5^di=