Month: November 2024

NP Fun

Olly / / Math Posts

Today I read about P and NP. I started with the informal discussion of the topic in Math Games with Bad Drawings by Ben Orlin, which I got for my birthday last week. Then I read the somewhat more technical overview in Introduction to Algorithms by Thomas H. Cormen et al., a beautiful, big book that I’ve been lugging around since college. Then I looked at some of the discussion of the topic in The Princeton Companion to Mathematics (an even bigger, more beautiful book). It was good to refresh my memory on this fundamental of computer science, which was my college minor.

For those unaware, P and NP are classes of problems, divided based on how difficult they appear to be to solve. Problems in P can be thought of as those that will take a computer a reasonable length of time to solve. Problems in NP are those that, using any known algorithm, will take a computer an unreasonable length of time to solve. The relationship between P and NP is an unsolved problem in mathematics. (Are they actually different?) Something I thought was interesting, though, was Ben Orlin’s comment that humans seem to be very attracted to problems in NP. Many of our games and puzzles fall into that class.

Oops

Olly / / Math Posts

Well, it turns out that 253 is not prime. Rather, 253=11(23). It also turns out that the proposition I wanted to use to show that 253 is prime is not true. Oops.

(I worked out the latter myself and then looked up the former.)

Today I’ve been reading more about primality tests, which is a complex topic. I found this page, which seems to give a fairly clear account of two of them. I’m going to have to review quite a few ideas in number theory to understand it, though.

Dabbling Day

Olly / / Updates

I only did a little study today, but it is more than I have been doing for the past five weeks. I worked for a while on showing that 253 is prime, but didn’t make much progress with the proposition I was trying to prove. I will try again tomorrow.

I also started watching a video from the YouTube channel 3Blue1Brown. I wanted to think more about the questions it introduced, though, so I did not watch all of it.

The Renewal Equation Renewed

Olly / / Math Posts

Hello, faithful readers (and anyone else out there). I took a much longer break than I intended, but I am finally ready to start blogging again. There has been a problem with my medication for the past three weeks, but it is now corrected and I am feeling better.

Today I worked on some AMC exam problems. The one I found most interesting was:

What is the least value of $n$ such that $n!$ is a multiple of $2024$?

I am pretty sure I know the answer to this, as well as how to answer the analogous question for any natural number. I ended up pursuing a tangent, however, to do with how I would show that 253, one of the prime factors of 2024, is indeed prime. I expect to post more about that in the coming week. Stay tuned.

(Note on 22 November: It turns out 253 is not prime. Oops.)