Calculate all the squares up to x using only addition and subtraction

Question

The goal is to calculate all the squares up to x with addition and subtraction.

Rules:

1. The code must be a function which takes the total number of squares to generate, and returns an array containing all those squares.
2. You can not use strings, structures, multiplication, division, or built-in functions for calculating squares.
3. You can only use arrays, integers (whole numbers), addition, subtraction. No other operators allowed!

This is a code-golf question, so the shortest code in bytes wins!

Answer 1

APL - 10

{+\1++⍨⍳⍵}

Example usage:

{+\1++⍨⍳⍵}10
1 4 9 16 25 36 49 64 81 100

ngn APL demo

Answer 2

C, 55 52 bytes

int s(int n,int*r){for(int i=0,j=-1;n--;*r++=i+=j+=2);}

simply sums odd numbers

• n: number of squares to compute
• r: output array for storing the results
• j: takes the successive values 1, 3, 5, 7, ...
• i: is incremented by j on each iteration

Edit

4 chars can be saved using the implicit int declaration (>C99), but this costs 1 char because for initializers cannot contain a declaration in >C99. Then the code becomes

s(int n,int*r){int i=0,j=-1;for(;n--;*r++=i+=j+=2);}

Usage

void main() {
    int r[20];
    s(20, r);
    for (int i = 0; i < 20 ; ++i) printf("%d\n", r[i]);
}  

Output

1
4
9
16
25
36
49
(...)
361
400

Answer 3

GolfScript, 17 characters

{[,{.+(1$+}*]}:F;

Usage (see also examples online):

10 F     # => [0 1 4 9 16 25 36 49 64 81]

Note: * is a loop and not the multiplication operator.

Answer 4

Windows Batch, 115 bytes

setlocal enabledelayedexpansion&for /l %%i in (1 1 %1)do (set a=&for /l %%j in (1 1 %%i)do set /a a+=%%i
echo.!a!)

This should be placed in a batch file instead of being run from cmd, and it outputs the list to the console. It takes the number of squares to create from the first command-line argument. For the most part it uses & instead of newlines, one is still needed however and it counts as two bytes.

It needs delayed variable expansion enabled, this can be done with cmd /v:on. Assuming it's not, an extra setlocal enabledelayedexpansion& was needed at the start (without it the script is 83 bytes).

Answer 5

JavaScript - 32 Characters

for(a=[k=i=0];i<x;)a[i]=k+=i+++i

Assumes a variable x exists and creates an array a of squares for values 1..x.

ECMAScript 6 - 27 Characters

b=[f=i=>b[i]=i&&i+--i+f(i)]

Calling f(x) will populate the array b with the squares for values 0..x.

Answer 6

Haskell - 30

f n=scanl1(\x y->x+y+y-1)[1..n]

This uses the fact that (n+1)^2=n^2+2n+1

Answer 7

Julia - 33

Any square number can be written by a summation of odd numbers:

julia> f(x,s=0)=[s+=i for i=1:2:(x+x-1)];f(5)
5-element Array{Int64,1}:
  1
  4
  9
 16
 25

Answer 8

Perl, 27 bytes

sub{map{$a+=$_+$_-1}1..pop}

Math:

$$ \text{square}\left(n\right) = \begin{cases} 0 & \text{for } n = 0 \\ \text{square}\left(n - 1\right) + n + n - 1 & \text{for } n > 0 \end{cases} $$ $$ \text{square}\left(n\right) - \text{square}\left(n - 1\right) = n^2 - \left(n - 1\right)^2 = 2n - 1 $$

Script for calling the function to print 10 squares:

#!/usr/bin/env perl
$square = sub{map{$a+=$_+$_-1}1..pop};
use Data::Dumper;
@result = &$square(10);
print Dumper \@result;

Result:

$VAR1 = [
          1,
          4,
          9,
          16,
          25,
          36,
          49,
          64,
          81,
          100
        ];

Edits:

• Anonymous function (−2 bytes, thanks skibrianski)
• pop instead of shift (−2 bytes, thanks skibiranski)

Answer 9

C++ 99 81 78 80 78

int* f(int x){int a[x],i=1;a[0]=1;while(i<x)a[i++]=a[--i]+(++i)+i+1;return a;}  

my first try in code-golf

this code is based on
a = 2 x n - 1
where n is term count and a is n th term in the following series
1, 3, 5, 9, 11, 13, .....
sum of first 2 terms = 2 squared

sum of first 3 terms = 3 squared
and so on...

Answer 10

DCPU-16 Assembly (90 bytes)

I wrote this in assembly for a fictional processor, because why not?

:l
ADD I,1
SET B,0
SET J,0
:m
ADD J,1
ADD B,I
IFL J,I
SET PC,m
SET PUSH,B
IFL I,X
SET PC,l

The number is expected to be in the X register, and other registers are expected to be 0. Results are pushed to the stack, it will break once it reaches 65535 due to the 16 bit architecture. You may want to add a SUB PC, 1 to the end to test it. Compiled, the program should be 20 bytes (10 words).

Answer 11

Haskell

f x=take x [iterate (+y) 0 !! y | y<- [0..]]

This basically invents multiplication, uses it own itself, and maps it over all numbers. f 10 = [0,1,4,9,16,25,36,49,64,81]. Also f 91 = [0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936,2025,2116,2209,2304,2401,2500,2601,2704,2809,2916,3025,3136,3249,3364,3481,3600,3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,5041,5184,5329,5476,5625,5776,5929,6084,6241,6400,6561,6724,6889,7056,7225,7396,7569,7744,7921,8100].

Answer 12

Haskell, 34 / 23

n#m=m+n:(n+2)#(m+n)
f n=take n$1#0

or, if imports are okay:

f n=scanl1(+)[1,3..n+n]

Output:

λ> f 8
[1,4,9,16,25,36,49,64]

Answer 13

Jelly, 4 bytes

+)’Ä

Try it online!

How it works

+)’Ä - Main link. Takes x on the left
 )   - For each integer 1 ≤ i ≤ x:
+    -   Yield i+i = 2i
  ’  - Decrement each
   Ä - Calculate the cumulative sum

Answer 14

Javascript 47

function f(n,a){return a[n]=n?f(n-1,a)+n+n-1:0}

r=[];f(12,r);console.log(r) returns :
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144]

Answer 15

Smalltalk, 52

f:=[:n||s|(s:=1)to:n collect:[:i|x:=s.s:=s+i+i+1.x]]

Returns a new array (i.e. does not fill or add to an existing one).

call:

f value:10

-> #(1 4 9 16 25 36 49 64 81 100)

Answer 16

python - 39

a=0
for i in range(5):a+=i+i+1;print(a)

Replace 5 with any value. Any suggestions?

Answer 17

Bash - 92 85 62 61 59 57

declare -i k=1;for((i=0;i++<$1;k+=i+i+1));do echo $k;done

Result:

$ ./squares.sh 10
1
4
9
16
25
36
49
64
81
100

Edit: I replaced the inner loop with the algorithm from @mniip's Haskell solution.

Answer 18

Same method as above, in APL and J:

APL: F←{+\1+V+V←¯1+⍳⍵} (17 characters) works with most APL variants (try it here)

and even less (only 14 characters) with NGN APL: F←{+\1+V+V←⍳⍵} (see here)

J: f=:+/\@(>:@+:@:i.) (18 characters)

edit: better solution in APL: F←{+\¯1+V+V←⍳⍵} (15 characters)

Answer 19

C# (82)

int[] s(int n){int i,p=0;var r=new int[n];while(i<n){p+=i+i+1;r[i++]=p;}return r;}

Answer 20

C# - 93

int[]s(int l){int[]w=new int[l];while(l>=0){int i=0;while(i<l){w[l-1]+=l;i++;}l--;}return w;}

When called from another method of the same class, will return the array - [1,4,9,16,25,36...], up to lth element.

Answer 21

Fortran II|IV|66|77, 134 122 109 105

  SUBROUTINES(N,M)
  INTEGERM(N)
  K=0
  DO1I=1,N
  K=K+I+I-1
1 M(I)=K
  END

Edit: removed inner loop and used @mniip's Haskell algorithm instead.

Edit: Verified that the subroutine and driver are valid Fortran II and IV

Driver:

  INTEGER M(100)
  READ(5,3)N
  IF(N)5,5,1
1 IF(N-100)2,2,5
2 CALLS(N,M)
  WRITE(6,4)(M(I),I=1,N)
3 FORMAT(I3)
4 FORMAT(10I6)
  STOP  
5 STOP1
  END

Result:

$ echo 20 | ./a.out
   1     4     9    16    25    36    49    64    81   100
 121   144   169   196   225   256   289   324   361   400

Answer 22

Python - 51

Here I'm defining a function as requested by the rules.

Using sum of odd numbers:

f=lambda n:[sum(range(1,i+i+3,2))for i in range(n)]

This only uses sum (a builtin which performs addition) and range (a builtin which creates arrays using addition). If you object to sum, we can do this with reduce:

def g(n):v=[];reduce(lambda x,y:v.append(x) or x+y,range(1,i+i+3,2));return v

Answer 23

PHP, 92 bytes

This needs to have the "short tags" option enabled, of course (to shave off 3 bytes at the start).

<? $x=100;$a=1;$r=0;while($r<=$x){if($r){echo"$r ";}for($i=0,$r=0;$i<$a;$i++){$r+=$a;}$a++;}

Output:

1 4 9 16 25 36 49 64 81 100 

Answer 24

Forth - 48 bytes

: f 1+ 0 do i 0 i 0 do over + loop . drop loop ;

Usage:

7 f

Output:

0 1 4 9 16 25 36 49

Answer 25

Vyxal, 9 bytes

ɾ(n:+‹)W¦

Try it Online!

It could be just two bytes if everything is allowed

Answer 26

Pascal, 182 B

This is your standard odd number theorem. $$ n^2 = \sum_{i=1}^{n}\left(2i - 1\right) = \sum_{i=1}^{n}\left(i + i - 1\right) = \sum_{i=1}^{n}\left(i\right) + \sum_{i=1}^{n}\left(i\right) - \sum_{i=1}^{n}\left(1\right) $$

type Z=integer;L(n:Z)=array[1..n]of Z;P=^L;function Q(n:Z)=q:P;var i:Z;begin
new(q,n);q^[1]:=1;for i:=2 to n do q^[i]:=q^[i-1]+i;for i:=1 to n do begin
n:=q^[i];q^[i]:=n+n-i end end;

Disgolfed:

    type
        { This declares an Extended Pascal schema data type. }
        integerList(length: integer) = array[1‥length] of integer;
        { It is not possible to create new data types in routine signatures. }
        integerListReference = ↑integerList;
    
    { In Pascal functions cannot return variably‑sized values
      therefore a (constant‑sized) pointer is returned. }
    function squares(order: integer) = result: integerListReference;
        var
            { `For`‑loop counter variables must be _proper_ variables.
              It is not possible to re‑use `order` for that purpose. }
            i: integer;
        begin
            { Allocate memory and discriminate the schema data type.
              The value of `order` becomes the `length` of `integerList`. }
            new(result, order);
            { Dereference pointer and assign `1` to the first element. }
            result↑[1] ≔ 1;
            { In Pascal `for` loop limits are inclusive.
              `i` becomes `2`, `3`, …, `order − 2`, `order − 1`, and `order`.
              An empty range (that means 2 > order) is legal and
              just causes the `for`‑loop body to be never executed. }
            for i ≔ 2 to order do
            begin
                result↑[i] ≔ result↑[pred(i)] + i
            end;
            { In Pascal `for`‑loop limits are evaluate exactly once.
              Therefore a redefinition of `order` is harmless. }
            for i ≔ 1 to order do
            begin
                order ≔ result↑[i];
                result↑[i] ≔ order + order − i
            end
        end;

Note, Pascal has a built‑in square function named sqr. It returns an integer value for an integer argument, a real value for a real argument, and – in case of Extended Pascal (ISO 10206) – a complex number in case of a complex argument.