CODEWITHSUNDEEP
pythonalgorithmmath
Gabriel
Gabriel

Reputation: 18780

How do I get the Math equation of Python Algorithm?

ok so I am feeling a little stupid for not knowing this, but a coworker asked so I am asking here: I have written a python algorithm that solves his problem. given x > 0 add all numbers together from 1 to x.

def intsum(x):
  if x > 0:
    return x + intsum(x - 1)
  else:
    return 0

intsum(10)
55

first what is this type of equation is this and what is the correct way to get this answer as it is clearly easier using some other method?

Upvotes: 5

Views: 1032

Answers (8)

Alex Martelli
Alex Martelli

Reputation: 881695

Transforming recursively-defined sequences of integers into ones that can be expressed in a closed form is a fascinating part of discrete mathematics -- I heartily recommend Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik (see. e.g. the wikipedia entry about it).

However, the specific sequence you show, fac(x) = fac(x - 1) + x, according to a famous anecdote, was solved by Gauss when he was a child in first grade -- the teacher had given the pupils the taksk of summing numbers from 1 to 100 to keep them quet for a while, but two minutes later there was young Gauss with the answer, 5050, and the explanation: "I noticed that I can sum the first, 1, and the last, 100, that's 101; and the second, 2, and the next-to-last, 99, and that's again 101; and clearly that repeats 50 times, so, 50 times 101, 5050". Not rigorous as proofs go, but quite correct and appropriate for a 6-years-old;-).

In the same way (plus really elementary algebra) you can see that the general case is, as many have already said, (N * (N+1)) / 2 (the product is always even, since one of the numbers must be odd and one even; so the division by two will always produce an integer, as desired, with no remainder).

Upvotes: 8

Felix Kling
Felix Kling

Reputation: 816462

Larry is very correct with his formula, and its the fastest way to calculate the sum of all integers up to n.

But for completeness, there are built-in Python functions, that perform what you have done, on lists with arbitrary elements. E.g.

  • sum()

    >>> sum(range(11))
55
>>> sum([2,4,6])
12

  • or more general, reduce()

    >>> import operator
>>> reduce(operator.add, range(11))
55

Upvotes: 3

brainjam
brainjam

Reputation: 19005

OP has asked, in a comment, for a link to the story about Gauss as a schoolchild.

He may want to check out this fascinating article by Brian Hayes. It not only rather convincingly suggests that the Gauss story may be a modern fabrication, but outlines how it would be rather difficult not to see the patterns involved in summing the numbers from 1 to 100. That in fact the only way to miss these patterns would be to solve the problem by writing a program.

The article also talks about different ways to sum arithmetic progressions, which is at the heart of OP's question. There is also an ad-free version here.

Upvotes: 3

edstafford
edstafford

Reputation: 53

I'm not allowed to comment yet so I'll just add that you'll want to be careful in using range() as it's 0 base. You'll need to use range(n+1) to get the desired effect.

Sorry for the duplication...

sum(range(10)) != 55

sum(range(11)) == 55

Upvotes: 3

Rob Rolnick
Rob Rolnick

Reputation: 9959

Here is how to prove the closed form for an arithmetic progression

S  = 1 +   2   + ... + (n-1) + n
S  = n + (n-1) + ... +   2   + 1
2S = (n+1) + (n+1) + ... + (n+1) + (n+1)
     ^ you'll note that there are n terms there.
2S = n(n+1)
S = n(n+1)/2

Upvotes: 4

Gabriel Ščerbák
Gabriel Ščerbák

Reputation: 18570

What you have there is called arithmetic sequence and as suggested, you can compute it directly without overhead which might result from the recursion.

And I would say this is a homework despite what you say.

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490148

Consider that N+1, N-1+2, N-2+3, and so on all add up to the same number, and there are approximately N/2 instances like that (exactly N/2 if N is even).

Upvotes: 1

Larry
Larry

Reputation: 4559

This is recursion, though for some reason you're labeling it like it's factorial.

In any case, the sum from 1 to n is also simply:

n * ( n + 1 ) / 2

(You can special case it for negative values if you like.)

Upvotes: 15

Related Questions