-----------------------------------

wtd

Thu Feb 15, 2007 9:42 am


Open Language TYS

-----------------------------------

Write a function which sums an inclusive range of numbers.  Bonus points for efficiency.


-----------------------------------

Cervantes

Thu Feb 15, 2007 11:54 am


RE:Open Language TYS

-----------------------------------

Maybe I don't understand the question, because here's my solution:

(define (sum low high)
    (/ (- (* high (sub1 high)) (* (sub1 low) (- low 2))) 2))


Are we supposed to take into account negative numbers too, I suppose?


-----------------------------------

Clayton

Thu Feb 15, 2007 12:16 pm


Re: Open Language TYS

-----------------------------------

In my eyes, it shouldn't make a difference. Adding 1 + 2 is the same as adding 2 + 1 right? so you just get the range and add all numbers together to find the total, so I'm not sure why you're multiplying there Cervantes :P


-----------------------------------

Hikaru79

Thu Feb 15, 2007 12:35 pm


Re: Open Language TYS

-----------------------------------

In my eyes, it shouldn't make a difference. Adding 1 + 2 is the same as adding 2 + 1 right? so you just get the range and add all numbers together to find the total, so I'm not sure why you're multiplying there Cervantes :P

He's using the identity that the sum of the first n consecutive numbers is n(n+1)/2. This gives us an almost constant-time solution to wtd's TYS, which also leads me to think he meant something else. Cervantes' solution is also what I would have done; it's just too easy :P


-----------------------------------

wtd

Thu Feb 15, 2007 12:52 pm


RE:Open Language TYS

-----------------------------------

No no... you got the right answer.  :)


-----------------------------------

Clayton

Thu Feb 15, 2007 1:39 pm


Re: Open Language TYS

-----------------------------------

Shows how little I know, and how much I need to learn :P


-----------------------------------

Cervantes

Thu Feb 15, 2007 3:31 pm


Re: Open Language TYS

-----------------------------------

This reminds me of a problem I liked, stolen from 
The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2.

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is 4164. Note that 1 = 0^2 + 1^2 has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than 10^8 that are both palindromic and can be written as the sum of consecutive squares.