Mathing…

This is a follow up to Sum of Consecutive Integers and Sum of Consecutive Integers: Update 1.

I presented the original question (how many ways can 1,000 can be written as sum of consecutive integers) to students in my Pre-Calculus Honors class. I estimate that about 10 students of 80 have seriously attempted it and some came close. I was pleasantly surprised when, on the next school day, one student presented to me the correct solution. I gave that student another number to try out and this time he came close. He missed the number of solutions by 1. As soon as I pointed it out, he found it within 2 minutes. He finds the number of ways by actually figuring out what the consecutive integers were and counted how many ways he found. He definitely had an algorithm to find the sequences of consecutive integers. That’s a good sign right?

The question for me as a teacher is (and one raised by Jonathan) is how did the student figure out the solution and how do you support students so they can discover the solution. The way I went about it is to figure out how I would solve it and how my line of questions led to the solution so that I can support my student through the same process. The problem upon reflection is, however, that tools available to me may not be available to students. I can’t expect students to be able to use my method. So I was excited that one of my students was able to find the solution.

When I asked the student how he arrived at the solution. He answered frankly and told me that he found the solution online. So I extended him an opportunity to get some “make-up credit” (since we don’t have extra credit at our school) if he could come up with a solution to extension to the first question (calculate the number of ways that N can be written as the sum of consecutive integers given an integer N). I have yet to hear from him. More importantly, I didn’t find out how one would go about finding a solution and how I could support that process for all students.

So I stayed busy with the second question which asked for a generalized solution. First thing I did was investigate, try out a few numbers and see how they worked to see if there were any easy patterns. Several versions later and we have SumConInt v1.1a. I have made one change to clarify the connections. I am counting a consecutive integer sequence of length 1. All numbers can be written as the sum of the sequence of integer starting with it with length 1.

First step is see if there are any obvious patterns for all the numbers from 1-50.

I didn’t find any patterns from the above. It seems that the number of ways increases when the numbers increase, but not in any familiar way. It also seemed that the number of ways also didn’t increase smoothly or steadily.

So I asked if there were any patterns to be found in even numbers.

No patterns stood out for me on this one immediately. However I did notice that some large numbers have few number of ways they can be written, they seem to be powers of 2. We’ll examine this later.

I asked if there were any patterns to be found in the odd numbers.

Didn’t see any patterns here. I did notice that 45 is the first number with double digit number of ways it can be written as sum of consecutive digits. Scrolling back up to check 1-50. I notice that the greatest number of ways seem to come up first for odd numbers; 3 in 4 ways, 9 in 6 ways, 15 in 8 ways, and 45 in 12 ways. I’ll investigate this later.

Time to follow up on the powers of 2 angle with prime factorization.

Seems like powers of 2 all have exactly 2 ways. Even factors don’t seem to have any effect on the number of ways.

Let’s check powers of 3 angle.

The number of ways increase linearly as the power of 3. Given 3ⁿ, the number of ways seems to be 2(n+1).

Let’s take a number with many factors like 60 and see if powers of 2 has any effect on the number of ways. My suspicion is that it will not have an effect on the number of ways.

That confirms it!

Let’s try this again but with powers of 3. There should be an increase in number of ways with increasing powers of 3.

I think I am on to something. This time though, instead of increasing by 2 as I saw earlier, it’s increasing by 4. Maybe the factor of 5 is doing something. I’ll follow up on it later.

Let’s investigate squares and cubes. First the squares.

And now the cubes.

Hrm. It seems the number of ways is primarily determined by odd factors.

Let’s try this again but only with odd squares and cubes. First the odd squares.

And the odd cubes.

225 is the most interesting number in here. It seems given a prime factorization, where n and m are exponents of 2 distinct odd prime numbers the, the number of ways is 2(n+1)(m+1). This may be the pattern. But why does it work?

Let’s build some numbers using only odd prime numbers and see if it follows the pattern.

#1 – 2(1+1) = 4 ways
#2 – 2(2+1) = 6 ways
#3 – 2(1+1)(1+1) = 8 ways
#4 – 2(2+1)(1+1) = 12 ways
#5 – 2(1+1)(1+1)(1+1) = 16 ways

Let’s check this again, but this time with odd primes. If I’m correct all odd prime numbers can be written in 2(1+1) = 4 ways.

Let’s try a few more combinations of odd factors.

Let’s try one more combination of odd prime factors where the powers are 1 and 2.

Looks good!

Let’s look in more detail why the exponents of odd factors seem to determine the number of ways. Notice for every number the “1st int” gives the first integer in the sequence, “num int” gives the number of integers in the sequence, and “median” gives the median of the sequence. Notice that “num int” time “median” gives the actual number.

Odd prime factors determine the number of unique odd factors in the sequence. If a number has 3¹5¹ in the prime factorization. We can have 1(3⁰5⁰), 3(3¹5⁰), 5(3⁰5¹), and 15 (3¹5¹) as the distinct odd factors. Multiplying the number 60 by powers of 3 increases the number of unique odd factors.

Let’s see what happens when we multiply by powers of 2.

Additional factors of 2 does not increase the number of ways, it does change the first even number of terms in a sequence. The higher the number of factors of 2, the greater the number of the first even numbered sequence of terms. It also does seem that these even numbered sequences are all multiples of the odd numbered factors.

The answer, it seems, is the number of distinct odd factors multiplied by two. Interestingly, Jonathan followed up his extension to the puzzle with a question that asked for the number of unique factors (odd or even) of a given number as if to hint at the solution.

I’ve had a few weeks to reflect on process of solving this puzzle. I’ve also had given some students who wanted to explore the puzzle a little further a link to the tool that I used to figure out the answer (SumConInt v1.1a). It is not obvious to students why I had those presets or why the sequence of questions led to the answer. I’m not sure how I would keep them motivated while solving the puzzle, especially if they didn’t have the tool like I did. I’m less sure whether what I did really helps them learn about the problem solving process or whether I’m giving them the solution to the question. If I am leading them to the solution with questions, is there any purpose to have them figure this problem out? I guess I’ve had limited success with this question. I’d be interested in knowing how other teachers might support students while solving this puzzle.

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

This is a follow-up to my response to JD2718′s Puzzle on Sum of Consecutive Integers

At end of Sum of Consecutive Integers I said I’d be posting the tool I used to get to my solution. I can’t find a better name for now so it’s temporarily just SumConInt. You can find it under Math Tools in the future.

Use the presets to go through some of the numbers that I tried as I looked for a pattern. There’s a logic to the sequence of presets that is listed. Each one clarifying the underlying structure just a little bit more. I hope it’ll lead you to the same solution that I found.

The script is NOT efficient. I haven’t spent time optimizing it. It was a one-off kind of thing that I used to test my conjectures. I may spend time cleaning up the code in the future. A supervisor warned me that having embarrassing/clumsy code online was one way to not get hired as a programmer. You may see random comments and variables that aren’t used. The script comes with no guarantees expressed or implied.

After you’re done playing with presets, try using some batch commands and some individual number tests. I haven’t spent time doing error checking on input so don’t test outlandish values unless you can handle crashes well. The “calculate up to” should be used for numbers less than 100. Use it with caution.

I will probably have a follow-up post with a solution in a few days.

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

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