11
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – rodolphito Jun 25 '15 at 1:38
  • \$\begingroup\$ @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? \$\endgroup\$ – xnor Jun 25 '15 at 1:41
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – xnor Jun 25 '15 at 1:51
  • 1
    \$\begingroup\$ love to see something like that tagged in fastest-code \$\endgroup\$ – Abr001am Jun 25 '15 at 2:52
  • 2
    \$\begingroup\$ "The first 10 square triangular numbers..." Surely you meant 11? :P \$\endgroup\$ – Alex A. Jun 25 '15 at 14:39

17 Answers 17

8
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – rodolphito Jun 25 '15 at 2:10
  • \$\begingroup\$ @Rodolvertice: I've switched to an iterative approach. It's actually shorter and it's less memory intensive. \$\endgroup\$ – Dennis Jun 25 '15 at 3:11
8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ That is quite cheaty, a 'loop' by string multiplication, haha. \$\endgroup\$ – rodolphito Jun 25 '15 at 1:17
  • \$\begingroup\$ @Rodolvertice: Not cheaty at all really. Rather clever, and indeed fairly common on the site. \$\endgroup\$ – Alex A. Jun 25 '15 at 14:26
  • \$\begingroup\$ 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). \$\endgroup\$ – Kade Jun 25 '15 at 16:18
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Jun 25 '15 at 5:17
  • \$\begingroup\$ @xnor: I think he already does that. However, the result returned by the loop is your b. \$\endgroup\$ – Dennis Jun 25 '15 at 5:43
5
\$\begingroup\$

Oasis, 7 - 4 - 4 = -1 (Non-competing)

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.

Non-competing because language postdates challenge.

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)

\$\endgroup\$
  • \$\begingroup\$ The question says For n=1 return 0, but this returns 1. This is fixable by adding the -O option. \$\endgroup\$ – Grimy May 13 at 15:15
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I don't think this qualifies for the bonus. f(15) should return 85170343853180456676, not 85170343853180450000. \$\endgroup\$ – Dennis Jun 25 '15 at 5:15
  • \$\begingroup\$ @Dennis JavaScript must be truncating it. .-. Yup, JavaScript rounds to 16 digits when \$\endgroup\$ – Downgoat Jun 25 '15 at 5:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Ismael Miguel Jun 25 '15 at 9:08
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Ismael Miguel Jun 25 '15 at 9:26
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Ismael Miguel Jun 25 '15 at 9:30
3
\$\begingroup\$

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:

output

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

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

[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

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

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

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

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.

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

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

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

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

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

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

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

Perl 6, 25 - 8 = 17 bytes

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

Try it online!

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

05AB1E, 10 - 8 = 2 bytes

1ÎGDŠ34*Ìα

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

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