Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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
3  
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
11  
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

14 Answers 14

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
2  
+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

share|improve this answer

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
7  
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 *)
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
1  
@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
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  

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

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

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}}, # /.
     {{live, live} -> Sequence[{live, live}, {live, dead}, {live, dead}, {dead, dead}],
      {live, dead} -> Sequence[{live, dead}, {dead, dead}]}] &, {}, n]]

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]
share|improve this answer
    
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
1  
Heh, another silly one: With[{m = 10}, Flatten@ConstantArray[🍺, {m, 1 + m, 1 + m + m}] ~Partition~ 6 // Dimensions // First ] (looks best on a mac) –  rm -rf May 27 '13 at 0:35
    
@rm-rf Yeah, 🍻, right back at you, buddy! –  Michael E2 May 27 '13 at 4:43

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

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

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
1  
@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

A Wolfram Alpha minded answer:

WolframAlpha["find the sequence 1,5,14,30,55"]
share|improve this answer
sos[n_Integer] := Total[Total[Range[1, #, 2]] & /@ (2 Range[n])]
share|improve this answer
2  
No need to call Total[] twice: Total[Range[1, #, 2] & /@ (2 Range[n]), 2] –  J. M. 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}
share|improve this answer

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.