Re: More number theory tidbits, paper?

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 07/31/04 

Date: Sat, 31 Jul 2004 11:23:47 -0400 (EDT)

On Sat, 31 Jul 2004, James Harris wrote:
>
> jesse@phiwumbda.org (Jesse F. Hughes) wrote:
>> jstevh@msn.com (James Harris) writes:
>>
>>> That relation was shown to be true by a poster in my previous thread,
>>> and I noted that I'd be interested if someone could derive the
>>> relation, but no one has.
>>
>> But what does *derive* mean? How can someone *prove* a result but
>> fail to *derive* it?
>
> The result is that floor((N-4)/6) is the count of odd composites that
> have 3 as a factor given an even N that is greater than 2.
>
> It is possible to prove that it does in fact give that count, but, how
> did I get the formula?

   /You/ probably got it from a heavenly messenger, but a normal person
(read: an evil, evil mathematician) would presumably get it by division.
Look:

     How many odd composites less than N are divisible by 3?

Well, we know that all numbers divisible by 3 are composites, except
for 3 itself. So we rephrase:

     How many odd multiples of 3 are less than N?
     Subtract 1 from the resulting count, if 3 is less than N.

Now, odd multiples of 3 are numbers of the form 6k+3.

     How many numbers of the form 6k+3 are less than N?
     Subtract 1 from the resulting count, if 3 is less than N.

Because I'm terribly lazy, we'll do the count by cases. Six cases
there are: one for each residue modulo 6.

     If N=0 (mod 6): we have (N/6), minus 1 if N>3
     If N=1 (mod 6): we have ((N-1)/6), minus 1 if N>3
     If N=2 (mod 6): we have ((N-2)/6), minus 1 if N>3
     If N=3 (mod 6): we have ((N-3)/6), minus 1 if N>3
     If N=4 (mod 6): we have ((N-4)/6)+1, minus 1 if N>3
     If N=5 (mod 6): we have ((N-5)/6)+1, minus 1 if N>3

Introducing the "floor" notation to get rid of some icky
minus signs, we have

     If N=0,1,2,3 (mod 6): we have floor(N/6), minus 1 if N>3
     If N=4,5 (mod 6): we have floor(N/6), plus 1 if N<=3

Now (belatedly!) we notice that N cannot be less than or
equal to 3 in the second case (N=4 or N=5 (mod 6)). So that
"if" drops out.

     If N=0,1,2,3 (mod 6): we have floor(N/6), minus 1 if N>3
     If N=4,5 (mod 6): we have floor(N/6)+1

Finally, we can use the fact that

     floor((N-4)/6) = floor(N/6) for N=4,5 (mod 6)
     floor((N-4)/6) = floor(N/6)-1 for N=0,1,2,3 (mod 6)

to derive that

     We have floor((N-4)/6) for all N>3

You had phrased the theorem as applying to all "even N greater
than 2." We have proved the stronger theorem that this formula
applies for /all/ natural numbers N greater than 3 (and of course
with the appropriate "-1" term added back in for N<=3).

> I derived the formula from first principles, but that was a couple of
> years ago, and the specifics of how I did it escape me at the moment.

   It's almost always worthwhile to derive it again if you have the time.
Just two days ago I found myself needing the point-to-line-segment
distance formula, but remembering next to nothing about the appropriate
concepts. So I got paper and pencil and derived a formula that worked...
for everything except horizontal lines. ;) (Following which I got on
Google and found the real formula on a website.) But it was quite a
pleasant surprise that I could actually get as far as I did. :))

> What if they post in order to believe that they can control
> mathematics and I ruin their fantasy?

   But I /do/ control mathematics! With a bit of practice, you might be
able to control it, as well.

-Arthur