# Sum of Squares without multiplication

I want to sum the squares for a given number N from 1 without using Multiplication. Is it possible?

-
Please check the documentation properly.Try n = 10;Sum[i^2, {i, 1, n}] or Total@Table[i^2, {i, 1, n}]. – PlatoManiac Sep 5 '12 at 9:38
n = 10; Sum[ Sum[j, {j, i}], {i, n}] – Rolf Mertig Sep 5 '12 at 9:53
Or a nested For loop.. – PlatoManiac Sep 5 '12 at 9:57
HINT: $$\begin{array}{ccccc} \blacksquare & {\color{red}\blacksquare} & {\color{green}\blacksquare} & {\color{purple}\blacksquare}\\ {\color{red}\blacksquare} & {\color{red}\blacksquare} & {\color{green}\blacksquare} & {\color{purple}\blacksquare}\\ {\color{green}\blacksquare} & {\color{green}\blacksquare} & {\color{green}\blacksquare} & {\color{purple}\blacksquare}\\ {\color{purple}\blacksquare} & {\color{purple}\blacksquare} & {\color{purple}\blacksquare} & {\color{purple}\blacksquare} \end{array}$$ – J. M. Sep 5 '12 at 10:31
@DavidCarraher sure. I was too quick. n = 10; Sum[Sum[i, {i}], {i, n}] is what I meant. BTW: doing Sum[Sum[i, {i}], {i, m}] gives (1/6)*(-1 + m)*m*(1 + m), while Sum[i^2, {i, m}] gives the correct (1/6)*m*(1 + m)*(1 + 2*m). Not sure if this is a bug or just stretching Sum too much ... – Rolf Mertig Sep 5 '12 at 18:29
show 1 more comment

Figuring out what the following snippet does is left as an exercise for the reader:

With[{n = 9},
s = t = 0; j = 1;
Do[
t += j; s += t; j += 2,
{n}]; s
]

-
I feel like browsing the wrong site ... – belisarius Sep 5 '12 at 11:50

A Mathematica minded answer:

HarmonicNumber[n, -2]


So:

Simplify[Sum[i^2, {i, n}] == HarmonicNumber[n, -2]]
(* True *)

-
Out of curiosity, how is HarmonicNumber implemented internally? You appear to presume its implementation does not involve multiplication. It's hard to see how that would be. – whuber Sep 5 '12 at 19:41
@whuber I doubt any Mma code is completely exempt from multiplications if you go down till machine code! Someone has to do pointer arithmetic ... – belisarius Sep 5 '12 at 20:20
A lot of pointer arithmetic is done by adding. It is plausible that either at the p-code level or the machine level, many of the solutions offered here use no multiplication (nor anything even more complicated, like exponentiation). That's not so plausible for Harmonic number calculations :-). – whuber Sep 5 '12 at 21:39
@whuber You misunderstood me. There is no way to prevent multiplication. "Modern" machine addressing modes involve base + (index * scale) + displacement at the hardware level. See for example staff.ustc.edu.cn/~xlanchen/cailiao/… or any reference to the lea instruction in assembly – belisarius Sep 5 '12 at 23:13
@whuber: from what I've seen internally, HarmonicNumber is converted to PolyGamma[]; numerically evaluating that would definitely require not a few multiplications. – J. M. Sep 6 '12 at 0:23
show 1 more comment

Someone certainly had to write this recursive one:

Clear[f]
f[x_Integer, y_Integer] := x + f[x, y - 1]
f[x_Integer, 0] := 0
f[x_Integer] := f[x, x] + f[x - 1]
f[0] := 0

-
 +1 This is in the spirit of the modern foundations of arithmetic. – whuber Sep 5 '12 at 19:41

Try this :

s[n_] := Total[ Range[n]^2]


to check how it works, e.g. :

s[5] // Trace


There is also a purely symbolic approach, e.g. : $\quad n^2$ ~ Sum ~$n\quad$ (see Infix notation) :

(n^2) ~ Sum ~ n

1/6 (-1 + n) n (-1 + 2 n)


Note : Sum[ n^2, n] returns the same as Sum[ i^2, {i, n-1}] does, i.e. indefinite sums starts at 0 while definite ones at 1, e.g. :

Table[ Sum[ n^2,     n ], {n, 5}]
Table[ Sum[ k^2, {k, n}], {n, 5}]

{0, 1, 5, 14, 30}
{1, 5, 14, 30, 55}


Test

We added Verde's approach (HarmonicNumber) for comparison.

st = {  Sum[i^2, {i, 10^6}]           // AbsoluteTiming,
s[10^6]                       // AbsoluteTiming,
(Sum[n^2, n] /. n -> 10^6 + 1) // AbsoluteTiming,
HarmonicNumber[ 10^6, -2]     // AbsoluteTiming  };

Last @ First @ st
Equal @@ Last /@ st

333333833333500000
True

First /@ st

{1.4570000, 1.0540000, 0., 0.}


Conclusion

Symbolic computations are especially recommended

-

Yes, it is possible.

Since multiplication of positive integers is repeated addition, we can repeatedly add instead of multiply:

n = 10;
sum = 0;
Do[
Do[
sum = sum + i,
{j, 1, i}],
{i, 1, n}];
Print[sum]

-

An oddball one using a recursive, memoizing function for the square.

Clear[sq];
sq[n_Integer] := sq[n] = sq[n - 1] + n + (n - 1)
sq[1] = 1;

Sum[sq[n], {n, 6}]


91

It's not something I would directly use for such a goal, but you asked for something without explicit multiplications and you got it.

Alternatively, if we don't interpret Dot as some kind of multiplication then

#.# &@Range[6]


would fit the requirements too.

-
Total@Flatten[ConstantArray[#, #] & /@ Range[9]]


I think this exercise is somewhat of a Rorschach test… I don't know what the above says about me, though :)

-
What do you think? – belisarius Sep 5 '12 at 17:53
@Verde what is this, self-Rorschach? I don't think that works… “I think it says I'm handsome” – F'x Sep 5 '12 at 18:09

I'll join the bandwagon with SparseArray:

sq[n_Integer] := Tr@SparseArray[{{i_, i_} :> i^2}, n]

-
Squaring involves multiplication, doesn't it? Tsk, tsk :-). – whuber Sep 5 '12 at 19:39
@whuber sshhh... it was supposed to be hidden :D Ok, you could do {i_, i_} :> f[i, i], where f is from my other answer :) – rm -rf Sep 5 '12 at 19:47
Original +1 but slow sq[10^6]; // AbsoluteTiming yields {2.1980000, Null}. – Artes Sep 5 '12 at 20:04
@Artes Heh, of course it is slow! I thought people were generally just having fun here :) No one would really sum squares using Tr@SparseArray... (at least, I hope they don't and this isn't used in any decent code :P) – rm -rf Sep 5 '12 at 20:42

w = 10;
E^(Log[1/6] + Log[w] + Log[1 + w] + Log[1 + w + w])


385

Explanation

ClearAll[w]
Sum[i^2, {i, 1, w}]


1/6 w (1 + w) (1 + 2 w)

-

A Wolfram Alpha minded answer:

WolframAlpha["find the sequence 1,5,14,30,55"]

-

You can sum the diagonal. However, that might be slowest procedure of all.

-
How about Tr[t], assuming your table is t? That's what R.M. did. – David Carraher Sep 5 '12 at 19:18
@DavidCarraher, this is for others like me: When I look at the figures, I can feel the wheels turning. When I read the math, I find out the hamsters are dead. – Fred Kline Sep 5 '12 at 21:21
Don't give up. My hamsters died a long time ago. – David Carraher Sep 5 '12 at 23:04