From: Sashank Varma
Subject: birthday problem in lisp
Date: 
Message-ID: <varmas-0411981219300001@129.59.192.40>
a stats newbie just asked me to prove that if a room contains
more than 22 randomly chosen people, there is a greater than
50% chance that two share the same birthday. it's an old
problem that most of us on this newsgroup have probably solved
at some point. so i fired up my copy of MCL and we solved
the problem. thought i'd share the results with the newsgroup.

(if you like challenges, you should stop here and give it
a crack.)

===

? (defun ! (n)
    "factorial function."
    (if (zerop n)
      1
      (* n (! (- n 1)))))
!

? (defun sample-without (n r)
    "number of ways to sample n items r times without replacement."
    (/ (! n) (! (- n r))))
SAMPLE-WITHOUT

? (defun sample-with (n r)
    "number of ways to sample n items r times with replacement."
    (expt (float n) r))
SAMPLE-WITH

? (defun prob (r)
    "probability that r people have different birthdays."
    (/ (sample-without 365 r) (sample-with 365 r)))
PROB

? (dotimes (n 57)
    (format t "~&~A:~A~,3F" (+ n 1) #\tab (prob (+ n 1))))
1: 1.000
2: 0.997
[snip!]
22:   0.524
23:   0.493
[snip!]
56:   0.012
57:   0.010
NIL
? 

yeah, i know it's missing error checking, i shouldn't have
used a user-reserved macro character (!) to name the factorial
function, etc; i was just "thinking out loud" in lisp to solve
the problem.

sashank

From: Paul McNamee
Subject: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <86pvak5yq2.fsf@nautilus.jhuapl.edu>
> a stats newbie just asked me to prove that if a room contains
> more than 22 randomly chosen people, there is a greater than
> 50% chance that two share the same birthday.
Speaking of doing mathematical tricks in Lisp, here's a short
anecdote.

My collegueues and I love plying each other with interesting puzzles
and a couple of days ago my officemate asked me what the square root
of i (as in, i the complex number) was.  I spent a few minutes on it,
and then someone from a neighboring office came in with the solution.
It looked right so I stopped my work somewhat disappointed that I
hadn't arrived at the solution first.

Only then I realized that I could have found the solution much faster
by evaluating (sqrt (sqrt -1)) in my Lisp interpreter.  Oh well, too
bad I didn't think of it right off.

- Paul

············@jhuapl.edu
Johns Hopkins University Applied Physics Laboratory
http://apl.jhu.edu/~paulmac/
From: Klaus Schilling
Subject: Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <8767cc5w2v.fsf@ivm.de>
Paul McNamee <·······@apl.jhu.edu> writes:
> 
> My collegueues and I love plying each other with interesting puzzles
> and a couple of days ago my officemate asked me what the square root
> of i (as in, i the complex number) was.  I spent a few minutes on it,
> and then someone from a neighboring office came in with the solution.
> It looked right so I stopped my work somewhat disappointed that I
> hadn't arrived at the solution first.
> 
> Only then I realized that I could have found the solution much faster
> by evaluating (sqrt (sqrt -1)) in my Lisp interpreter.  Oh well, too
> bad I didn't think of it right off.

Most people who know about complex numbers know it by heart,  it can't be
called an interesting math problem.

	Klaus Schilling
From: Barry Margolin
Subject: Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <o3Y42.13$Ki.321538@burlma1-snr1.gtei.net>
In article <··············@ivm.de>,
Klaus Schilling  <···············@home.ivm.de> wrote:
>Paul McNamee <·······@apl.jhu.edu> writes:
>> Only then I realized that I could have found the solution much faster
>> by evaluating (sqrt (sqrt -1)) in my Lisp interpreter.  Oh well, too
>> bad I didn't think of it right off.
>
>Most people who know about complex numbers know it by heart,  it can't be
>called an interesting math problem.

There's a difference between "know *about* complex numbers" and using them
regularly enough to have information like that off the top of your head.  I
might have known this 20 years ago, but not now.

-- 
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
From: Aleksandar Bakic
Subject: Re: Interesting math problems easily solved with Lisp (was birthday  problem in lisp)
Date: 
Message-ID: <36551433.74033155@brazil.tcimet.net>
Barry Margolin wrote:
> 
> In article <··············@ivm.de>,
> Klaus Schilling  <···············@home.ivm.de> wrote:
> >Paul McNamee <·······@apl.jhu.edu> writes:
> >> Only then I realized that I could have found the solution much faster
> >> by evaluating (sqrt (sqrt -1)) in my Lisp interpreter.  Oh well, too
> >> bad I didn't think of it right off.
> >
> >Most people who know about complex numbers know it by heart,  it can't be
> >called an interesting math problem.
> 
> There's a difference between "know *about* complex numbers" and using them
> regularly enough to have information like that off the top of your head.  I
> might have known this 20 years ago, but not now.
> 

But there is a simple theorem: represent unit-size complex numbers in
polar coordinates. Then, when you multiply them, just add the angles.
Vice versa, when taking a root of such a number, just divide its angle
by the root degree. For example, i = (1, pi/2), sqrt(i) = (1, pi/4).

Aleks

> --
> Barry Margolin, ······@bbnplanet.com
> GTE Internetworking, Powered by BBN, Burlington, MA
> *** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
> Don't bother cc'ing followups to me.
From: Barry Margolin
Subject: Re: Interesting math problems easily solved with Lisp (was birthday  problem in lisp)
Date: 
Message-ID: <kai52.103$Ki.894592@burlma1-snr1.gtei.net>
In article <·················@brazil.tcimet.net>,
Aleksandar Bakic  <········@brazil.tcimet.net> wrote:
>Barry Margolin wrote:
>> 
>> In article <··············@ivm.de>,
>> Klaus Schilling  <···············@home.ivm.de> wrote:
>> >Paul McNamee <·······@apl.jhu.edu> writes:
>> >> Only then I realized that I could have found the solution much faster
>> >> by evaluating (sqrt (sqrt -1)) in my Lisp interpreter.  Oh well, too
>> >> bad I didn't think of it right off.
>> >
>> >Most people who know about complex numbers know it by heart,  it can't be
>> >called an interesting math problem.
>> 
>> There's a difference between "know *about* complex numbers" and using them
>> regularly enough to have information like that off the top of your head.  I
>> might have known this 20 years ago, but not now.
>
>But there is a simple theorem: represent unit-size complex numbers in
>polar coordinates. Then, when you multiply them, just add the angles.
>Vice versa, when taking a root of such a number, just divide its angle
>by the root degree. For example, i = (1, pi/2), sqrt(i) = (1, pi/4).

If you have to do that, you obviously don't "know it by heart."  I'm sure I
could have figured it out, I just didn't know it off the top of my head.

-- 
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
From: Liam Healy
Subject: Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <51btm2faru.fsf@corkie.nrl.navy.mil>
Paul McNamee <·······@apl.jhu.edu> writes:

...
> 
> My collegueues and I love plying each other with interesting puzzles
> and a couple of days ago my officemate asked me what the square root
> of i (as in, i the complex number) was.  I spent a few minutes on it,
> and then someone from a neighboring office came in with the solution.
> It looked right so I stopped my work somewhat disappointed that I
> hadn't arrived at the solution first.
> 
> Only then I realized that I could have found the solution much faster
> by evaluating (sqrt (sqrt -1)) in my Lisp interpreter.  Oh well, too
> bad I didn't think of it right off.
> 
> - Paul

Please, Lisp is a powerful tool.  Use it wisely :-)

No computer, no calculating,
sqrt2/2 + sqrt2/2 i

Think polar coordinates.  It's easy.
i is a unit vector at 90 degrees,
its square root is a unit vector at 45 degrees.
Done.

Next problem: what's the cube root of i?
(sqrt3/2 + i/2)

-- 
Liam Healy
··········@nrl.navy.mil
From: Ralf Muschall
Subject: Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <73ctrc$h85$1@news00.btx.dtag.de>
Liam Healy wrote:

> Please, Lisp is a powerful tool.  Use it wisely :-)

> No computer, no calculating,
> sqrt2/2 + sqrt2/2 i
> 
> Think polar coordinates.  It's easy.

It's easy for us physicists, mathematicians, technicians of some
sort and similar perverts :-)
For other people, it is as hard as computing the resultant
of two polynomials (e.g. x^4+x*y+1, x^3+y^3 wrt. x) would be
for us (agreed, Lisp doesn't have that, but you get the idea).

Ralf
From: Paul McNamee
Subject: Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <86g1b86bhf.fsf@nautilus.jhuapl.edu>
·············@t-online.de (Ralf Muschall) writes:
[on computing the sqrt of i]
> > No computer, no calculating,
> > sqrt2/2 + sqrt2/2 i
> > 
> > Think polar coordinates.  It's easy.
> 
> It's easy for us physicists, mathematicians, technicians of some
> sort and similar perverts :-)
> For other people, it is as hard as computing the resultant
> of two polynomials (e.g. x^4+x*y+1, x^3+y^3 wrt. x) would be
> for us (agreed, Lisp doesn't have that, but you get the idea).

I was the original poster regarding computing the sqrt of i, and I
don't mind the thrashing I've received.  It's been about 10 years or
so since I've done any complex math, and I wasn't aware of the unit
circle technique for solving this problem so easily.  If I had known
it was so simple I wouldn't have posted it here -- my intended point
was that Lisp remains a great environment for playing around with
problems.

I'd love to see more posts here about (truly) interesting problems.

- Paul

············@jhuapl.edu
Johns Hopkins University Applied Physics Laboratory
http://apl.jhu.edu/~paulmac/
From: David Steuber "The Interloper
Subject: Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <365db9cd.2635639@news.newsguy.com>
On 24 Nov 1998 16:13:00 -0500, Paul McNamee <·······@apl.jhu.edu>
claimed or asked:

% I'd love to see more posts here about (truly) interesting problems.

Ok, how about proving Fermat's last theorem?

a^n + b^n = c^n is false for all integers a,b,c where n > 2.

I recall the Cambridge proof being on the order of 200 pages.  A
shorter proof would be nice.  One that I get would be even nicer.
Keep in mind that I have 11 fingers...

10, 9, 8,7,6 on one hand, plus five on the other.

--
David Steuber (ver 1.31.3a)
http://www.david-steuber.com
To reply by e-mail, replace trashcan with david.

May the source be with you...
From: Natarajan Krishnaswami
Subject: Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <slrn75qh3t.hd2.nxk3@yukon.SCL.CWRU.Edu>
On Thu, 26 Nov 1998 05:46:58 GMT, David Steuber "The Interloper" <········@david-steuber.com> wrote:
> Keep in mind that I have 11 fingers...
> 
> 10, 9, 8,7,6 on one hand, plus five on the other.

Sort of like horses: fore legs in front, two in back, for a total of
six legs, an even number.  But six is certainly an odd number of legs
for a horse to have, so the number of legs a horse has is both even
and odd, so it must have infinitely many legs....


N.
From: Christopher R. Barry
Subject: Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <365E7EA3.7C5B4C9B@2xtreme.net>
David Steuber The Interloper wrote:
> 
> On 24 Nov 1998 16:13:00 -0500, Paul McNamee <·······@apl.jhu.edu>
> claimed or asked:
> 
> % I'd love to see more posts here about (truly) interesting problems.
> 
> Ok, how about proving Fermat's last theorem?
> 
> a^n + b^n = c^n is false for all integers a,b,c where n > 2.
> 
> I recall the Cambridge proof being on the order of 200 pages.
[...]

200 pages??? This must have been a really verbose and descriptive
version. I have a 1600x1200 X desktop on a 21" and with a maximised
browser window I could fit half of the thing in one of these windows.
With a small enough font, I'm sure I could get the whole thing, and it
would still be readable. This was a full version, not like the
generalization on the page it was linked from that was much smaller and
actually comprehensible to me.

Christopher
From: Gareth McCaughan
Subject: Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp)
Date: 
Message-ID: <86u2zlqm5p.fsf@g.pet.cam.ac.uk>
Christopher Barry wrote:

[the proof of FLT]
> 200 pages??? This must have been a really verbose and descriptive
> version. I have a 1600x1200 X desktop on a 21" and with a maximised
> browser window I could fit half of the thing in one of these windows.

I don't know what that was (maybe a description of how the
proof works), but it certainly wasn't the Wiles/Taylor proof
of FLT, which is certainly much nearer to 200 pages than to 2.
I know: I've seen it.

-- 
Gareth McCaughan       Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk  Cambridge University, England.
From: David Steuber "The Interloper
Subject: Fermat's Last Joke (was Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp))
Date: 
Message-ID: <365f92d2.1518152@news.newsguy.com>
On 27 Nov 1998 13:51:14 +0000, Gareth McCaughan
<·····@dpmms.cam.ac.uk> claimed or asked:

% Christopher Barry wrote:
% 
% [the proof of FLT]
% > 200 pages??? This must have been a really verbose and descriptive
% > version. I have a 1600x1200 X desktop on a 21" and with a maximised
% > browser window I could fit half of the thing in one of these windows.
% 
% I don't know what that was (maybe a description of how the
% proof works), but it certainly wasn't the Wiles/Taylor proof
% of FLT, which is certainly much nearer to 200 pages than to 2.
% I know: I've seen it.

It is said that in the margins of his notes, Fermat wrote of his
theorem, "Proof very interesting."  However, the proof was never
found.  Since the theorem seems true by inspection, it is obvious that
Fermat jotted down that little note for the same reason that text book
authors write, "... is left as an exercise for the student."

--
David Steuber (ver 1.31.3a)
http://www.david-steuber.com
To reply by e-mail, replace trashcan with david.

May the source be with you...
From: Hrvoje Niksic
Subject: Re: Fermat's Last Joke (was Re: Interesting math problems easily solved with Lisp (was birthday problem in lisp))
Date: 
Message-ID: <kigiufzisj0.fsf@jagor.srce.hr>
Clemens Heitzinger <········@rainbow.studorg.tuwien.ac.at> writes:

> "I have found a truely marvellous proof, but the margin is too small
> to hold it."
> 
> So one wonders...  Why didn't he get a piece of paper (he sure had
> enough) and write it down, if it was such a great proof?

Because he considered it obvious?  :-)

-- 
Hrvoje Niksic <·······@srce.hr> | Student at FER Zagreb, Croatia
--------------------------------+--------------------------------
Ask not for whom the <CONTROL-G> tolls.