[math-fun] Prob. that 2 numbers relatively prime, error term?
A018805(n) is no. of pairs (x,y) in [1..n]X[1..n] with gcd(x,y)=1. It is ~ 6*n^2/Pi^2 + C*n*log n, I think. What is C, and how can one find it using Mathematica or some other program? I ask because there are several similar sums I am interested in. Is there a reference? Background: A331755 has an explicit formula (involving A018805) and is ~ 9*n^4/(8*Pi^2) + O(n^3 log n). A331763 is a mystery that I would love to solve, and seems to be ~ constant*n^4/Pi^2. Maybe knowing the second terms in the asymptotic expansions would help with the curve-fitting.
On 15/07/2020 16:59, Neil Sloane wrote:
A018805(n) is no. of pairs (x,y) in [1..n]X[1..n] with gcd(x,y)=1. It is ~ 6*n^2/Pi^2 + C*n*log n, I think. What is C, and how can one find it using Mathematica or some other program? I ask because there are several similar sums I am interested in. Is there a reference?
According to an answer to https://math.stackexchange.com/questions/64498/probability-that-two-random-n... Mertens proved in 1874 that the error is O(n log n); Walfisz proved in 1963 that it's O(n (log n)^2/3 (log log n)^1/3); Chowla and Pillai proved in 1930 that it isn't o(n log log log n) and that the sum of the error terms for n=1, ..., n=N is asymptotically 3/pi^2 N^2; that Montgomery proved in 1987 that the error is infinitely often at least of order n sqrt(log log n). More details from the author of that answer at https://enaslund.wordpress.com/2012/01/15/the-sum-of-the-totient-function-an... So it looks as if C=0 and the actual magnitude of the error term isn't fully known. -- g
I found this article really interesting. It suggests that real numbers are, from the perspective of the universe, not real. https://www.quantamagazine.org/does-time-really-flow-new-clues-come-from-a-c...
Here's a paper which gives a recent survey of such things: https://hal.archives-ouvertes.fr/hal-02585977/document . According to that paper the best result for the remainder that Neil asks about is due to Cohen and Dress https://projecteuclid.org/download/pdf_1/euclid.facm/1229618741 Basically the remainder is O(sqrt(n)), with the constant in the O, 0.02767 for n >= 438653 Victor On Wed, Jul 15, 2020 at 12:48 PM Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 15/07/2020 16:59, Neil Sloane wrote:
A018805(n) is no. of pairs (x,y) in [1..n]X[1..n] with gcd(x,y)=1. It is ~ 6*n^2/Pi^2 + C*n*log n, I think. What is C, and how can one find it using Mathematica or some other program? I ask because there are several similar sums I am interested in. Is there a reference?
According to an answer to
https://math.stackexchange.com/questions/64498/probability-that-two-random-n... Mertens proved in 1874 that the error is O(n log n); Walfisz proved in 1963 that it's O(n (log n)^2/3 (log log n)^1/3); Chowla and Pillai proved in 1930 that it isn't o(n log log log n) and that the sum of the error terms for n=1, ..., n=N is asymptotically 3/pi^2 N^2; that Montgomery proved in 1987 that the error is infinitely often at least of order n sqrt(log log n).
More details from the author of that answer at
https://enaslund.wordpress.com/2012/01/15/the-sum-of-the-totient-function-an...
So it looks as if C=0 and the actual magnitude of the error term isn't fully known.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sorry, This last thing was about a related problem -- the remainder for the number of square free integers <= n. On Wed, Jul 15, 2020 at 1:30 PM Victor Miller <victorsmiller@gmail.com> wrote:
Here's a paper which gives a recent survey of such things: https://hal.archives-ouvertes.fr/hal-02585977/document . According to that paper the best result for the remainder that Neil asks about is due to Cohen and Dress https://projecteuclid.org/download/pdf_1/euclid.facm/1229618741
Basically the remainder is O(sqrt(n)), with the constant in the O, 0.02767 for n >= 438653
Victor
On Wed, Jul 15, 2020 at 12:48 PM Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 15/07/2020 16:59, Neil Sloane wrote:
A018805(n) is no. of pairs (x,y) in [1..n]X[1..n] with gcd(x,y)=1. It is ~ 6*n^2/Pi^2 + C*n*log n, I think. What is C, and how can one find it using Mathematica or some other program? I ask because there are several similar sums I am interested in. Is there a reference?
According to an answer to
https://math.stackexchange.com/questions/64498/probability-that-two-random-n... Mertens proved in 1874 that the error is O(n log n); Walfisz proved in 1963 that it's O(n (log n)^2/3 (log log n)^1/3); Chowla and Pillai proved in 1930 that it isn't o(n log log log n) and that the sum of the error terms for n=1, ..., n=N is asymptotically 3/pi^2 N^2; that Montgomery proved in 1987 that the error is infinitely often at least of order n sqrt(log log n).
More details from the author of that answer at
https://enaslund.wordpress.com/2012/01/15/the-sum-of-the-totient-function-an...
So it looks as if C=0 and the actual magnitude of the error term isn't fully known.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There's also the paper arxiv:1612.03700 "The probability that two random integers are coprime" which relates the best remainder to the RH. On Wed, Jul 15, 2020 at 12:00 PM Neil Sloane <njasloane@gmail.com> wrote:
A018805(n) is no. of pairs (x,y) in [1..n]X[1..n] with gcd(x,y)=1. It is ~ 6*n^2/Pi^2 + C*n*log n, I think. What is C, and how can one find it using Mathematica or some other program? I ask because there are several similar sums I am interested in. Is there a reference?
Background: A331755 has an explicit formula (involving A018805) and is ~ 9*n^4/(8*Pi^2) + O(n^3 log n). A331763 is a mystery that I would love to solve, and seems to be ~ constant*n^4/Pi^2. Maybe knowing the second terms in the asymptotic expansions would help with the curve-fitting. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Dave Dyer -
Gareth McCaughan -
Neil Sloane -
Victor Miller