20
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Are we to output truthy and falsy outputs or is two consistent values ok? \$\endgroup\$ – Wheat Wizard Mar 5 '18 at 19:49
  • \$\begingroup\$ @WheatWizard two consistent values are acceptable. \$\endgroup\$ – JungHwan Min Mar 5 '18 at 19:51
  • \$\begingroup\$ However much the truncations overlap, the result is equivalent to a smaller triangle with smaller truncations (if truncations can have side length 0). \$\endgroup\$ – Asone Tuhid Mar 5 '18 at 22:33

14 Answers 14

8
\$\begingroup\$

Haskell, 46 45 bytes

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

Try it online!

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

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

\$\endgroup\$
  • \$\begingroup\$ Really nice explanation! \$\endgroup\$ – Amphibological Jul 10 '18 at 17:07
6
\$\begingroup\$

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!

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

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.

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

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

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
\$\endgroup\$
  • \$\begingroup\$ You beat me too it, +1 GG \$\endgroup\$ – FantaC Mar 5 '18 at 20:12
  • \$\begingroup\$ @tfbninja I wish I had a nicer explanation for what ɐ- does \$\endgroup\$ – mudkip201 Mar 5 '18 at 20:15
  • 1
    \$\begingroup\$ added, you can rollback if you want though \$\endgroup\$ – FantaC Mar 5 '18 at 20:17
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Looks like your check is overlooking a==1. \$\endgroup\$ – xnor Mar 5 '18 at 20:22
  • \$\begingroup\$ @xnor I see why. It has been fixed now. \$\endgroup\$ – Wheat Wizard Mar 5 '18 at 20:32
3
\$\begingroup\$

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?
\$\endgroup\$
  • \$\begingroup\$ e.2,@(!-/3*!)[:i.2+] \$\endgroup\$ – FrownyFrog Apr 28 '18 at 11:09
  • \$\begingroup\$ e.2,@(!-/3*!)1+i.,] maybe \$\endgroup\$ – FrownyFrog May 25 '18 at 16:35
3
\$\begingroup\$

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

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

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

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!

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

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.

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

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

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

Add++, 36 bytes

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

Try it online!

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