Mathing…

JD2718 has an interesting extension to How many ways can 1000 be expressed as the sum of consecutive integers? where he asks:

Given an integer N, N ≠ 0, how many ways can N be written as the sum of consecutive integers?

I came across the first puzzle through Nick’s blog Divide By Zero where he found the form of the solutions to the puzzle. He tried them out on a google spreadsheet and was able to find all 7 solutions. He didn’t count a consecutive sequence of 1 number (1,000 by itself) as a solution.

I verified Nick’s solution by doing a brute force search from -10,000 to 10,000 to find the sequences of consecutive integers that would add to 1,000.

I did this initially because I wondered if it was possible to have an infinite number of solutions. I thought that the negative numbers could be offset by the positive numbers in such a way as to produce the desired sum. I was wrong.

I then noticed that for 1,000 and for many other numbers I tried, the sequence of consecutive integers were always centered around a positive integer or a decimal that ended at 0.5.

Next thing I noticed was that when the sequence was centered around a positive integer it always had an odd number of consecutive integers. When the sequence was centered around a decimal that ended at 0.5 there were an even number of consecutive integers that added up to our solution.

The next 3 patterns that helped me get the solution were:

1. The first occurrence of the largest number of ways a number can be written as sum of consecutive integers happened on the following: 3 (3 ways), 9 (5 ways), 15 (7 ways), 45 (11 ways).
2. Prime numbers (other than 2) could be written in 3 ways only: 3 (3 ways), 5(3 ways), 7 (3 ways), 11 (3ways). My birthday which is prime (when written as DDMMYYYY) can be written in only 3 ways.
3. Powers of 2 could only be written 1 way

I’ll post the tool I used to help me find the solution tomorrow. The tool itself isn’t elegantly coded (this is not a programming class/puzzle) and doesn’t run efficiently (I’m also very rusty), but it was used to help me build some sense of what the solutions are so that I could get to a general solution.

The challenge was coming up with a systematic way of finding the number of different ways the number can be written as the sum of consecutive integers without having to find out what those sequences are.

My algorithm finds the following results:

• 1,000 can be written as a sum of consecutive integers 7 different ways
• 15,015 can be written as a sum of consecutive integers in 63 different ways
• 15, 30, 60, 120, 240, 480, 960, 1920 can all be written as a sum of consecutive integers in 7 different ways

The puzzle was interesting. However I feel as if I cheated since I found to solution with a little help from firefox, notepad, some javascript and html. I’m not sure how I’d be able to keep the kids engaged to find the solution or how they would find the solution another way. The hints I presented above should be sufficient to help a student get to the solution, but I only found those after a little programming. The tool I created also evolved as I looked for different patterns. I had to slowly improve the algorithm as the first few versions took 10-15 minutes on my slow computer to brute force search for solutions through large numbers. The question is what kind of question can you ask students without giving too much away. Give enough hints and we take away any joy students may get from discovering the solution to the puzzle themselves. In a way, puzzles are a little like the Zen Koans, it’s no fun when other people give you the answer.

NOTE: I don’t count a consecutive integer of 1 as a sum of consecutive integers (eg, 3=-2-1+0+1+2+3, 3=0+1+2, 3=1+2, 3=3, I don’t count the last one)

Sum of Consecutive Integers
Sum of Consecutive Integers: UPDATE 1
Sum of Consecutive Integers: UPDATE 2