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!

• Peter Taylor: This is essentially Most optimized algorithm for incrementing squares - or, at least, will get pretty much identical answers.
• Toothbrush: @PeterTaylor No, it's not the same, as that's for the most optimised algorithm for incrementing squares, but my question asks for only addition and subtraction.
• Peter Taylor: Which is the same thing. As witness: the present answer to this question does exactly the same as the vast majority of answers to the previous question.
• Toothbrush: @PeterTaylor I might be biased, but I really don't think it's at all the same.
• Blacklight Shining: This question may already have answers elsewhere, but that does not make the question a duplicate of the other question.

Answer 1

APL - 10

{+1円++⍨⍳⍵}

Example usage:

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

ngn APL demo

• Adám: Save three bytes: +1円+⍳+⍳

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

• Mukul Kumar: that logic is Excellent! you deserve +1

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.

• Toothbrush: OK; how does it work?
• Howard: @toothbrush , takes the input and converts it to the array [0 1 ... n-1]. Then * injects the given code-block into the array. This block first doubles the current item (.+) subtracts one (() and then adds the previous result 1$+ (in other words, add 2j-1 to the previous square number). [] encloses everything in order to return a new array.
• Toothbrush: Great! I don't know GolfScript, so I wondered how it worked.

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.

• Eliseo D'Annunzio: I have to ask... the i+++i at the end...?
• MT0: k+=i+++i is the same as k += i + (++i) which is the same as k+=i+i+1 followed by i=i+1
• Eliseo D'Annunzio: Oh that is genius... I've gotta implement that in my next codegolf if needed! :)
• Toothbrush: You can save one character by moving the function declaration to inside the array (e.g. b=[f=i=>b[i]=i&&i+--i+f(i)]).
• MT0: Thanks - saved one character on the top answer too by moving things round to remove a semi-colon.

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

• Jonathan Van Matre: Hi, and welcome to CG.se! Nice, succinct answer. Never heard of Julia, but it looks intriguing.
• Glenn Randers-Pehrson: Isn't "2x" a multiplication in Julia? You could say x+x instead, which will cost you just one byte.
• CCP: You are right (didnt notice), edited.
• Glenn Randers-Pehrson: I'm not familiar (yet) with julia, but looked it up in the online manual at docs.julialang.org/en/release-0.2 and found "Numeric Literal Coefficients: To make common numeric formulas and expressions clearer, Julia allows variables to be immediately preceded by a numeric literal, implying multiplication." So yeah, 2x is a multiplication.

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)

• skibrianski: I see no reason why you need to name your sub. IOW "sub{map{$a+=$_+$_-1}1..shift}" seems legit to me, and saves you two chars.
• Heiko Oberdiek: @skibrianski: An anonymous function is also a function. The downside is that the calling of the function is a little more cumbersome.
• skibrianski: Right, but that's on the caller. There are entries in other languages that define anonymous subs, so I think you're safe =)
• skibrianski: And you can save another 2 chars by using pop() instead of shift() since there's only one argument.

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

• user12205: I think you can remove the braces {} after the for loop, since there is only one statement. This can reduce your char count by 2
• Mukul Kumar: If you declare arrays of non-constant size in some function other than main() then it's acceptable
• Kerrek SB: This code has undefined behaviour.
• V-X: and returns pointer to data on stack destroyed during the return.
• mniip: @MukulKumar addition, subtraction, I'm only using those

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

python - 39

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

Replace 5 with any value. Any suggestions?

Answer 12

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

• Glenn Randers-Pehrson: Can you extend the demo to a little larger than 10?

Answer 13

Haskell, 34 / 23

n#m=m+n:(n+2)#(m+n)
f n=take n1ドル#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 14

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 15

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]

• Toothbrush: Great! In EcmaScript 6: f=(n,a)=>a[n]=n?f(n-1,a)+n+n-1:0.
• Claudia: I really can't wait for ECMAScript 6 to really enter mainstream use. That would be the perfect excuse to learn it.
• MT0: The Arrow Function part of the ECMAScript 6 specification has been in FireFox since version 22.

Answer 16

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

• user12205: did you try removing the spaces between int[] and sq? I don't know C#, but I think it should work.
• Rajesh: No, that wont work. First int[] is the return type of method "sq". I can reduce the method name to may be just "s" :)
• user12205: I mean using int[]sq instead of int[] sq and int[]res instead of int[] res. This helps you save two chars, and I didn't get any compilation errors with that. Also you should use single character identifiers for sq and res as you suggested.
• user12205: seems like there's something wrong with your answer
• luser droog: Indent code with 4 spaces to put it in a code-block with monospace font.

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

Japt -m, 6 bytes

T±U+UÄ

Try it

T±U+UÄ :Implicit map of each U in the range [0,input)
T± :Increment T (initially 0) by
 U+UÄ : U+U+1

• noodle person: 5 bytes T±UÑÄ
• Shaggy: Addition & subtraction only, @noodleperson.
• noodle person: Ah, my mistake.

Answer 27

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.

Answer 28

awk

A completely hands-free approach in awk

jot 50 | awk '2ドル = __ += _ + ++_' 

1 1 11 121 21 441 31 961 41 1681
2 4 12 144 22 484 32 1024 42 1764
3 9 13 169 23 529 33 1089 43 1849
4 16 14 196 24 576 34 1156 44 1936
5 25 15 225 25 625 35 1225 45 2025
6 36 16 256 26 676 36 1296 46 2116
7 49 17 289 27 729 37 1369 47 2209
8 64 18 324 28 784 38 1444 48 2304
9 81 19 361 29 841 39 1521 49 2401
10 100 20 400 30 900 40 1600 50 2500