Tuesday, May 22, 2007

LHIRT POD #3 Solution

Here's the solution to LHIRT POD #3, again written white on white (highlight to read):

According to Catalan, 2NCN = ∑I NI 2. Since N C 0 = N C N = 1, there’s where our 2 comes from. It turns out that N C x where 1 < X < N. Therefore N C I = 2 + ∑ 1 N C I = 2 + (N * k) for some k. This means that the remainder will always be 2. As far as the converse, consider 343 as an example. 686 C 343 (mod 343) = 2, and yet 343=7 3 and thus not prime.

One issue with this: I have yet to find a counterexample that isn’t in the form pq where p and q are both prime. Interesting?

Cool problem huh? Anyone want to conjecture on that final form of the answer?


1 comment:

Anonymous said...

Excellent puzzle. At the right level for my rusty brain.

Thoroughly enjoyed solving it, though it made me open my old probability book for definitions and properties of combinations. ( Its been years since I studied math. Too much software makes your brain soft. :-) )

No luck with the converse though. I'm going to try the first puzzle now.

Reg. mathml why can't you use something like this? http://pear.math.pitt.edu/mathzilla/itex2mmlFrag.html