HDTenEightyP/NetNews huggingface dataset:
From: victor@watson.ibm.com (Victor Miller)
Subject: Re: nth prime
Date: Fri, 11 Sep 1992 14:00:49 GMT
Reply-To: victor@watson.ibm.com
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
	<1992Sep10.164133.27763@infodev.cam.ac.uk> <a_rubin.716166518@dn66>
Organization: IBM, T.J. Watson Research Center

>>>>> On 10 Sep 92 23:08:38 GMT, a_rubin@dsg4.dse.beckman.com (Arthur Rubin) said:

Arthur> In <1992Sep10.164133.27763@infodev.cam.ac.uk> gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:

>In article <1992Sep10.190905.10741@waikato.ac.nz> bill@waikato.ac.nz writes:

>>Sorry to ask such a FAQ, but what's the quickest algorithm to
>>find the nth prime? Is it O(nlogn) or something else?

>I think there is no way to get p_n exactly that's much better than
>the good old sieve of Eratosthenes. So in sieving out multiples of 2
Arthur> ...

Arthur> This isn't quite correct.  There is an integral for (the number of primes
Arthur> <= n) which takes o(n) to evaluate.  (I don't know the exact order.)  I'm
Arthur> pretty sure that the time to find the first n primes is about  O(n log n),
Arthur> but you don't have to all n of them in order to find the n_th.
Arthur> --
Arthur> Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
Arthur> 216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
Arthur> My opinions are my own, and do not represent those of my employer.
Arthur> My interaction with our news system is unstable; please mail anything important.

This keeps coming up (maybe it should be in the FAQ).  There are two
different methods for evaluation pi(x) (the exact number of primes
<=x).  One is a method based on combinatorial sieving.  The latest and
greatest incarnation of that method is a paper "Calculating pi(x): the
Meissel-Lehmer Method" by Jeff Lagarias, Victor Miller (that's me),
and Anrew Odlyzko in Math. Comp. 1985.  It gives the history of this
method.  Although it had its genesis in the observation of Legendre
that one could get an explicit formula for pi(x) only involving primes
<= sqrt(x), it needed substantial refinements to get to the running
time of O(x^{2/3 + \epsilon}).  I programmed this method and used it
to calculate the table of values given in the paper (up to x=4*10^16).
Once one has a method of calculating pi(x) you can use binary search
to caculate p_n (the n-th prime).  This adds a factor of log n.  Using
interpolation search only adds a factor of log log n.

Lagarias and Odlyzko, in "Calculating pi(x): an Analytic Method" in J.
of Algorithms, 1986, describe a method based on "explicit formulas in
prime number theory" which has running time O(x^{3/5+\epsilon}) and
space o(x).  Based an a subsequent paper by Odlyzko and Schonhage this
running time can be gotten down to O(x^{1/2+\epsilon}) with space
O(x^{1/4+\epsilon}).  This method is extremely subtle, and to my
knowledge has never been implemented.


--
		Victor S. Miller
		Bitnet: VICTOR at WATSON
		Internet: victor@watson.ibm.com
		IBM, TJ Watson Research Center
		"Great artists steal; lesser artists borrow" Igor Stravinsky
From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
Newsgroups: sci.math
Subject: Re: Digits/Prog to compute pi?
Date: 15 Sep 92 23:41:43 GMT
Organization: U of Cambridge, England

In article <1992Sep15.090518.13252@sbil.co.uk>, pbond@spitws100.sbil.co.uk (Philip Bond) writes:

> Here is PI to around 65,000 places. You can get more if you need it. See
> the FAQ for details. I generated this list using Mathematica, and checked it 
> against the 1,000,000 places book published by the French Atomic Energy
> Commission. Let me know if you have any problems reading the email.
> 
>           .
>           .
>           .
>
>   701696524755774089164456867771715850058326994340167720215676772406812836656\
>   526412298243946513319735919970940327593850266955747023181320324371642058614\
>   103360652453693916005064495306016126782264894243739716671766123104897503188\
>   573216555498834212180284691252908610148552781527762562375045637576949773433\
>   684601560772703550962904939248708840628106794362241870474700836884267102255\
>   830240359984164595112248527263363264511401739524808619463584078375355688562\
>   231711552094722306543709260679735100056554938122457548372854571179739361575\
>   616764169289580525729752233855861138832217110736226000000000000000000000000\
                                                       ^^^^^^^^^^^^^^^^^^^^^^^^

At what point does it start being inaccurate? Immediately before those 0s? Or
somewhere else? (I don't believe all those 0s really belong there.)   

-- 
Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
Newsgroups: sci.math
Subject: Re: nth prime
Date: 10 Sep 92 23:17:42 GMT
Organization: U of Cambridge, England

In article <1992Sep10.164133.27763@infodev.cam.ac.uk>, gjm11@cus.cam.ac.uk (me) wrote:

> I think there is no way to get p_n exactly that's much better than
> the good old sieve of Eratosthenes.

Ahem. As has been pointed out to me, this is quite false. There are quicker
ways to calculate exactly the number of primes less than n (there's a method
due to Legendre that takes time about n^(2/3), and the person who pointed out
my mistake thinks there may be a method that takes only n^(3/5)), and then
[this is what I missed!] you can do a binary search thing, which is going to
take not more than about log n iterations of the prime-counting procedure.
So, YES: you can calculate the n'th prime in time about n^t, for some t which
might be as small as 3/5 but is certainly no worse than 2/3. ("About" here
means that you can do it in time O(n^(t+epsilon)) whenever epsilon>0, if
you're being picky.)

I can probably find a reference to the Legendre method if you want.
-- 
Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
Newsgroups: sci.math
Subject: Re: Freedman-Donaldson Theorem
Date: 10 Sep 92 23:20:53 GMT
Organization: U of Cambridge, England

In article <640034@otter.hpl.hp.com>, sec@otter.hpl.hp.com (Simon Crouch) writes:

> Well, a reasonable place to start is (a) Donaldson and Kronheimer's book
> "The geometry of four manifolds" and (b) Freedman and Quinn's book
> "The topology of four manifolds". (Sorry if the titles are inaccurate
                                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Hmm. I think you really do need the hyphen in "four-manifolds"...
(I owe this joke to W B R Lickorish, who ought to know)

-- 
Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
From: clong@romulus.rutgers.edu (Chris Long)
Newsgroups: sci.math
Subject: Re: What's going on here ???
Date: 15 Sep 92 10:35:03 GMT
Organization: Rutgers Univ., New Brunswick, N.J.

I read an article on just this series once, and *many* different
approaches were given that ended up yielding the same answer (the
one you found).  I believe it appeared in the Monthly during the
60s, but I can't recall which issue, sorry.
-- 
Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618
From: koiran@ens-lyon.fr (Pascal Koiran)
Newsgroups: sci.math
Subject: decidability and dynamical systems
Date: 8 Sep 92 11:12:05 GMT
Reply-To: koiran@ens-lyon.fr
Organization: Ecole Normale Superieure de Lyon

Hello,

Can someone provide a solution to the following problem, or give references
to related work in the litterature ?

Let f:[0,1]-->[0,1] be a continuous piecewise-linear function (with a finite
number of laps). The endpoints of the laps have rational coordinates.
Given such an f and a rational x \in [0,1], is it decidable whether a fixed
point is reached in finite time when f is iterated on x ?
In other words, is it decidable whether there exists t, f^t(x)=f^{t+1}(x) ?

One can ask the same question for other classes of non-linear functions,
such as polynomials, rational functions, ...

Thanks,

Pascal.
From: wjh@cbnewsl.cb.att.com (william.j.hery)
Newsgroups: sci.math
Subject: Re: Abel
Date: 5 Sep 92 04:18:59 GMT
Organization: AT&T

With all these postinga about Abel, I can't help but mention that on a trip
to Oslo recently I discovered that there is a statue of Abel (labeled only
ABEL) near the royal residence there; a guide book (Berlitz) confirms that
it is actually the mathematician Abel.

Now I think its great to have a statue of a "pure" mathematician in such
a prominent place (does anyone know of any others?)--and to have post
cards of the statue to send to mathematician friends (which I did)--
but the way he was portrayed seemed pretty odd to me: with a fierce
look on his face, stark naked, standing over a couple of other bodies in
apparant victory. Does anyone know the story of the this sculpture
and why he is portrayed that way? BTW, the sculpture is by the great Norwegian
sculptor Viegland, whose works form the heart of Froggner Park in Oslo
in a truely wonderful series of bronze and stone larger-than-life
pieces which portray the human condition in many interesting ways.

Bill Hery
AT&T Bell Labs
201-386-2362
hery@att.COM
Newsgroups: sci.math
From: arnold@cs.toronto.edu (Arnold Rosenbloom)
Subject: Foundational issues
Organization: Department of Computer Science, University of Toronto
Distribution: na
Date: 12 Sep 92 14:19:54 GMT

I have been reading a book on number theory and one on set theory and
have the following questions.

First the number theory text assumes the Peano Axioms, now if we
view these axioms as the specification of a particular set, how
do we know that we have a well defined system. For example, the Peano
axioms assume the existence of a successor function that behaves in a certain
way. How do we know there is a subset of NxN which has the required properties.

The other side (set theory) of the coin also presents some problems. 
THat is, the natural
numbers are 'defined' as 0={}, 1={0}, 2={0,1}, ... , n+1={0,...,n}.
But this looks like an inductive definition. So how can you make an inductive
definition (and hope it makes sense) without the natural number system already
there to prove that you have actually defined something?

Thanks
Arnold Rosenbloom
From: kriman@acsu.buffalo.edu (Alfred M. Kriman)
Newsgroups: sci.math
Subject: Re: Tiling sphere by triangles (Re: 3 space terahedron-packing)
Summary: Two errata corrected.
Date: 13 Sep 92 00:04:39 GMT
Organization: UB

In article <BuGKn5.Lnt@acsu.buffalo.edu> kriman@acsu.buffalo.edu
(I, Alfred M. Kriman) answered a query of goodman@bright.uoregon.edu
(Albert Goodman) in article <1992Sep11.182727.28044@nntp.uoregon.edu>,
whom I thank for pointing out an error in my posting.

I was sloppy in my response.  Two errors are noted below:
>
>   It may provide insight into the problem to recognize that regular
>spherical polygons of different sizes cannot be congruent.  The reason
I should have written something like "similar" ->^^^^^^^^^.  The point
is that scaling the lengths of a spherical polygon yields a spherical
polygon which lies in the surface of a scaled (i.e., different-radius)
sphere.  This does not yield a new tiling for the original sphere, it
just yields a similar tiling for a different sphere.
>
>   More specifically, the sum of the exterior angles of a spherical
>triangle (in radians) is pi plus the angular area of the triangle (in
>steradians).             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Wrong.  I should have written TWO times pi, MINUS the angular area ...
For small triangles one recovers the Euclidean value 2*pi.  For very large
triangles that cover nearly the whole sphere, one obtains -2*pi, but the
convention of "exterior" angle yields minus the intuitive values, so all
is well.
From: petry@pythagoras.math.washington.edu (David Petry)
Newsgroups: sci.math
Subject: Re: Why don't we split the group?
Date: 6 Sep 92 23:29:44 GMT
Article-I.D.: u.1992Sep6.232944.20285
Organization: University of Washington, Mathematics, Seattle

In article <4066@svin09.info.win.tue.nl> pwk@win.tue.nl writes:

>I would like to see:
>sci.math.coding        (with error correcting/cryptology/information theory)
>sci.math.group         (group theory)
>sci.math.misc          (whatever...)
>sci.math.puzzles       (well, puzzles appear sometimes)
>and many more.

Let us not forget sci.math.humor     :-)


David Petry
From: reus@klein.euromath.dk (Jens Peter Reus Christensen)
Newsgroups: sci.math
Subject: Re: nth prime
Date: 11 Sep 92 10:05:18 GMT
Organization: University of Copenhagen, Dept. of Math.

In article <1992Sep10.190905.10741@waikato.ac.nz> bill@waikato.ac.nz writes:

   
   Sorry to ask such a FAQ, but what's the quickest algorithm to
   find the nth prime? Is it O(nlogn) or something else?

   Bill Teahan,
   Systems Programmer,
   University of Waikato,
   Hamilton, New Zealand
***
The nth prime divided by  n*log(n) converges to 1 !! There is no
simple closed formula for the nth prime known but likely an ocean
of algoritms.

--
|--------------------------------------------------------------------------|
|  Jens Peter Reus Christensen   |                                         |
|  Associate professor, Dr. Phil.|                                         |
|  Department of mathematics     | e-mail:          reus@math.ku.dk        |
|  University of Copenhagen      |                                         |
|  Universitetsparken 5          | phone:           +45 3135 3133 ext. 458 |
|  DK-2100 Copenhagen            | fax:                      +45 3135 4254 |
|--------------------------------------------------------------------------|
|  Disclaimer: Except when explicitly stated otherwise any message         |
|  with this signature is the authors purely private responsibility.       | 
|--------------------------------------------------------------------------|
|  Motto : For everyone who has will be given more, and he will have       |
|  an abundance. Whoever does not have, even what he has will be taken     |
|  from him.  Matthew principle - Matth.Ch.25 v.29                         |
|--------------------------------------------------------------------------|
From: andrew@rentec.com (Andrew Mullhaupt)
Newsgroups: sci.math
Subject: Re: Proof of God's Existence
Date: 6 Sep 92 00:28:31 GMT
Organization: Renaissance Technologies Corp., Setauket, NY.

In article <1992Sep1.215331.89956@vaxc.cc.monash.edu.au> kevin@vaxc.cc.monash.edu.au writes:

	[Doubts about the possibility of proving existence of God deleted...]

>Asides from limitations in the expressive power of mathematics, the following
>will show any proof of the ontic status of God futile.
>1. It is possible to imagine a world, completely agreeing with the current one
>on all sensory data, in which God exists. 

Although you got all the theists and agnostics on board with you here, the
"hard atheists" are split on this issue. Some would assert that it is not
possible to imagine this, since they hold that the existence of God would have
certain consequences which are not observed.

>2. It is possible to imagine a world, completely agreeing with the current one
>on all sensory data, in which God doesn't exists.

Symmetric with the first claim, there are theists who can't swallow this one...

>Then the existence of these epistemically indistinguishable worlds proves that
>any ontological statement about God is INDEPENDENT of any epistemically 
>knowable axioms on the real world.

Now you get it from both sides - you claimed it was possible to imagine these
worlds, but what you want to use is that they exist. It is hard to think of
lots of people who can agree with this strong condition. Even so, if both
of these worlds exist, then God exists, which contradicts undecidability.

Your argument seems to be that there is no way to know which of these imaginable
outcomes corresponds to reality. But this is your conclusions, too...

Later,
Andrew Mullhaupt
From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
Newsgroups: sci.math
Subject: Re: What about 3.4 dimension?
Date: 11 Sep 92 14:13:32 GMT
Organization: U of Cambridge, England

In article <1992Sep10.235019.834@infodev.cam.ac.uk>, I wrote:

>  Example: That famous "snowflake" thing you get as follows: The first "stage"
>  is just an equilateral triangle. The second is obtained by gluing on a 1/3-size
>  equilateral triangle onto the outside of each side of the triangle; this looks
>  like a Star of David. The third is obtained by gluing on a 1/9-size triangle
>  to the outside of each line segment making up the new figure. And so on, adding
>  more and smaller triangles every time.
>  If you think of this as a "filled-in" shape, it has dimension 2. (This is easy
>  to prove.) But what about the boundary? That actually has dimension 4/3, and
                                                             ^^^^^^^^^^^^^
NO NO NO NO!!! Wrong! I beg your collective pardon; I should have said
log 4/log 3. (But the idea is the important thing.)

-- 
Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
From: luzeaux@liszt.berkeley.edu (Dominique Luzeaux)
Newsgroups: sci.math
Subject: Re: measures of the `size' of infinite sets
Date: 9 Sep 92 00:36:34 GMT
Reply-To: luzeaux@liszt.berkeley.edu (Dominique Luzeaux)
Organization: University of California, Berkeley

In article <1992Sep8.134624.11005@newstand.syr.edu>,
hgraber@lynx.cat.syr.edu (Harry Graber) writes:
|> have been devised for the size of an infinite set.  Some of these measures
|> give a different result, and agree with our `intuitive' position that
the set
|> of multiples of 29 is in some definite sense smaller than the set of numbers
|> that are not multiples of 29.

Do you want a measure (i.e. positive, completely additive), or a way to agree
with your intuitive position. In that latter case, density is the answer.
The set of multiples of 29 will have a density 29 times smaller than the set of
integers.
Other ways of separating ``large'' sets from ``small'' sets, when they have the
same cardinality, can be by their topological properties; that leads for
instance
to categorical considerations. In fact measure and category are two of the most
used manners to see whether a set is small or large. Unfortunately (or
fortunately) there are sets which are large in one sense and small in an
other one; although it has been shown that a homeomorphism could be
built between zero measure sets and first category sets.

	Dominique Luzeaux
Newsgroups: sci.math
From: N51L5201@ncsuvm.cc.ncsu.edu (David Auerbach)
Subject: Re: measures of the `size' of infinite sets
Organization: North Carolina State University
Date: Sat, 12 Sep 1992 15:18:19 GMT

In article <1992Sep8.134624.11005@newstand.syr.edu>
hgraber@lynx.cat.syr.edu (Harry Graber) writes:
 
>     I am familiar with the method devised by Cantor for comparing the card-
>inality of two infinite sets.  Suppose I divide all the positive integers into
>two sets, one consisting of all numbers that are multiples of 29, and the other
>containing all the rest (I have no special reason for choosing the number 29,
>except that it is >2).  There is no doubt but that a one-to-one correspon-
>dence can be established between these sets, so they are commensurable. Accord-
>ing to Cantor, then, both sets are the same size.
>
>     An associate of mine here tells me that there are other measures that
>have been devised for the size of an infinite set.  Some of these measures
>give a different result, and agree with our `intuitive' position that the set
>of multiples of 29 is in some definite sense smaller than the set of numbers
>that are not multiples of 29.  However, this is an area neither of us has
>specialized in.  I never knew that these other measures even existed, and he
>had heard of them but is not able to tell me what any of them is.  Will you
>kind and sagacious folks out there please send some enlightenment my way?
>
>--H. Graber
There is a dissertation by Fred M. Katz, written for the MIT Dept. of Linguisti
cs and Philosophy in the late seventies that is all about precisely this
problem: i.e. giving a coherent notion of size that repects those "other"
intuitions.
Newsgroups: sci.math
From: cyeomans@ms.uky.edu (Charles Yeomans)
Subject: Re: Godel and the US constitution
    <1992Sep3.114520.21990@ms.uky.edu> <185vavINNdgn@hilbert.math.ksu.edu>
Date: Mon, 7 Sep 1992 17:43:59 GMT
Organization: University Of Kentucky, Dept. of Math Sciences

In article <185vavINNdgn@hilbert.math.ksu.edu> bennett@math.ksu.edu (Andy Bennett) writes:
>cyeomans@ms.uky.edu (Charles Yeomans) writes:
>>The Constitution explicitly gives the president the power to suspend
>>habeas corpus when martial law has been declared.  But the army has no
>>such power unless the president himself calls for it.
>
>Actually, the constitution explicitly gives Congress the power to suspend
>habeas corpus (It is subsection 3 of Section 9 of Article I dealing with
>Legislative authority. Presidential authority is dealt with in Article II)
>On this basis the supreme court ruled Lincoln's suspension of habeas corpus
>unconstitutional during the Civil war. Lincoln supposedly remarked that since
>it was the supreme court's ruling, they could enforce it and continued to
>deny habeas corpus. The army mainly used the suspension of habeas corpus
>to lock up Marylanders who advocated seccession. Early in the Civil war it
>appeared Maryland would secede. Since that would have placed Washington DC
>between two states of the confederacy, it would have been a catastrophe for
>Lincoln and the north. Therefore he overstepped his authority to prevent it.
>Maryland's state song refers to "the tyrant" meaning Lincoln for his actions.
>
>Now that I've had a turn too, can we get back to mathematics?
>
You're not perfectly correct, but you're a hell of a lot closer than I 
was.  AFter Allan Adler suggested that I might be a bit off the mark, 
I consulted the document itself and then my wife, who is a law professor
in her spare time.  She pointed out that that the mention of habeas corpus
is in Article I, section 9.  She also said that Congress is not explicitly
given the power to suspend habeas corpus, but that that power is explicitly
taken away from them in most cases.  My wife assures me that this is
different than COngress being given explicitly the power to suspend
HC.  

I have been ordered to reread the constitution as penance for my bad
memory.

Charles Yeomans
cyeomans@ms.uky.edu
yeomans@austin.onu.edu

Newsgroups: sci.math,comp.lang.misc,comp.lang.fortran,comp.std.c,comp.lang.c
From: peter@ferranti.com (peter da silva)
Subject: Re: Scientists as Programmers (was Re: Small Language Wanted)
Organization: Xenix Support, FICC
Date: Fri, 11 Sep 1992 13:57:28 GMT

In article <a_rubin.716152347@dn66> a_rubin@dsg4.dse.beckman.com (Arthur Rubin) writes:
> In <id.I12T.GP4@ferranti.com> peter@ferranti.com (peter da silva) writes:
> >	int a, b;
> >	long c;

> >	c = a * b;

> Aside from there being no guarantee that "long" is longer than "int",

Yes, blame the authors of the first VAX compilers for that.

> I
> don't think it is LEGAL for ANSI C to do this,

I've seen people make this claim before; but I've yet to see a good
explanation. Care to try?
-- 
Peter da Silva                                               `-_-'
Ferranti Intl. Ctls. Corp.                                    'U` 
Sugar Land, TX  77487-5012
+1 713 274 5180                                   Har du kramat din varg idag?