*Introduction to Number Theory*, by Mathew Crawford, from Art of Problem Solving, and we've spent most of our sessions since then working out of that. I like not having to worry about what we're going to explore, and he seems to like the problems we encounter each week. He and I work through each problem together. Sometimes I hold back more, and get him to do one on his own, and sometimes I do more (with him correcting my mistakes). We skipped most of the first 3 chapters, because he knew most of that.

Number Theory includes so many cool ideas. I especially like playing with modular arithmetic, and seeing the power it can have. I've never taken a number theory course myself, so I'm consolidating my thinking, and enjoying the stretching.

Here's a problem from the book (modified a bit):

I've got one part solved, and am still thinking about another part...Consider n! and the sum 1+2+...+n.

When is the sum a factor of the factorial?(problem 6.31)

[Please don't give complete solutions in the comments. But I'd love to know if you've played with it, and what approach you took.]

Enjoy!

_____

*Search on Artemis to find all the posts.

Cute problem. I looked at the formulas for computing factorials and triangular numbers and sought insight. Once I had an idea, I then through some carefully chosen test cases at it to validate the idea.

ReplyDeleteFor instance, I verified that when n=36, the sum is not a divisor of the product, but it is when n=38.

I am confident of my solution, but I haven't proven it.

I too considered a closed expression for the sum from 1 to n and thought I had an answer pretty quickly. Realized from Blaise's comment that I was missing a piece. I now think that I've dealt with this 2nd part and have an informal proof. So if n=100, the sum isn't a divisor of the factorial but the sum is a divisor when n=101.

ReplyDeleteYes, fab problem. I was going to say I hadn't figured it out yet but as I started to write down my approach it became clear to me that I had. So, for n=732 the sum does not divide the factorial, but for n=733 it does... is this what you're getting Avery and Blaise?

ReplyDeleteMy approach, like the others, began with writing a closed form for the sum. Then I multiplied and divided some stuff and reduced everything mod n+1. Then I realized I knew what was going on and it reminded me of Wilson's Theorem.

Everyone's being so good about hiding their complete thoughts. :^) I guess I'll say a little here. Odd numbers were easy for me. I showed 'Artemis' a proof as I thought it out. Even numbers felt more confusing, but then I thought about it in bed, and realized I had it.

ReplyDeleteIf you have it, you know which even numbers work.

Ben, I'll have to think about Wilson's Theorem when I'm not so tired.