# 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}$$ –  Guess who it is. 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

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 belisarius'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

-

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

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. –  Guess who it is. Sep 6 '12 at 0:23
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

Yes, it is possible.

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.

-

# Ten ways to beat a dead horse

Sunday afternoon on an airplane without wifi and this was the problem I remembered reading at breakfast. Forgive me for the time I had on my hands. All because @Aky resurrected this dead horse. (Thanks by the way. I'm glad to have figured out the CellularAutomaton one, but we landed before I could come up with a good MapAll application.)

No speed demons here, but I assiduously avoided Times, sometimes Plus, too (notwithstanding objections that internally some arithmetic has to be occurring).

Simple:

ss1[n_] := Range[n] + Range[n] - 1 // Accumulate // Total

ss2[n_] := Total[# ~Table~ {#} & /@ Range[n], 2]


CellularAutomaton

ss3[n_] :=
Total[CellularAutomaton[
{62, {2, {{{0, 0, 0}, {1, 1, 0}, {0, 0, 0}},
{{0, 1, 0}, {1, 1, 0}, {0, 0, 0}},
{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}}}, {1, 1, 1}},
SparseArray[{{1, 1, 1} -> 1}, {n, n, n}], {{{n - 1}}}], 3]


Rules:

Clear[live, dead];
ss4[n_] := Length[Nest[Join[{{live, live}}, # /.


My own SparseArray version:

ss5[n_] := SparseArray[{{i_, j_, k_} /; i <= k && j <= k -> 1},
{n, n, n}]["NonzeroPositions"] // Length


Why not LeafCount?

ss6[n_] := Flatten[Table[FoldList[{#2, #1} &, 0, Range @ i], {i, n - 1}], 1] // LeafCount


Functional to illiterate -- I mean, illegible:

ss7[n_] := Total[{{#, #} &[Range /@ #], {{-#}}} & @ Range[n], 4]

ss8[n_] := NestList[Most, #, Length@#] & @ NestList[{0, 0, #1} &, 0, n - 1] //
Flatten // Length

ss9[n_] := Fold[{#1} /. {0} -> #2 &, 0, #] & @
FoldList[{#1} /. 0 -> #2 &, 0, NestList[{{#}} &, 0, n - 1]] /. {0} -> 0 // Depth

ss10[n_] := (x \[Function] #) /@ # & /@ (r \[Function] r[[1 ;; #]] & /@ r) @ Range @ n //
Flatten // Length


Postscript

Got a MapAll one:

ssPS[n_] := Total @ Cases[
MapAll[{Depth[#], #} &, #] & /@ NestList[{#} &, x, n - 1], _Integer, Infinity]

-
Actually, the thread was at the top of the list of questions and (failing to notice the date) I assumed it was a new question that had received a flurry of replies. I suppose now that was because someone had edited it. +1 for the variety. –  Aky May 26 '13 at 23:51
@Aky Yeah, I didn't notice the date either. And I didn't notice someone had edited it. +1 to you, too. –  Michael E2 May 26 '13 at 23:53
I would also like to assure all readers that no horses were harmed during the writing of these answers. –  Aky May 26 '13 at 23:55
Heh, another silly one: With[{m = 10}, Flatten@ConstantArray[🍺, {m, 1 + m, 1 + m + m}] ~Partition~ 6 // Dimensions // First ] (looks best on a mac) –  The Toad May 27 '13 at 0:35
@rm-rf Yeah, 🍻, right back at you, buddy! –  Michael E2 May 27 '13 at 4:43

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)

-

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 :) –  The Toad 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) –  The Toad Sep 5 '12 at 20:42

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

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

-
sos[n_Integer] := Total[Total[Range[1, #, 2]] & /@ (2 Range[n])]

-
No need to call Total[] twice: Total[Range[1, #, 2] & /@ (2 Range[n]), 2] –  Guess who it is. May 26 '13 at 13:55
@J.M. Thank you. –  Aky May 26 '13 at 14:03

Late to the party!

f[n_]:=Total[Accumulate[Range[1, n + n, 2]]]


So for instance the first seven are

f/@Range[7]

{1, 5, 14, 30, 55, 91, 140}

-