5
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Please check the documentation properly.Try n = 10;Sum[i^2, {i, 1, n}] or Total@Table[i^2, {i, 1, n}]. $\endgroup$ Sep 5, 2012 at 9:38
  • 3
    $\begingroup$ n = 10; Sum[ Sum[j, {j, i}], {i, n}] $\endgroup$ Sep 5, 2012 at 9:53
  • $\begingroup$ Or a nested For loop.. $\endgroup$ Sep 5, 2012 at 9:57
  • 11
    $\begingroup$ 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}$$ $\endgroup$ Sep 5, 2012 at 10:31
  • $\begingroup$ @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 ... $\endgroup$ Sep 5, 2012 at 18:29

14 Answers 14

9
$\begingroup$

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
$\endgroup$
1
  • 2
    $\begingroup$ +1 This is in the spirit of the modern foundations of arithmetic. $\endgroup$
    – whuber
    Sep 5, 2012 at 19:41
8
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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
 ]
$\endgroup$
1
  • 7
    $\begingroup$ I feel like browsing the wrong site ... $\endgroup$ Sep 5, 2012 at 11:50
7
$\begingroup$

A Mathematica minded answer:

HarmonicNumber[n, -2]

So:

Simplify[Sum[i^2, {i, n}] == HarmonicNumber[n, -2]]
(* True *)
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Sep 5, 2012 at 19:41
  • $\begingroup$ @whuber I doubt any Mma code is completely exempt from multiplications if you go down till machine code! Someone has to do pointer arithmetic ... $\endgroup$ Sep 5, 2012 at 20:20
  • 1
    $\begingroup$ 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 :-). $\endgroup$
    – whuber
    Sep 5, 2012 at 21:39
  • 1
    $\begingroup$ @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 $\endgroup$ Sep 5, 2012 at 23:13
  • $\begingroup$ @whuber: from what I've seen internally, HarmonicNumber is converted to PolyGamma[]; numerically evaluating that would definitely require not a few multiplications. $\endgroup$ Sep 6, 2012 at 0:23
7
$\begingroup$
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 :)

$\endgroup$
3
  • $\begingroup$ What do you think? $\endgroup$ Sep 5, 2012 at 17:53
  • 1
    $\begingroup$ @Verde what is this, self-Rorschach? I don't think that works… “I think it says I'm handsome” $\endgroup$
    – F'x
    Sep 5, 2012 at 18:09
  • 2
    $\begingroup$ “My shirt, boy! What do you see!?” $\endgroup$ Sep 5, 2012 at 18:42
5
$\begingroup$

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]
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Aky
    May 26, 2013 at 23:51
  • $\begingroup$ @Aky Yeah, I didn't notice the date either. And I didn't notice someone had edited it. +1 to you, too. $\endgroup$
    – Michael E2
    May 26, 2013 at 23:53
  • $\begingroup$ I would also like to assure all readers that no horses were harmed during the writing of these answers. $\endgroup$
    – Aky
    May 26, 2013 at 23:55
  • 2
    $\begingroup$ Heh, another silly one: With[{m = 10}, Flatten@ConstantArray[🍺, {m, 1 + m, 1 + m + m}] ~Partition~ 6 // Dimensions // First ] (looks best on a mac) $\endgroup$
    – rm -rf
    May 27, 2013 at 0:35
  • 1
    $\begingroup$ @rm-rf Yeah, 🍻, right back at you, buddy! $\endgroup$
    – Michael E2
    May 27, 2013 at 4:43
4
$\begingroup$

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]
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ How about Tr[t], assuming your table is t? That's what R.M. did. $\endgroup$
    – DavidC
    Sep 5, 2012 at 19:18
  • 2
    $\begingroup$ @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. $\endgroup$ Sep 5, 2012 at 21:21
  • 3
    $\begingroup$ Don't give up. My hamsters died a long time ago. $\endgroup$
    – DavidC
    Sep 5, 2012 at 23:04
3
$\begingroup$

I'll join the bandwagon with SparseArray:

sq[n_Integer] := Tr@SparseArray[{{i_, i_} :> i^2}, n]
$\endgroup$
4
  • $\begingroup$ Squaring involves multiplication, doesn't it? Tsk, tsk :-). $\endgroup$
    – whuber
    Sep 5, 2012 at 19:39
  • $\begingroup$ @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 :) $\endgroup$
    – rm -rf
    Sep 5, 2012 at 19:47
  • $\begingroup$ Original +1 but slow sq[10^6]; // AbsoluteTiming yields {2.1980000, Null}. $\endgroup$
    – Artes
    Sep 5, 2012 at 20:04
  • 1
    $\begingroup$ @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) $\endgroup$
    – rm -rf
    Sep 5, 2012 at 20:42
2
$\begingroup$

A Wolfram Alpha minded answer:

WolframAlpha["find the sequence 1,5,14,30,55"]
$\endgroup$
1
$\begingroup$
sos[n_Integer] := Total[Total[Range[1, #, 2]] & /@ (2 Range[n])]
$\endgroup$
2
  • 2
    $\begingroup$ No need to call Total[] twice: Total[Range[1, #, 2] & /@ (2 Range[n]), 2] $\endgroup$ May 26, 2013 at 13:55
  • $\begingroup$ @J.M. Thank you. $\endgroup$
    – Aky
    May 26, 2013 at 14:03
0
$\begingroup$

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}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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