Re: Fun, weird, sad, cool

From: The Last Danish Pastry (clivet_at_gmail.com)
Date: 09/12/04 

Date: Sun, 12 Sep 2004 09:35:55 +0100

"James Harris" <jstevh@msn.com> wrote in message
news:3c65f87.0409111448.3f290d0@posting.google.com...

> "The Last Danish Pastry" <clivet@gmail.com> wrote in message
news:<2qgl9cF1029hpU1@uni-berlin.de>...
> > "James Harris" <jstevh@msn.com> wrote in message
> > news:3c65f87.0409110526.69140ee1@posting.google.com...
> >
> > > "The Last Danish Pastry" <clivet@gmail.com> wrote in message
> > news:<2qev7sFul4fgU1@uni-berlin.de>...
> > > > "James Harris" <jstevh@msn.com> wrote in message
> > > > news:3c65f87.0409101439.666fe8d6@posting.google.com...
> > > >
> > > > > "The Last Danish Pastry" <clivet@gmail.com> wrote in message
> > > > news:<2qdqs3Ftqef8U1@uni-berlin.de>...
> > [snip]
> > > > > > Back in the mists of time... well... six weeks ago...
> > > > > > No Way was explaining something to you...
> > > > > > http://tinylink.com/?2GoRBD5hlN
> > > > > >
> > > > > > No Way:
> > > > > > "Yes, it's constantly combing two terms with:
> > > > > > [(N+k)/(2*k)] = [N/k] - [N/(2*k)]"
> > > > > >
> > > > > > Harris:
> > > > > > "How do you get that?"
> > > > > >
> > > > > > Harris:
> > > > > > "I'd be interested in a proof of that relation.
> > > > > >
> > > > > > Note that for the relations I gave I proved [(N-4)/6] directly
by
> > the
> > > > > > method I've posted, and then used it with my prime counting
function
> > > > > > to find the other formulas.
> > > > > >
> > > > > > So, not surprisingly, I'm curious about how you came up with
your
> > > > > > formula, as I doubt you used my prime counting function.
> > > > > >
> > > > > > That is, I'd like to see the proof of your formula:
> > > > > >
> > > > > > [(N+k)/(2*k)] = [N/k] - [N/(2*k)]"
> > > > > >
> > > > > > A couple of people pointed out that the proof was trivial.
> > > > >
> > > > > But they never gave a valid proof.
> > > >
> > > > David Kastrup gave a perfectly valid proof at
> > > > http://tinylink.com/?THwzLbot1J
> > > >
> > > > I reproduce it here:
> > > > ===========================================================
> > > > > > How do you get that?
> > > > >
> > > > > Oh, good grief. You are not being serious, right?
> > > > >
> > > > > [a/b] =(a - (a mod b))/b
> > >
> > > Correct.
> > >
> > > > > Consequently you have
> > > > > [(N+k)/2k] + [N/2k] = N/k + 1/2 - ((N+k mod 2k) + (N mod 2k))/2k
> > >
> > > Ugly, but still ok. Here substitutions were made using
> > >
> > > [a/b] = a/b - (a mod b)/b
> > >
> > > from the previous correct relation, which is fine in rationals though
> > > the poster doesn't state that he's now in the field of rationals,
> >
> > No. He doesn't.
> >
> > If, in a mathematical proof, it has been established, for example, that
x, y
> > and z are integers and also that
> >
> > x + y = z (1)
> >
> > and if now, the author of the proof wishes to use the fact that
> >
> > x/2 + y/2 = z/2 (2)
>
> Now you're in rationals unless x, y and z are even.
>
> That's just a fact and I don't know why you're trying to argue about
> something so basic.
>
> > it is not usual to remark that while equation (1) concerns the equality
of
> > two integers, equation (2) concerns the equality of two rationals. Even
if
> > such a remark was deemed to be required, "I am now in the field of
> > rationals" would be far too imprecise for the purpose.
>
> You do understand right that if you're not in rationals, for instance,
> if you're in the ring of integers, then you can't just put up x/2
> unless x is even, right?
>
> Do you understand that?
>
> The ring has to do with valid operations, and if you're not in
> rationals, then 1/2 is not in the ring, so you can't act like it is.
>
> Why argue about something so basic?
>
> > Anyway...
> >
> > > and
> > > then there's some grouping and basic simplification done.
> > >
> > > > > Now if (N mod 2k) < k, then
> > > > > (N mod 2k) = (N mod k) and (N+k mod 2k) = k + (N mod k)
> > > > > else
> > > > > (M mod 2k) = (N mod k) + k and (N+k mod 2k) = (N mod k)
> >
> > TYPO: "(M mod 2k)" should be "(N mod 2k)"
> >
> > > Here it's just bizarre, and I don't feel like muddling through it
> > > again.
> >
> > I see. I take that to mean that you do not understand it.
>
> I said it's just bizarre and I didn't feel like muddling through it.
>
> So you can take it to mean that it's just bizarre and I don't feel
> like muddling through it.
>
> > Not understanding a step in a proof is a commonplace in mathematics. The
> > usual procedure is to have pencil and paper to hand so that you can
perform
> > the required manipulations to get from one line to the next.
>
> I have the direct proof, which is quite simple.
>
> I muddled through the above a while back, and saw something I didn't
> like, but didn't feel like going through it again when I was typing up
> my reply.
>
> > Let me try to help you with the above.
> >
> > Let P = N mod 2k.
> >
> > Clearly 0 <= P < 2k.
> >
> > Hence
> > 0 <= P < k [case A]
> > OR (exclusively)
> > k <= P < 2k [case B]
> >
> > In case A we have:
> > N mod k = P mod k = P
> > So: N mod 2k = P = N mod k
> > AND
> > (N+k) mod 2k = (P+k) mod 2k = P+k = k + N mod k
> >
> > In case B we have:
> > N mod k = P mod k = P-k
>
> You have above
>
> P = N mod 2k
>
> so substituting gives
>
> N mod k = (N mod 2k) mod k = (N mod 2k) - k.
>
> > So: N mod 2k = P = k + N mod k
>
> And that gives
>
> N mod 2k = (N mod 2k) = k + N mod k
>
> and it's so freaking muddled that it's hard to see what the hell
> you're trying to say, but if you feel confident then go ahead and
> expand out on these steps.
>
> At this point your case is that
>
> k <= (N mod 2k) < 2k
>
> and don't use P. I find it annoying to have to come back and make
> substitutions for a useless extra variable. Just use (N mod 2k).
>
> And yes, please expand on just that part for now.

Ok. Let me try again.

We know that N can be expressed as:

    N = 2kQ + P

where Q is some integer and 0 <= P < 2k. However, if you don't like these
extra names P and Q we can just say:

    N = 2k[N/2k] + (N mod 2k)

Clearly 0 <= N mod 2k < 2k.

Hence
    0 <= N mod 2k < k [case A]
OR (exclusively)
    k <= N mod 2k < 2k [case B]

In case A we have:
    N mod k
    = (2k[N/2k] + (N mod 2k)) mod k
    = (N mod 2k) mod k, since 2k[N/2k] is a multiple of k
    = N mod 2k, since [in case A] N mod 2k < k
    So: N mod 2k = N mod k [*]
AND
    (N+k) mod 2k
    = (2k[N/2k] + (N mod 2k) + k) mod 2k
    = ((N mod 2k) + k) mod 2k, since 2k[N/2k] is a multiple of 2k
    = (k + N mod 2k) mod 2k
    = k + N mod 2k, since k + N mod 2k < 2k [since N mod 2k < k]
    = k + N mod k, by result [*] above
    So: (N+k) mod 2k = k + N mod k

In case B we have:
    N mod k
    = (2k[N/2k] + (N mod 2k)) mod k
    = (N mod 2k) mod k, since 2k[N/2k] is a multiple of k
    = N mod 2k - k, since [in case B] k <= N mod 2k < 2k
    So: N mod 2k = k + N mod k [**]
AND
    (N+k) mod 2k
    = (2k[N/2k] + (N mod 2k) + k) mod 2k
    = ((N mod 2k) + k) mod 2k, since 2k[N/2k] is a multiple of 2k
    = (2k +(N mod 2k - k)) mod 2k
    = N mod 2k - k, since [in case B] 0 <= N mod 2k - k < k
    = N mod k, by result [**] above
    So: (N+k) mod 2k = N mod k

I realise I have still left steps out. If you still cannot understand it
please post again and I will try to fill in more details.

For completeness I repeat the end of an earlier post:
========================================================
> > > So the right side is
> > > N/k + 1/2 - (2 (N mod k) + k)/2k = (N - (N mod k)/k) = [N/k]

TYPO: "(N - (N mod k)/k)" should be "(N/k - (N mod k)/k)"

> And how does that follow?

The poster is referring to the right hand side of the equation

[(N+k)/2k] + [N/2k] = N/k + 1/2 - ((N+k mod 2k) + (N mod 2k))/2k

In case A we have:

  N/k + 1/2 - ((N+k mod 2k) + (N mod 2k))/2k
= N/k + 1/2 -((k + N mod k) + (N mod k))/2k
= N/k + 1/2 - 1/2 -(N mod k)/k
= (N - N mod k)/k
= [N/k]

In case B we have:

  N/k + 1/2 - ((N+k mod 2k) + (N mod 2k))/2k
= N/k + 1/2 - ((N mod k) + (k + N mod k))/2k
= N/k + 1/2 - 1/2 -(N mod k)/k
= (N - N mod k)/k
= [N/k]

So, since case A and case B exhaust the cases, the original formula is
proved.
======================================================== 

-- 
Clive Tooth
http://www.clivetooth.dk

Relevant Pages

  • Re: Fun, weird, sad, cool
    ... >> If, in a mathematical proof, it has been established, for example, that x, y ... that it's required to -say- that we're now in rationals. ... >if you're in the ring of integers, then you can't just put up x/2 ... please expand on just that part for now. ...
    (sci.math)
  • Re: JSH: Critique means slow, and thorough
    ... Zis in the rationals. ... integers gives you reals, as you end up with numbers that result from infinite sums, whether you want them or not. ... where 1 and -1 are the only rational units is the field of reals, and if i is in the ring, then you have the field of complex numbers. ...
    (sci.math)
  • Re: PL/I, COBOL, Advantages, Equivalence, et al
    ... The rationals and the integers have the same cardinality - they can be placed in 1-1 correspondence, but that does not make them isomorphic. ... Algebraically, the integers are a ring, in fact an integral domain, and the rationals are a field of characteristic 0. ... There are several methods for constructing the reals from the rationals. ... In other words, all roots of polynomial equations with either real or complex coefficients are complex numbers and every such equation has a complete set of n roots, where n is the degree of the equation (the fundamental theorem of algebra). ...
    (comp.lang.pl1)
  • Re: semi-local rings
    ... >Let R be a semi-local ring, that is, a ring ... the two maximal ideals of R are the rationals in R whose ... denominator is not a multiple of 3). ... the map T_1 to R_is not surjective. ...
    (sci.math)
  • Re: PL/I, COBOL, Advantages, Equivalence, et al
    ... The rationals and the integers have the same cardinality - they can be placed in 1-1 correspondence, but that does not make them isomorphic. ... the rationals are also a ring because after all a field is a ring with additional properties. ... There are several methods for constructing the reals from the rationals. ... In other words, all roots of polynomial equations with either real or complex coefficients are complex numbers and every such equation has a complete set of n roots, where n is the degree of the equation (the fundamental theorem of algebra). ...
    (comp.lang.pl1)