How about Hilbert's squarefill evaluated with a fixed, irrational step size? gosper.org/hilbrand.png --rwg --I like that. I had the idea (did I post it?) another time of integrating high-dimensional functions by regarding them as 1D integrals along a spacefilling curve... which hopefully would work better than plain monte-carlo integration. One could also "adapt" rather easily using that approach. Is the nearest-neighbor distance-distribution different for this kind of point set, than for random points? (I presume yes, but can see that arbitrarily small distances still do occur.) On 11/13/13, math-fun-request@mailman.xmission.com <math-fun-request@mailman.xmission.com> wrote:
Send math-fun mailing list submissions to math-fun@mailman.xmission.com
To subscribe or unsubscribe via the World Wide Web, visit http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun or, via email, send a message with subject or body 'help' to math-fun-request@mailman.xmission.com
You can reach the person managing the list at math-fun-owner@mailman.xmission.com
When replying, please edit your Subject line so it is more specific than "Re: Contents of math-fun digest..."
Today's Topics:
1. Re: math-fun Digest, Vol 129, Issue 12 (Warren D Smith) 2. Re: density of primorial+1 primes (Bill Gosper) 3. Re: density of primorial+1 primes (rcs@xmission.com) 4. Re: density of primorial+1 primes (Bill Gosper) 5. good deterministic algorithmic point sets without repeated distances? (Warren D Smith) 6. Re: good deterministic algorithmic point sets without repeated distances? (meekerdb)
----------------------------------------------------------------------
Message: 1 Date: Mon, 11 Nov 2013 22:09:36 -0500 From: Warren D Smith <warren.wds@gmail.com> To: math-fun@mailman.xmission.com Subject: Re: [math-fun] math-fun Digest, Vol 129, Issue 12 Message-ID: <CAAJP7Y3LB8Rb=hFMqwdqi8myvLzwm+kPzn1mDrMr8u+bCPPqrw@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1
I'm curious: Can one state in closed form what is the asymptotic density of prime numbers among numbers Q(n) of the form
Q(n) := primorial(n) + 1
i.e.,
Q(n) = 2*3*5*7*...*p_n + 1
(where p_n is the nth prime) ???
--I would think that Q(n) is prime with "probability" about loglog(Q(n)) times greater than the usual 1/log(Q(n)) probability.
------------------------------
Message: 2 Date: Tue, 12 Nov 2013 11:56:48 -0800 From: Bill Gosper <billgosper@gmail.com> To: math-fun@mailman.xmission.com Subject: Re: [math-fun] density of primorial+1 primes Message-ID: <CAA-4O0FvpLthgQeVHFkWsB86iHYrsMMRhn_pfLZoogR5E4uAhw@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1
DanA>
I'm curious: Can one state in closed form what is the asymptotic density of prime numbers among numbers Q(n) of the form
Q(n) := primorial(n) + 1
i.e.,
Q(n) = 2*3*5*7*...*p_n + 1
(where p_n is the nth prime) ???
CG>It's not even known that there are infinitely many. Caldwell & Gallot conjecture that there are about e^gamma * log x prime Q(n) with n <= x, that is, that the usual heuristic gives the right answer.
I think sieve theory can give an upper bound if that's enough for your purposes.
Charles Greathouse
WDS>--I would think that Q(n) is prime with "probability" about loglog(Q(n)) times greater than the usual 1/log(Q(n)) probability. [Warren]
Only slightly less infeasible might be the coprime sequence A000058 (interesting comments). In[10]:= NestList[#^2 - # + 1 &, 2, 9]
Out[10]= {2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443, 12864938683278671740537145998360961546653259485195807, 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443}
In[8]:= N[Timing[Nest[#^2 - # + 1 &, 2, 21]]]
Out[8]= {0.007302, 1.853733657356281*10^426880}
(Half a million digits in 7ms?)
In[6]:= TimeConstrained[PrimeQ[#], 1] & /@ NestList[#^2 - # + 1 &, 2, 21]
Out[6]= {True, True, True, True, False, True, False, False, False, False, False, False, False, False, False, False, False, False, $Aborted, $Aborted, False, $Aborted}
where $Aborted almost certainly means True. Changing the timeout from 1 to 288 sec did zilch. Decertifying a_20 In[9]:= Timing[PrimeQ[Nest[#^2 - # + 1 &, 2, 20]]]
Out[9]= {0.150525, False}
took < 1/6 sec. Can we show there are no (strong?) pseudoprimes of this form?
--rwg
SUPERIMPOSED
PSEUDOPRIMES
------------------------------
Message: 3 Date: Tue, 12 Nov 2013 13:17:42 -0700 From: rcs@xmission.com To: math-fun@mailman.xmission.com Subject: Re: [math-fun] density of primorial+1 primes Message-ID: <20131112131742.s0v082qagck4s4wg@webmail.xmission.com> Content-Type: text/plain; charset=ISO-8859-1; DelSp="Yes"; format="flowed"
I'll guess that the False value for a_20 is from some small factor, and that the Aborted values are because the test ran out of time before completing even one superimposed test. Try asking for a few digits of 2^(a_12) (mod a_12), and then see how far you can get with a_13 ... before running out of gas.
Rich
--------- Quoting Bill Gosper <billgosper@gmail.com>: <eliding earlier comments --rich>
Only slightly less infeasible might be the coprime sequence A000058 (interesting comments). In[10]:= NestList[#^2 - # + 1 &, 2, 9]
Out[10]= {2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443, 12864938683278671740537145998360961546653259485195807, 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443}
In[8]:= N[Timing[Nest[#^2 - # + 1 &, 2, 21]]]
Out[8]= {0.007302, 1.853733657356281*10^426880}
(Half a million digits in 7ms?)
In[6]:= TimeConstrained[PrimeQ[#], 1] & /@ NestList[#^2 - # + 1 &, 2, 21]
Out[6]= {True, True, True, True, False, True, False, False, False, False, False, False, False, False, False, False, False, False, $Aborted, $Aborted, False, $Aborted}
where $Aborted almost certainly means True. Changing the timeout from 1 to 288 sec did zilch. Decertifying a_20 In[9]:= Timing[PrimeQ[Nest[#^2 - # + 1 &, 2, 20]]]
Out[9]= {0.150525, False}
took < 1/6 sec. Can we show there are no (strong?) pseudoprimes of this form?
--rwg
SUPERIMPOSED
PSEUDOPRIMES _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
Message: 4 Date: Tue, 12 Nov 2013 16:21:29 -0800 From: Bill Gosper <billgosper@gmail.com> To: math-fun@mailman.xmission.com Subject: Re: [math-fun] density of primorial+1 primes Message-ID: <CAA-4O0H1FR1Ubvj8Fn=tQcs3faNfq9OEB3r57YbfBens7VRzbw@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1
RCS>
I'll guess that the False value for a_20 is from some small factor, and that the Aborted values are because the test ran out of time before completing even one superimposed test. Try asking for a few digits of 2^(a_12) (mod a_12), and then see how far you can get with a_13 ... before running out of gas.
Rich
---------
I lose; you win: In[11]:= PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 12]
Out[11]= 3366937412175501591717367777101460820640224690509113100163277\ 6539067634240985481258893779792671452248127456725155260727280357834657\ 6076738692420210769091266874710826881662611178920169012031118635505607\ 4310982786125119105965083788824019629431580952133240830246962982908185\ 9746496798634116562354568928408751636377986351524509214103104546223261\ 2396128362132130189597314029272968730759961945103880790832377276137373\ 9360515945586462465327970571098621823207535551580401784234812938313843\ 6459926693612089970288170337138209267562435148320741084111322614415098\ 1287168301351535936792810718614137830956322091599451719533327897728719\ 2022822793035110202282332960887794400493112644185559756058506634629406\ 8091290492788783650041163770989366969890285626688901808066658454549560\ 7443533211603079106672889774858913012113951640476740718704380411099010\ 204
In[13]:= PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 6]
Out[13]= 4457343787994
(Note: a_0:=2 .)
In[14]:= PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 5]
Out[14]= 2
In[16]:= PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 4]
Out[16]= 1103
In[17]:= PowerMod[3, #, #] &@Nest[#^2 - # + 1 &, 2, 5]
Out[17]= 3
In[18]:= PowerMod[8, #, #] &@Nest[#^2 - # + 1 &, 2, 5]
Out[18]= 8
In[12]:= Timing[N[PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 13]]]
Out[12]= {0.105467, 2.415419924381151*10^1667}
In[19]:= Timing[N[PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 14]]]
Out[19]= {0.647739, 7.344539857481122*10^3334}
In[20]:= Timing[N[PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 15]]]
Out[20]= {3.835341, 6.597333832436021*10^6669}
In[21]:= Timing[N[PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 16]]]
Out[21]= {21.430643, 1.412908137918137*10^13339}
In[22]:= Timing[N[PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 17]]]
Out[22]= {119.182441, 8.856579016766857*10^26679}
In[23]:= Timing[N[PowerMod[2, #, #] &@Nest[#^2 - # + 1 &, 2, 18]]]
Out[23]= {576.777472, 7.425006686698617*10^53359}
In[24]:= Timing[PrimeQ[Nest[#^2 - # + 1 &, 2, 18]]]
Out[24]= {577.039477, False}
In[25]:= Timing[PrimeQ[Nest[#^2 - # + 1 &, 2, 19]]] should take about an hour. Meanwhile, we can now conjecture, as with Fermat #s, that there are no more of these primes! --rwg Quoting Bill Gosper <billgosper@gmail.com>: <eliding earlier comments --rich>
Only slightly less infeasible might be the coprime sequence A000058 (interesting comments). In[10]:= NestList[#^2 - # + 1 &, 2, 9] Out[10]= {2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443, 12864938683278671740537145998360961546653259485195807, 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443} In[8]:= N[Timing[Nest[#^2 - # + 1 &, 2, 21]]] Out[8]= {0.007302, 1.853733657356281*10^426880} (Half a million digits in 7ms?) In[6]:= TimeConstrained[PrimeQ[#], 1] & /@ NestList[#^2 - # + 1 &, 2, 21] Out[6]= {True, True, True, True, False, True, False, False, False, False, False, False, False, False, False, False, False, False, $Aborted, $Aborted, False, $Aborted} where $Aborted almost certainly means True. Changing the timeout from 1 to 288 sec did zilch. Decertifying a_20 In[9]:= Timing[PrimeQ[Nest[#^2 - # + 1 &, 2, 20]]] Out[9]= {0.150525, False} took < 1/6 sec. Can we show there are no (strong?) pseudoprimes of this form? --rwg
SUPERIMPOSED PSEUDOPRIMES <disformatting earlier comments --Firefox>
------------------------------
Message: 5 Date: Wed, 13 Nov 2013 00:16:49 -0500 From: Warren D Smith <warren.wds@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] good deterministic algorithmic point sets without repeated distances? Message-ID: <CAAJP7Y2mMwA54-adLHnnUs-R8z6Ju4octFC8_XjxpaSHWyuVfg@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1
In the plane (or some other low dimensional space) I want a good infinite point set that has "density 1."
What does "good" mean? Well, "more uniform than random" in some vague sense, such as sphere packing, sphere covering, and providing good estimates of integrals via sums.
BUT, what I also want, is the set has no repeated distances. So lattices are undesirable. Random point sets will not repeat a distance (with probability 1) so they are great, except they fail to be good in the sense of the previous paragraph, while lattices can be quite good in that sense.
Another thing I want is an easy, algorithmic description of the point set, and it should be deterministic.
The question is how to get the best of both worlds.
I admit, I am being vague here. Ideas are solicited.
------------------------------
Message: 6 Date: Tue, 12 Nov 2013 21:45:25 -0800 From: meekerdb <meekerdb@verizon.net> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] good deterministic algorithmic point sets without repeated distances? Message-ID: <528311F5.3070308@verizon.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
How about lattice points plus small random vectors.
Brent
On 11/12/2013 9:16 PM, Warren D Smith wrote:
In the plane (or some other low dimensional space) I want a good infinite point set that has "density 1."
What does "good" mean? Well, "more uniform than random" in some vague sense, such as sphere packing, sphere covering, and providing good estimates of integrals via sums.
BUT, what I also want, is the set has no repeated distances. So lattices are undesirable. Random point sets will not repeat a distance (with probability 1) so they are great, except they fail to be good in the sense of the previous paragraph, while lattices can be quite good in that sense.
Another thing I want is an easy, algorithmic description of the point set, and it should be deterministic.
The question is how to get the best of both worlds.
I admit, I am being vague here. Ideas are solicited.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
----- No virus found in this message. Checked by AVG - www.avg.com Version: 2014.0.4158 / Virus Database: 3629/6830 - Release Date: 11/12/13
------------------------------
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
End of math-fun Digest, Vol 129, Issue 13 *****************************************
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)