# Triangular Square Numbers

Square numbers are those that take the form of $$\n^2\$$ where $$\n\$$ is an integer. These are also called perfect squares, because when you take their square root you get an integer.

The first 10 square numbers are: (OEIS)

0, 1, 4, 9, 16, 25, 36, 49, 64, 81

Triangular numbers are numbers that can form an equilateral triangle. The n-th triangle number is equal to the sum of all natural numbers from 1 to n.

The first 10 triangular numbers are: (OEIS)

0, 1, 3, 6, 10, 15, 21, 28, 36, 45

Square triangular numbers are numbers that are both square and triangular.

The first 10 square triangular numbers are: (OEIS)

0, 1, 36, 1225, 41616, 1413721, 48024900, 1631432881, 55420693056, 1882672131025, 63955431761796

There is an infinite number of square numbers, triangle numbers, and square triangular numbers.

Write a program or named function that given an input (parameter or stdin) number $$\n\$$, calculates the $$\n\$$th square triangular number and outputs/returns it, where n is a positive nonzero number. (For $$\n=1\$$ return 0)

For the program/function to be a valid submission it should be able to return at least all square triangle numbers smaller than $$\2^{31}-1\$$.

# Bonus

-4 bytes for being able to output all square triangular numbers less than 2^63-1

-4 bytes for being able to theoretically output square triangular numbers of any size.

+8 byte penalty for solutions that take nonpolynomial time.

Bonuses stack.

This is code-golf challenge, so the answer with the fewest bytes wins.

• I have added an 8 byte penalty for solutions that take >O(n) time to make it more fair for those who aim for faster code. Jun 25 '15 at 1:38
• @Rodolvertice I don't think you mean linear time. The iterative solution I have is quadratic time because there are n steps, and in each step the arithmetic takes linear time because the number of digits grows linearly in n. I don't think linear time is possible. Unless you're saying arithmetic operations are constant time?
– xnor
Jun 25 '15 at 1:41
• @Rodolvertice I mean that my iterative solution is not O(n). I think the cleaner thing to do is say "polynomial time" instead. If you assume linear time arithmetic, you get weird things like a solution using exponentiation being called constant time. Amortization doesn't come into play here.
– xnor
Jun 25 '15 at 1:51
• love to see something like that tagged in fastest-code Jun 25 '15 at 2:52
• "The first 10 square triangular numbers..." Surely you meant 11? :P Jun 25 '15 at 14:39

# CJam, 12 8 bytes

XUri{_34*@-Y+}*;


Makes use of the recurrence relation from the Wikipedia article.

The code is 16 bytes long and qualifies for both bonuses.

Try it online in the CJam interpreter.

### How it works

My code turned out to be identical to xnor's in always every aspect, except that I use CJam's stack instead of variables.

XU               e# Push 1 and 0 on the stack.
e# Since 34 * 0 - 1 + 2 = 1, this compensates for 1-based indexing.
ri{        }*  e# Do int(input()) times:
_34*        e#   Copy the topmost integer and multiply it by 34.
@-      e#   Subtract the bottommost integer from the result.
; e# Discard the last result.

• It runs instantly for very large inputs, but over 3000 it gives a Javascript range error on the online interpreter. Im going to try it on the java implementation. Jun 25 '15 at 2:10
• @Rodolvertice: I've switched to an iterative approach. It's actually shorter and it's less memory intensive. Jun 25 '15 at 3:11

## Python 2, 45 - 4 - 4 = 37

a=1;b=0
exec"a,b=b,34*b-a+2;"*input()
print a


Iterates using the reccurence

f(0) = 1
f(1) = 0
f(k) = 34*f(k-1)-f(k-2)+2


In theory, this supports numbers of any size, but runs in exponential time, so it shouldn't qualify for the bonuses. Should work for numbers of any size. For example, for 100, gives

1185827220993342542557325920096705939276583904852110550753333094088280194260929920844987597980616456388639477930416411849864965254621398934978872054025


A recursive solution uses 41 chars, but shouldn't qualify because it takes exponential time.

f=lambda k:k>2and 34*f(k-1)-f(k-2)+2or~-k

• That is quite cheaty, a 'loop' by string multiplication, haha. Jun 25 '15 at 1:17
• @Rodolvertice: Not cheaty at all really. Rather clever, and indeed fairly common on the site. Jun 25 '15 at 14:26
• I believe your recursive solution qualifies for bonus #1, which would have it tied with the exec solution. If you're allowed to change recursion limit, then it also could calculate a square triangle number of any size, qualifying it for #2. However, I'm not sure if that qualifies (@Rodolvertice).
Jun 25 '15 at 16:18

# Pyth, 16 - 4 - 4 = 8 bytes

Uses the recursive formula from the OEIS article.

K1uhh-*34G~KGtQZ


It uses the post-assign command which is pretty new and seems really cool. Uses reduce to iterate n-1 times because of 1-based indexing.

K1            Set K=1
u       tQ    Reduce input()-1 times
Z    With zero as base case
hh            +2
-           Subtract
*34G       34 times iterating variable
~K         Assign to K and use old value
G         Assign the iterating variable.


Seems to be polynomial because it loops n times and does math & assignment each iteration, but I'm not a computer scientist. Finishes n=10000 almost instantly.

• I think you can avoid subtracting 1 from the input if you start one iteration back at 0,1 rather than 1,0 -- see my Python answer.
– xnor
Jun 25 '15 at 5:17
• @xnor: I think he already does that. However, the result returned by the loop is your b. Jun 25 '15 at 5:43

# Oasis, 7 - 4 - 4 = -1

34*c-»T


Try it online!

Uses a(0) = 0, a(1) = 1; for n >= 2, a(n) = 34 * a(n-1) - a(n-2) + 2

Oasis supports arbitrary precision integers, so it should be able to go up to any number so long as no stack overflowing occurs. Let me know if this does not count for the bonus because of stack overflowing. It is also possible that this particular algorithm is non-polynomial, and let me know if that is the case.

Explanation:

34*c-»T -> 34*c-»10

a(0) = 0
a(1) = 1
a(n) = 34*c-»

34*c-»
34*    # 34*a(n-1)
c-  # 34*a(n-1)-a(n-2)
» # 34*a(n-1)-a(n-2)+2


Alternative solution:

-35*d+T


Instead uses a(n) = 35*(a(n-1)-a(n-2)) + a(n-3)

• The question says For n=1 return 0, but this returns 1. This is fixable by adding the -O option. May 13 '19 at 15:15

# JavaScript (ES6), 29-4 = 25 bytes

n=>n>1?34*f(n-1)-f(n-2)+2:n|0


Saved 5 bytes thanks to @IsmaelMiguel!

I've had to hardcode the 0, 1 and the negatives to avoid infinite recursion.

Console, I've named the function, f:

f(1);  // 0
f(13); // 73804512832419600
f(30); // 7.885505171090779e+42 or 7885505171090779000000000000000000000000000


EDIT: Turns out JavaScript will round the numbers to 16 (15) digits (Spec) because these numbers are too big causing an overflow. Put 714341252076979033 In your JavaScript console and see for yourself. It's more of a limitation of JavaScript

• I don't think this qualifies for the bonus. f(15) should return 85170343853180456676, not 85170343853180450000. Jun 25 '15 at 5:15
• @Dennis JavaScript must be truncating it. .-. Yup, JavaScript rounds to 16 digits when Jun 25 '15 at 5:22
• Try this one: n=>n?n<2?0:34*f(n-1)-f(n-2)+2:1 (31 bytes). I've tested till the 5th number. Jun 25 '15 at 9:08
• Here you now have a 29-bytes long solution: n=>n>1?34*f(n-1)-f(n-2)+2:!!n. It returns false on 0, true on 1 and 36 on 2. If you want it to return a number, you can replace !!n with +!!n. Jun 25 '15 at 9:26
• Fixed the problem. Use this: n=>n>1?34*f(n-1)-f(n-2)+2:n|0 (same byte count, now returns always numbers) Jun 25 '15 at 9:30

### Excel VBA - 90 bytes

n = InputBox("n")
x = 0
y = 1
For i = 1 To n
Cells(i, 1) = x
r = 34 * y - x + 2
x = y
y = r
Next i


When executed you are prompted for n, then the sequence up to and including n is output to column A:

It can be run up to and including n = 202 before it gives an overflow error.

# [Not Competing] Pyth (14 - 4 - 4 = 6 bytes)

K1u/^tG2~KGQ36


Used the first recurrence from OEIS, that after 0,1,36 you can find An = (An-1-1)2/An-2. A Not competing because this solution starts at 36, if you go lower you divide by zero (so input of 0 gives 36). Also had to hardcode 36.

Try it here

• This is OK as input will be nonzero. Mar 31 '21 at 20:17

# Java, 53 - 4 = 49 bytes

It's another simple recursion, but I don't often get to post Java with a <50 score, so...

long g(int n){return n<2?n<1?1:0:34*g(n-1)-g(n-2)+2;}


Now, for something non-recursive, it gets quite a bit longer. This one is both longer (112-4=108) -and- slower, so I'm not sure why I'm posting it except to have something iterative:

long f(int n){long a=0,b,c,d=0;for(;a<1l<<32&n>0;)if((c=(int)Math.sqrt(b=(a*a+a++)/2))*c==b){d=b;n--;}return d;}


# Julia, 51 bytes - 4 - 4 = 43

f(n)=(a=b=big(1);b-=1;for i=1:n a,b=b,34b-a+2end;a)


This uses the first recurrence relation listed on the Wikipedia page for square triangular numbers. It computes n = 1000 in 0.006 seconds, and n = 100000 in 6.93 seconds. It's a few bytes longer than a recursive solution but it's way faster.

Ungolfed + explanation:

function f(n)
# Set a and b to be big integers
a = big(1)
b = big(0)

# Iterate n times
for i = 1:n
# Use the recurrence relation, Luke
a, b = b, 34*b - a + 2
end

# Return a
a
end


Examples:

julia> for i = 1:4 println(f(i)) end
0
1
36
1225

julia> @time for i = 1:1000 println(f(i)) end
0
... (further printing omitted here)
elapsed time: 1.137734341 seconds (403573226 bytes allocated, 38.75% gc time)


## PHP, 6559 56-4=52 bytes

while($argv[1]--)while((0|$r=sqrt($s+=$f++))-$r);echo$s;


repeat until square root of $s is ∈ℤ: add $f to sum $s, increment $f;
repeat $argv[1] times. output sum. # Jelly, 13 - 8 = 5 bytes This qualifies for both bonuses. ×8‘,µÆ²Ạ 0Ç#Ṫ  Try it online! Done alongside caird coinheringaahing in chat. # Explanation ×8‘,µÆ²Ạ ~ Helper link. ×8 ~ 8 times the number. ‘ ~ Increment. , ~ Paired with the current number. µ ~ Starts a new monadic (1-arg) link. Æ² ~ Vectorized "Is Square?". Ạ ~ All. Return 1 only if both are truthy. 0Ç#Ṫ ~ Main link. 0 # ~ Starting from 0, collect the first N integers with truthy results, when applied: Ç ~ The last link as a monad. Ṫ ~ Last element. Output implicitly.  • 11 - 8 = 3 bytes Oct 6 '20 at 13:11 • @cairdcoinheringaahing Hi, feel free to edit or post a different submission! Oct 6 '20 at 21:13 • It's basically the same as yours (it doesn't even use any features that weren't available in 2017), so I don't reckon it warrants another answer Oct 6 '20 at 21:25 # Perl 6, 25 - 8 = 17 bytes {(0,1,2-*+34* *…*)[$_]}


Try it online!

# 05AB1E, 10 - 8 = 2 bytes

1ÎGDŠ34*Ìα


Try it online!

• And I thought I was clever using λ... Mar 31 '21 at 20:20

# APL (Dyalog Extended), 23-4-4 = 15 bytes

{⍵<2:⍵⋄2+-/34 1×∇¨⍵-⍳2}


Recursive dfn

⍵<2:⍵ is ⍵ less than 2, if so return ⍵

⋄ otherwise

∇¨⍵-⍳2 apply the function (∇) to the two previous values

34 1× multiply by the array 34 1

-/ subtract

2+ add 2

Try it online!

# Prolog, 70 74 - 4 - 4 = 66

n(X,R):-n(X,0,1,R).
n(X,A,B,R):-X=0,R=A;Z is X-1,E is 34*B-A+2,n(Z,B,E,R).


Running n(100,R) outputs:

X = 40283218019606612026870715051828504163181534465162581625898684828251284020309760525686544840519804069618265491900426463694050293008018241080068813316496


Takes about 1 second to run n(10000,X) on my computer.

Edit: The 66 version is tail-recursive. The previous non-tail-recursive version is the following:

n(X,[Z|R]):-X>1,Y is X-1,n(Y,R),R=[A,B|_],Z is 34*A-B+2;X=1,Z=1,R=[0];Z=0.


They have the same length in bytes but the non-tail-recursive generates stack overflows past a certain point (on my computer, around 20500).

# Javascript ES6, 7775 71 chars

// 71 chars
f=n=>{for(q=t=w=0;n;++q)for(s=q*q;t<=s;t+=++w)s==t&&--n&console.log(s)}

// No multiplication, 75 chars
f=n=>{for(s=t=w=0,q=-1;n;s+=q+=2)for(;t<=s;t+=++w)s==t&&--n&console.log(s)}

// Old, 77 chars
f=n=>{for(s=t=w=0,q=-1;n;s+=q+=2){for(;t<s;t+=++w);s==t&&--n&console.log(s)}}

• The solution is linear.
• The solution can output all numbers less then 2^53 because of numbers type.
• The algorithm itself can be used for unlimited numbers.

Test:

f(11)

0
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796


# C, 68 bytes

This was a fun challenge with C

main(o,k){o==1?k=0:0;k<9e9&&k>=0&&main(34*o-k+2,o,printf("%d,",k));}

Watch it run here: https://ideone.com/0ulGmM

# APL(NARS), 67 chars, 134 bytes

r←f w;c;i;m
c←0⋄i←¯1⋄r←⍬
→2×⍳0≠1∣√1+8×m←i×i+←1⋄r←r,m⋄→2×⍳w>c+←1


test:

  f 10
0 1 36 1225 41616 1413721 48024900 1631432881 55420693056 1882672131025


f would search in quadratic sequence the elements that are triangulars number too, so they have to follow the triangular check formula in APLs: 0=1∣√1+8×m with number m to check.

# Husk, 14 20 - 8 = 12 bytes

→!¡otS:o+2§-←o*34→ḋ2


Try it online!

Uses the same recurrence relation as the CJam answer. There's probably a better way to do this.

# Husk, 8 - 4 = 4 bytes

!Θf£∫Nİ□


Try it online!

it can theoretically output square triangular numbers of any size, but list intersection causes a stack overflow for anything above 3.

Instead of n uses f£, which is optimized for infinite lists.

Getting numbers takes a long, long, long time after 4.

• The second program doesn't work even in theory. You need f£ in place of n to handle infinite lists. Oct 7 '20 at 9:54
• I'll note that down. Thanks! @Zgarb Oct 7 '20 at 9:59

### x86_64 machine code - 46 bytes

Borrowed code from Albert Renshaw C answer.

47 bytes using ret instruction.

0000000000400080 <triangular_square>:
400080:   48 31 d2                xor    rdx,rdx      # rdx = 0
400083:   6a 00                   push   0x0
400085:   41 58                   pop    r8           # r8 = 0
400087:   48 ff c3                inc    rbx          # rbx = 1
40008a:   49 89 d8                mov    r8,rbx       # copy rbx value to r8

000000000040008d <triangular_square.loop>:
40008d:   e3 1f                   jrcxz  4000ae <triangular_square.done>  # if rcx is zero go to .done
40008f:   4d 6b c0 22             imul   r8,r8,0x22   # r8 * 0x22 (34)
400093:   49 29 d0                sub    r8,rdx       # r8 - rdx
400096:   49 83 c0 02             add    r8,0x2       # r8 + 2
40009a:   4d 89 c1                mov    r9,r8        # copy r8 value to r9
40009d:   48 ff c2                inc    rdx          # rdx + 1
4000a0:   48 ff ca                dec    rdx          # rdx - 1
4000a3:   48 87 da                xchg   rdx,rbx      # swap rbx value with rdx value
4000a6:   4c 89 cb                mov    rbx,r9       # copy r9 value to rbx
4000a9:   4c 89 c0                mov    rax,r8       # copy r8 value to rax (output)
4000ac:   e2 df                   loop   40008d <triangular_square.loop>  # keep looping until rcx is zero

00000000004000ae <triangular_square.done>:


Input in rcx output in rax. You can use debugger to test it.

TODO: Make a tester program on TIO.