[math-fun] number theory puzzle about squarefree number density
From: Victor Miller <victorsmiller@gmail.com>
Here's some answers (in addition you should look at Sol Golomb's Puzzle column in the Dec 2011 issue of the IEEE Information Theory Society Newsletter: http://www.itsoc.org/publications/newsletters/nits_NL_1211-Web.pdf/view which has a bunch of problems like this in even greater generality).
--thanks, Miller's were the solutions I had in mind, though I was not aware of Golomb column. In fact I'm still not aware of it since my computer refuses to open the pdf file, says it is "damaged." Anyway, I will now say what I worked out on this puzzle. If we choose n random uniformly from {1,2,...,N} in limit N-->infinity, then probability that the j-tuple n, n-1, n-2 ..., n+1-J (for some fixed J>=1) all are simultaneously free of Kth powers (for some fixed K>=2) is prf(J,K) = prod(primes p) (1 - J / p^K) or in MAPLE notation prf := (J,K,N) -> product( 1 - J / ithprime(m)^K, m=1..N ); in the limit N-->infinity. This is rigorous since the "probabilistic independence" is a rigorously valid statement in this case (e.g. see M.Kac's book if you don't understand what I mean by that). In the case J=1 we get prf(1,K) = 1/RiemannZeta(K) so prf(1,2) = 6/Pi^2 = 0.6079271016. The problem I posed was prf(2,2)=0.32263405 as best I've been able to determine (computed up to the 16000th prime and extrapolation to infinity). Also, ct:=0; for n from 1+10^6 by -1 to 2 do if( issqrfree(n) and issqrfree(n-1) ) then ct:=ct+1; fi; od; print(ct); prints 322619. Unfortunately I do not have any closed forms or rapid-convergent expressions except in the J=1 cases, although it is possible (albeit it seems to be hurting not helping) to transform the product to an interesting sum. One might dream that some of the loveliness of the zeta function, such as reflection formula, Riemann-Siegel integral formula, etc, has analogs for the more general prf function. I have no evidence for that, but since the Zeta function is a special case you would have at least a foothold to try to work on that. And as Miller noted, the chance that either n OR n-1 (or both) is squarefree is 2*prf(1,2) - prf(2,2) = 0.89322015.
I got Victor's product too, but when I worked it out numerically I didn't find it in Plouffe's inverter. That seemed strange -- it being a naturally defined quantity -- so I worked harder at my extrapolation. With the assumption that the correction, upon terminating at the Nth prime, behaves as 1/(N (Log N)^2), I then got 0.3226340989 ... for N = 1739034. Another visit to the inverter then identified the number as the "Feller-Tornier Constant" and offered the following useful OEIS link: http://oeis.org/A001692/a001692.html Veit On Feb 4, 2012, at 10:09 AM, Warren Smith wrote:
From: Victor Miller <victorsmiller@gmail.com>
Here's some answers (in addition you should look at Sol Golomb's Puzzle column in the Dec 2011 issue of the IEEE Information Theory Society Newsletter: http://www.itsoc.org/publications/newsletters/nits_NL_1211-Web.pdf/view which has a bunch of problems like this in even greater generality).
--thanks, Miller's were the solutions I had in mind, though I was not aware of Golomb column. In fact I'm still not aware of it since my computer refuses to open the pdf file, says it is "damaged."
Anyway, I will now say what I worked out on this puzzle.
If we choose n random uniformly from {1,2,...,N} in limit N-->infinity, then probability that the j-tuple n, n-1, n-2 ..., n+1-J (for some fixed J>=1) all are simultaneously free of Kth powers (for some fixed K>=2) is prf(J,K) = prod(primes p) (1 - J / p^K) or in MAPLE notation prf := (J,K,N) -> product( 1 - J / ithprime(m)^K, m=1..N ); in the limit N-->infinity. This is rigorous since the "probabilistic independence" is a rigorously valid statement in this case (e.g. see M.Kac's book if you don't understand what I mean by that). In the case J=1 we get prf(1,K) = 1/RiemannZeta(K) so prf(1,2) = 6/Pi^2 = 0.6079271016.
The problem I posed was prf(2,2)=0.32263405 as best I've been able to determine (computed up to the 16000th prime and extrapolation to infinity). Also, ct:=0; for n from 1+10^6 by -1 to 2 do if( issqrfree(n) and issqrfree(n-1) ) then ct:=ct+1; fi; od; print(ct); prints 322619.
Unfortunately I do not have any closed forms or rapid-convergent expressions except in the J=1 cases, although it is possible (albeit it seems to be hurting not helping) to transform the product to an interesting sum. One might dream that some of the loveliness of the zeta function, such as reflection formula, Riemann-Siegel integral formula, etc, has analogs for the more general prf function. I have no evidence for that, but since the Zeta function is a special case you would have at least a foothold to try to work on that.
And as Miller noted, the chance that either n OR n-1 (or both) is squarefree is 2*prf(1,2) - prf(2,2) = 0.89322015.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 2/4/12, Warren Smith <warren.wds@gmail.com> wrote:
In fact I'm still not aware of it since my computer refuses to open the pdf file, says it is "damaged."
I had trouble with this phenomenon until I twigged that it happens when the PDF file has been generated with a newer version of the Adobe software, but the reader is an older version. Pity they couldn't just tell you that, isn't it? Adobe Acrobat Reader version 7.0.8 is compatible with the newer PDF files and the older operating systems that people like us are (for various reasons) stuck with. It can be downloaded from http://mac.oldapps.com/adobe_reader.php --- but it's a dreadful memory hog, compared with (say) version 5. Fred Lunnon
participants (3)
-
Fred lunnon -
Veit Elser -
Warren Smith