I want to sum the squares for a given number N from 1 without using Multiplication. Is it possible?
14 Answers
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
-
2$\begingroup$ +1 This is in the spirit of the modern foundations of arithmetic. $\endgroup$– whuberSep 5, 2012 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
]
-
7$\begingroup$ I feel like browsing the wrong site ... $\endgroup$ Sep 5, 2012 at 11:50
A Mathematica minded answer:
HarmonicNumber[n, -2]
So:
Simplify[Sum[i^2, {i, n}] == HarmonicNumber[n, -2]]
(* True *)
-
$\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$– whuberSep 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$– whuberSep 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 thelea
instruction in assembly $\endgroup$ Sep 5, 2012 at 23:13 -
$\begingroup$ @whuber: from what I've seen internally,
HarmonicNumber
is converted toPolyGamma[]
; numerically evaluating that would definitely require not a few multiplications. $\endgroup$ Sep 6, 2012 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 :)
-
-
1$\begingroup$ @Verde what is this, self-Rorschach? I don't think that works… “I think it says I'm handsome” $\endgroup$– F'xSep 5, 2012 at 18:09
-
2
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]
-
$\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$– AkyMay 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$ 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$– AkyMay 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$ May 27, 2013 at 4:43
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.
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)
You can sum the diagonal. However, that might be slowest procedure of all.
-
$\begingroup$ How about
Tr[t]
, assuming your table ist
? That's what R.M. did. $\endgroup$– DavidCSep 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$– DavidCSep 5, 2012 at 23:04
I'll join the bandwagon with SparseArray
:
sq[n_Integer] := Tr@SparseArray[{{i_, i_} :> i^2}, n]
-
$\begingroup$ Squaring involves multiplication, doesn't it? Tsk, tsk :-). $\endgroup$– whuberSep 5, 2012 at 19:39
-
$\begingroup$ @whuber sshhh... it was supposed to be hidden :D Ok, you could do
{i_, i_} :> f[i, i]
, wheref
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$– ArtesSep 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
A Wolfram Alpha minded answer:
WolframAlpha["find the sequence 1,5,14,30,55"]
sos[n_Integer] := Total[Total[Range[1, #, 2]] & /@ (2 Range[n])]
-
2$\begingroup$ No need to call
Total[]
twice:Total[Range[1, #, 2] & /@ (2 Range[n]), 2]
$\endgroup$ May 26, 2013 at 13:55 -
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}
n = 10;Sum[i^2, {i, 1, n}]
orTotal@Table[i^2, {i, 1, n}]
. $\endgroup$For
loop.. $\endgroup$