Triangular Square Numbers

Question

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.

Answer 1

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.
           Y+    e#   Add 2.
               ; e# Discard the last result.

Answer 2

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

Answer 3

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.

Try it here online.

Answer 4

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)

Answer 5

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

Answer 6

Excel VBA - 90 bytes

Using the recurrence relation from the Wikipedia page:

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.

Answer 7

[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 A_n = (A_n-1-1)²/A_n-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

Answer 8

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;}

Answer 9

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)

Answer 10

PHP, 65 59 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.

Answer 11

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.

Answer 12

Perl 6, 25 - 8 = 17 bytes

{(0,1,2-*+34* *…*)[$_]}

Try it online!

Answer 13

05AB1E, 10 - 8 = 2 bytes

1ÎGDŠ34*Ìα

Try it online!

Answer 14

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!

Answer 15

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

Answer 16

Javascript ES6, 77 75 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

Answer 17

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

Answer 18

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.

Answer 19

Husk, ¹⁴ 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.

Answer 20

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.