Tell me more ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.
up vote 3 down vote favorite

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

share|improve this question
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
2  
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
8  
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

11 Answers

up vote 5 down vote

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
 ]
share|improve this answer
5  
I feel like browsing the wrong site ... – belisarius Sep 5 '12 at 11:50
up vote 5 down vote

A Mathematica minded answer:

HarmonicNumber[n, -2]

So:

Simplify[Sum[i^2, {i, n}] == HarmonicNumber[n, -2]]
(* True *)
share|improve this answer
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
1  
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
up vote 5 down vote

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
share|improve this answer
+1 This is in the spirit of the modern foundations of arithmetic. – whuber Sep 5 '12 at 19:41
up vote 5 down vote

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

share|improve this answer
up vote 4 down vote

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]
share|improve this answer
up vote 4 down vote

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.

share|improve this answer
up vote 4 down vote 
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 :)

share|improve this answer
What do you think? – belisarius Sep 5 '12 at 17:53
1  
@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
2  
up vote 3 down vote

I'll join the bandwagon with SparseArray:

sq[n_Integer] := Tr@SparseArray[{{i_, i_} :> i^2}, n]
share|improve this answer
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
1  
@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
up vote 2 down vote

If exponentiation is allowed, how about this?

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)

share|improve this answer
up vote 2 down vote

A Wolfram Alpha minded answer:

WolframAlpha["find the sequence 1,5,14,30,55"]
share|improve this answer
up vote 1 down vote

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

share|improve this answer
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
3  
Don't give up. My hamsters died a long time ago. – David Carraher Sep 5 '12 at 23:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.