-4

A perfect square is a number that is the square of an integer.

However, let's define something called a Magical Square, which is a perfect square with the following restriction:

The perfect square must be the sum of the numbers 1...N for some natural number N. Write a program that calculates the first X magical squares:

The first magical square is 1 (not 0, since N >= 1). The values of X are: 1 <= X <= 15. The program should be efficient and your score is the time taken to calculate the magical squares in seconds. The winner is the program that runs in the least amount of time. Please also include the generated numbers.

You can't hard-code the values, or read them from a file, etc. They MUST be calculated by the program.

Some examples: 1, 36, 1225, ...

mmk

Posted 2014-11-23T02:52:15.293

Reputation: 253

How are you going to select the winner? 2. Why constant output? Wouldn't this be more interesting if the code had X as input?

< – Dennis – 2014-11-23T02:55:29.033

4So isn't this just numbers that are perfect squares AND triangular numbers? – mdc32 – 2014-11-23T02:56:38.873

@mdc32, yes it is. – mmk – 2014-11-23T02:58:38.870

So, essentially, if sqrt(x*(x-1)) is a whole number, then print it. – mdc32 – 2014-11-23T03:11:10.483

"The winner is the program that runs in the least amount of time." As measured on which machine? Unless they're all measured on the same machine (which usually means yours) this is not an objective winning criterion. – Martin Ender – 2014-11-23T10:18:47.983

@MartinBüttner, I'll time it on my machine as well. – mmk – 2014-11-23T14:26:02.153

Are we allowed to use floating point numbers? – TheNumberOne – 2014-11-23T16:42:47.197

Answers

CJam, 1 ms

UXD{_34*2$m2+}*]1>N*

This uses the following known recurrence relation:

N[k] = 34 * N[k-1] - N[k-2] + 2

Timing/Output

$ cjam <(echo 'es:T; UXD{_34*2$m2+}*]1>N* esT-`p'); echo
"1"
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796
2172602007770041
73804512832419600
2507180834294496361
85170343853180456676

Dennis

Posted 2014-11-23T02:52:15.293

Reputation: 196 637

You forgot the 15th number. – TheNumberOne – 2014-11-23T13:29:15.663

Fixed, thanks. I changed the starting values, but not the number of iterations. – Dennis – 2014-11-23T13:34:49.243

Java 7, 467945 ns = .467945 ms

Using sudo's formula:

import java.math.BigInteger;
import java.io.*;

public class SquareTriangle{
    public static void main(String[] args){
        PrintStream out = new PrintStream(System.out, false);
        long startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++){
            BigInteger a = 0;
            BigInteger b = 1;
            BigInteger c;
            for (int i = 0; i < 15; i++){
                out.println(b);
                c = b;
                b =  c.multiply(BigInteger.valueOf(34)).subtract(a)
                         .add(BigInteger.valueOf(2));
                a = c;
            }
        }
        long endTime = System.nanoTime();
        out.flush();
        System.out.println((endTime - startTime)/100000 + " ns");
    }
}

Takes an average of 467945 ns per run on my very slow computer.

Here are the numbers:

1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796
2172602007770041
73804512832419600
2507180834294496361
85170343853180456676
2893284510173841030625

Edit: Now flushes the output stream after it is timed, not during.

TheNumberOne

Posted 2014-11-23T02:52:15.293

Reputation: 10 855

Magical Squares

Answers

CJam, 1 ms

Timing/Output

Java 7, 467945 ns = .467945 ms