The referenced sequence records numbers whose largest prime factor falls short of the square root of the number. The graph of the sequence makes it clear that these numbers have a well-defined asymptotic density. Following a citation to HAKMEM 29 (Schroeppel), we find a claim equivalent to saying that this density is 1 - ln 2 ~ 0.30685 But empirically, the density looks considerably smaller, more like 0.27. The problem can't be whether or not to include exact squares of primes, because those have asymptotic density 0. We have one more reported reference, to Exercise 28 on p. 26 of Tenenbaum and Wu, Théorie analytique et probabiliste des nombres, solution on p. 34. But I don't have a copy, and my French isn't up to the task of understanding their solution. Can somebody check it and compare it with Schroeppel's result (which, typically for HAKMEM, is stated without proof)? Rich, do you remember your approach?
Allan, 1. There are two related sequences. If we call your A063539 the number of sqrt(n-1)-smooth numbers , then A295084 counts sqrt(n)-smooth numbers, and my A333534 counts log(n)-smooth numbers. I only added it two days ago - a strange coincidence? I am interested in smooth numbers because they seem to underlie A332580, for which I am trying to find an upper bound. 2. There is a book by Andrew Granville on Smooth Numbers - I found a copy on the web: http://math.utoledo.edu/~codenth/Spring_13/3200/NT-books/Smooth_Numbers-Comp... 3. Will it be OK if I add your comments about the question of the density of A63539 to that entry? Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Fri, Apr 10, 2020 at 4:59 PM Allan Wechsler <acwacw@gmail.com> wrote:
The referenced sequence records numbers whose largest prime factor falls short of the square root of the number.
The graph of the sequence makes it clear that these numbers have a well-defined asymptotic density.
Following a citation to HAKMEM 29 (Schroeppel), we find a claim equivalent to saying that this density is 1 - ln 2 ~ 0.30685
But empirically, the density looks considerably smaller, more like 0.27.
The problem can't be whether or not to include exact squares of primes, because those have asymptotic density 0.
We have one more reported reference, to Exercise 28 on p. 26 of Tenenbaum and Wu, Théorie analytique et probabiliste des nombres, solution on p. 34. But I don't have a copy, and my French isn't up to the task of understanding their solution. Can somebody check it and compare it with Schroeppel's result (which, typically for HAKMEM, is stated without proof)? Rich, do you remember your approach? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If we wait a few days, Neil, we might get some enlightenment from Rich or from somebody who can read that French math book. And then we'll have a much more substantive comment to add. (For example, suppose it turns out that Tenenbaum and Wu made a mistake in their solution to Exercise 28? That'll be a great example of OEIS-enabled math.) On Fri, Apr 10, 2020 at 6:15 PM Neil Sloane <njasloane@gmail.com> wrote:
Allan,
1. There are two related sequences. If we call your A063539 the number of sqrt(n-1)-smooth numbers , then A295084 counts sqrt(n)-smooth numbers, and my A333534 counts log(n)-smooth numbers. I only added it two days ago - a strange coincidence? I am interested in smooth numbers because they seem to underlie A332580, for which I am trying to find an upper bound.
2. There is a book by Andrew Granville on Smooth Numbers - I found a copy on the web:
http://math.utoledo.edu/~codenth/Spring_13/3200/NT-books/Smooth_Numbers-Comp...
3. Will it be OK if I add your comments about the question of the density of A63539 to that entry?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 4:59 PM Allan Wechsler <acwacw@gmail.com> wrote:
The referenced sequence records numbers whose largest prime factor falls short of the square root of the number.
The graph of the sequence makes it clear that these numbers have a well-defined asymptotic density.
Following a citation to HAKMEM 29 (Schroeppel), we find a claim equivalent to saying that this density is 1 - ln 2 ~ 0.30685
But empirically, the density looks considerably smaller, more like 0.27.
The problem can't be whether or not to include exact squares of primes, because those have asymptotic density 0.
We have one more reported reference, to Exercise 28 on p. 26 of Tenenbaum and Wu, Théorie analytique et probabiliste des nombres, solution on p.
But I don't have a copy, and my French isn't up to the task of understanding their solution. Can somebody check it and compare it with Schroeppel's result (which, typically for HAKMEM, is stated without proof)? Rich, do you remember your approach? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It occurs to me that there might be another explanation. When we consider 7-smooth numbers, there are 2 seqs, the list of 7-smooth numbers, and the number of them that are <= n But when we consider sqrt(n-1)-smooth numbers, there are 3 sequences: the list of the individual numbers, the number of sqrt(k-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<k and the number of sqrt(n-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<n The entries A295084 and A333534 that I mentioned are of the first type There are 2 different densities! Maybe that explains the confusion? Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Fri, Apr 10, 2020 at 6:23 PM Allan Wechsler <acwacw@gmail.com> wrote:
If we wait a few days, Neil, we might get some enlightenment from Rich or from somebody who can read that French math book. And then we'll have a much more substantive comment to add.
(For example, suppose it turns out that Tenenbaum and Wu made a mistake in their solution to Exercise 28? That'll be a great example of OEIS-enabled math.)
On Fri, Apr 10, 2020 at 6:15 PM Neil Sloane <njasloane@gmail.com> wrote:
Allan,
1. There are two related sequences. If we call your A063539 the number of sqrt(n-1)-smooth numbers , then A295084 counts sqrt(n)-smooth numbers, and my A333534 counts log(n)-smooth numbers. I only added it two days ago - a strange coincidence? I am interested in smooth numbers because they seem to underlie A332580, for which I am trying to find an upper bound.
2. There is a book by Andrew Granville on Smooth Numbers - I found a copy on the web:
http://math.utoledo.edu/~codenth/Spring_13/3200/NT-books/Smooth_Numbers-Comp...
3. Will it be OK if I add your comments about the question of the
density
of A63539 to that entry?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 4:59 PM Allan Wechsler <acwacw@gmail.com> wrote:
The referenced sequence records numbers whose largest prime factor falls short of the square root of the number.
The graph of the sequence makes it clear that these numbers have a well-defined asymptotic density.
Following a citation to HAKMEM 29 (Schroeppel), we find a claim equivalent to saying that this density is 1 - ln 2 ~ 0.30685
But empirically, the density looks considerably smaller, more like 0.27.
The problem can't be whether or not to include exact squares of primes, because those have asymptotic density 0.
We have one more reported reference, to Exercise 28 on p. 26 of Tenenbaum and Wu, Théorie analytique et probabiliste des nombres, solution on p.
But I don't have a copy, and my French isn't up to the task of understanding their solution. Can somebody check it and compare it with Schroeppel's result (which, typically for HAKMEM, is stated without proof)? Rich, do you remember your approach? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
oh, I forgot the square roots I should have said: the list of the individual numbers, the number of sqrt(k-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<sqrt(k) and the number of sqrt(n-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<sqrt(n) On Fri, Apr 10, 2020 at 7:29 PM Neil Sloane <njasloane@gmail.com> wrote:
It occurs to me that there might be another explanation.
When we consider 7-smooth numbers, there are 2 seqs, the list of 7-smooth numbers, and the number of them that are <= n
But when we consider sqrt(n-1)-smooth numbers, there are 3 sequences: the list of the individual numbers, the number of sqrt(k-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<k and the number of sqrt(n-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<n
The entries A295084 and A333534 that I mentioned are of the first type
There are 2 different densities! Maybe that explains the confusion?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 6:23 PM Allan Wechsler <acwacw@gmail.com> wrote:
If we wait a few days, Neil, we might get some enlightenment from Rich or from somebody who can read that French math book. And then we'll have a much more substantive comment to add.
(For example, suppose it turns out that Tenenbaum and Wu made a mistake in their solution to Exercise 28? That'll be a great example of OEIS-enabled math.)
On Fri, Apr 10, 2020 at 6:15 PM Neil Sloane <njasloane@gmail.com> wrote:
Allan,
1. There are two related sequences. If we call your A063539 the number of sqrt(n-1)-smooth numbers , then A295084 counts sqrt(n)-smooth numbers, and my A333534 counts log(n)-smooth numbers. I only added it two days ago - a strange coincidence? I am interested in smooth numbers because they seem to underlie A332580, for which I am trying to find an upper bound.
2. There is a book by Andrew Granville on Smooth Numbers - I found a copy on the web:
http://math.utoledo.edu/~codenth/Spring_13/3200/NT-books/Smooth_Numbers-Comp...
3. Will it be OK if I add your comments about the question of the
density
of A63539 to that entry?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 4:59 PM Allan Wechsler <acwacw@gmail.com> wrote:
The referenced sequence records numbers whose largest prime factor falls short of the square root of the number.
The graph of the sequence makes it clear that these numbers have a well-defined asymptotic density.
Following a citation to HAKMEM 29 (Schroeppel), we find a claim equivalent to saying that this density is 1 - ln 2 ~ 0.30685
But empirically, the density looks considerably smaller, more like 0.27.
The problem can't be whether or not to include exact squares of primes, because those have asymptotic density 0.
We have one more reported reference, to Exercise 28 on p. 26 of Tenenbaum and Wu, Théorie analytique et probabiliste des nombres, solution on p.
But I don't have a copy, and my French isn't up to the task of understanding their solution. Can somebody check it and compare it with Schroeppel's result (which, typically for HAKMEM, is stated without proof)? Rich, do you remember your approach? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Allan, There are now six versions of these sequences: The following are all different versions of sqrt(n)-smooth numbers: A048098, A063539, A064775, A295084, A333535, A333536. On Fri, Apr 10, 2020 at 7:31 PM Neil Sloane <njasloane@gmail.com> wrote:
oh, I forgot the square roots
I should have said:
the list of the individual numbers, the number of sqrt(k-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<sqrt(k) and the number of sqrt(n-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<sqrt(n)
On Fri, Apr 10, 2020 at 7:29 PM Neil Sloane <njasloane@gmail.com> wrote:
It occurs to me that there might be another explanation.
When we consider 7-smooth numbers, there are 2 seqs, the list of 7-smooth numbers, and the number of them that are <= n
But when we consider sqrt(n-1)-smooth numbers, there are 3 sequences: the list of the individual numbers, the number of sqrt(k-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<k and the number of sqrt(n-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<n
The entries A295084 and A333534 that I mentioned are of the first type
There are 2 different densities! Maybe that explains the confusion?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 6:23 PM Allan Wechsler <acwacw@gmail.com> wrote:
If we wait a few days, Neil, we might get some enlightenment from Rich or from somebody who can read that French math book. And then we'll have a much more substantive comment to add.
(For example, suppose it turns out that Tenenbaum and Wu made a mistake in their solution to Exercise 28? That'll be a great example of OEIS-enabled math.)
On Fri, Apr 10, 2020 at 6:15 PM Neil Sloane <njasloane@gmail.com> wrote:
Allan,
1. There are two related sequences. If we call your A063539 the number of sqrt(n-1)-smooth numbers , then A295084 counts sqrt(n)-smooth numbers, and my A333534 counts log(n)-smooth numbers. I only added it two days ago - a strange coincidence? I am interested in smooth numbers because they seem to underlie A332580, for which I am trying to find an upper bound.
2. There is a book by Andrew Granville on Smooth Numbers - I found a copy on the web:
http://math.utoledo.edu/~codenth/Spring_13/3200/NT-books/Smooth_Numbers-Comp...
3. Will it be OK if I add your comments about the question of the
density
of A63539 to that entry?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 4:59 PM Allan Wechsler <acwacw@gmail.com> wrote:
The referenced sequence records numbers whose largest prime factor falls short of the square root of the number.
The graph of the sequence makes it clear that these numbers have a well-defined asymptotic density.
Following a citation to HAKMEM 29 (Schroeppel), we find a claim equivalent to saying that this density is 1 - ln 2 ~ 0.30685
But empirically, the density looks considerably smaller, more like 0.27.
The problem can't be whether or not to include exact squares of primes, because those have asymptotic density 0.
We have one more reported reference, to Exercise 28 on p. 26 of Tenenbaum and Wu, Théorie analytique et probabiliste des nombres, solution on p.
But I don't have a copy, and my French isn't up to the task of understanding their solution. Can somebody check it and compare it with Schroeppel's result (which, typically for HAKMEM, is stated without proof)? Rich, do you remember your approach? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Err, is the question "What's the fraction of numbers <N whose largest prime factor is < sqrtN?" ? If so, the answer is 1-log2 = 30.7%. This is a straightforward application of the prime number theorem, and, for a change, the answer is rigorous (rather than the typical situation where an answer to this sort of problem is either a heuristic estimate, or dependent on RH). We need to count the numbers up to N that are of the shape kP, with k an integer and sqrtN < P < N. This is sum over P of floor[N/P], which is close enough to N * sum(1/P). That sum is loglogP+C, with C = e^gamma or some such. Over our range of P, the sum is loglogN - loglogsqrtN, which works out to log2. This leaves 1-log2 as the fraction of interest. I worked out the closed form exact answer for "fraction of N that have no prime factor > cbrt N". It involves a couple of special functions, maybe Li or a dilog, but it's just a moderately messy integral. It came out to a little under 5%. My main interest was that it came out to a limiting percentage that didn't depend on N. Later, browsing MathComp, I came across a paper that showed how to numerically evaluate Dickman's function (and the parking-place constant), to high precision. Dickman's function, rho(x), is the fraction of numbers < N that have no prime factor > N^x. It's a messy integral that gets messier as x->0; the nesting depth of the integrals goes as 1/x. The fraction is very roughly given by rho(1/k) ~ 1/k^k. rho(x) is piecewise analytic (for 0<x<1), with the pieces joining at 1/N, and it has about 1/x derivatives at x. The 1/k^k estimate is useful as a guide for choosing methods & parameters for factoring algorithms. I think for a factor bound < 4rootN, rho(1/4) is about .5% rho(x) turns out to be an adequate estimator, though proving good error bounds depends on PNT, which needs RH for good error bounds. :-( Rich ------ Quoting Neil Sloane <njasloane@gmail.com>:
It occurs to me that there might be another explanation.
When we consider 7-smooth numbers, there are 2 seqs, the list of 7-smooth numbers, and the number of them that are <= n
But when we consider sqrt(n-1)-smooth numbers, there are 3 sequences: the list of the individual numbers, the number of sqrt(k-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<k and the number of sqrt(n-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<n
The entries A295084 and A333534 that I mentioned are of the first type
There are 2 different densities! Maybe that explains the confusion?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 6:23 PM Allan Wechsler <acwacw@gmail.com> wrote:
If we wait a few days, Neil, we might get some enlightenment from Rich or from somebody who can read that French math book. And then we'll have a much more substantive comment to add.
(For example, suppose it turns out that Tenenbaum and Wu made a mistake in their solution to Exercise 28? That'll be a great example of OEIS-enabled math.)
On Fri, Apr 10, 2020 at 6:15 PM Neil Sloane <njasloane@gmail.com> wrote:
Allan,
1. There are two related sequences. If we call your A063539 the number of sqrt(n-1)-smooth numbers , then A295084 counts sqrt(n)-smooth numbers, and my A333534 counts log(n)-smooth numbers. I only added it two days ago - a strange coincidence? I am interested in smooth numbers because they seem to underlie A332580, for which I am trying to find an upper bound.
2. There is a book by Andrew Granville on Smooth Numbers - I found a copy on the web:
http://math.utoledo.edu/~codenth/Spring_13/3200/NT-books/Smooth_Numbers-Comp...
3. Will it be OK if I add your comments about the question of the
density
of A63539 to that entry?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 4:59 PM Allan Wechsler <acwacw@gmail.com> wrote:
The referenced sequence records numbers whose largest prime factor falls short of the square root of the number.
The graph of the sequence makes it clear that these numbers have a well-defined asymptotic density.
Following a citation to HAKMEM 29 (Schroeppel), we find a claim equivalent to saying that this density is 1 - ln 2 ~ 0.30685
But empirically, the density looks considerably smaller, more like 0.27.
The problem can't be whether or not to include exact squares of primes, because those have asymptotic density 0.
We have one more reported reference, to Exercise 28 on p. 26 of Tenenbaum and Wu, Théorie analytique et probabiliste des nombres, solution on p.
But I don't have a copy, and my French isn't up to the task of understanding their solution. Can somebody check it and compare it with Schroeppel's result (which, typically for HAKMEM, is stated without proof)? Rich, do you remember your approach? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
My confusion was prompted by the the extreme slowness with which the density climbs to the predicted value. Over on Sequence Fanatics, somebody has run an exhaustive enumeration of "square-root-smooth" numbers out past 10^11. The density has not yet reached 0.29. On Sat, Apr 11, 2020 at 1:34 AM <rcs@xmission.com> wrote:
Err, is the question "What's the fraction of numbers <N whose largest prime factor is < sqrtN?" ?
If so, the answer is 1-log2 = 30.7%.
This is a straightforward application of the prime number theorem, and, for a change, the answer is rigorous (rather than the typical situation where an answer to this sort of problem is either a heuristic estimate, or dependent on RH). We need to count the numbers up to N that are of the shape kP, with k an integer and sqrtN < P < N. This is sum over P of floor[N/P], which is close enough to N * sum(1/P). That sum is loglogP+C, with C = e^gamma or some such. Over our range of P, the sum is loglogN - loglogsqrtN, which works out to log2.
This leaves 1-log2 as the fraction of interest.
I worked out the closed form exact answer for "fraction of N that have no prime factor > cbrt N". It involves a couple of special functions, maybe Li or a dilog, but it's just a moderately messy integral. It came out to a little under 5%. My main interest was that it came out to a limiting percentage that didn't depend on N.
Later, browsing MathComp, I came across a paper that showed how to numerically evaluate Dickman's function (and the parking-place constant), to high precision.
Dickman's function, rho(x), is the fraction of numbers < N that have no prime factor > N^x. It's a messy integral that gets messier as x->0; the nesting depth of the integrals goes as 1/x. The fraction is very roughly given by rho(1/k) ~ 1/k^k. rho(x) is piecewise analytic (for 0<x<1), with the pieces joining at 1/N, and it has about 1/x derivatives at x. The 1/k^k estimate is useful as a guide for choosing methods & parameters for factoring algorithms.
I think for a factor bound < 4rootN, rho(1/4) is about .5%
rho(x) turns out to be an adequate estimator, though proving good error bounds depends on PNT, which needs RH for good error bounds. :-(
Rich
------ Quoting Neil Sloane <njasloane@gmail.com>:
It occurs to me that there might be another explanation.
When we consider 7-smooth numbers, there are 2 seqs, the list of 7-smooth numbers, and the number of them that are <= n
But when we consider sqrt(n-1)-smooth numbers, there are 3 sequences: the list of the individual numbers, the number of sqrt(k-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<k and the number of sqrt(n-1)-smooth numbers that are <= n, meaning number of k <= n such that GPF(k)<n
The entries A295084 and A333534 that I mentioned are of the first type
There are 2 different densities! Maybe that explains the confusion?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 6:23 PM Allan Wechsler <acwacw@gmail.com> wrote:
If we wait a few days, Neil, we might get some enlightenment from Rich or from somebody who can read that French math book. And then we'll have a much more substantive comment to add.
(For example, suppose it turns out that Tenenbaum and Wu made a mistake in their solution to Exercise 28? That'll be a great example of OEIS-enabled math.)
On Fri, Apr 10, 2020 at 6:15 PM Neil Sloane <njasloane@gmail.com> wrote:
Allan,
1. There are two related sequences. If we call your A063539 the number of sqrt(n-1)-smooth numbers , then A295084 counts sqrt(n)-smooth numbers, and my A333534 counts log(n)-smooth numbers. I only added it two days ago - a strange coincidence? I am interested in smooth numbers because they seem to underlie A332580, for which I am trying to find an upper bound.
2. There is a book by Andrew Granville on Smooth Numbers - I found a copy on the web:
http://math.utoledo.edu/~codenth/Spring_13/3200/NT-books/Smooth_Numbers-Comp...
3. Will it be OK if I add your comments about the question of the
density
of A63539 to that entry?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Apr 10, 2020 at 4:59 PM Allan Wechsler <acwacw@gmail.com> wrote:
The referenced sequence records numbers whose largest prime factor falls short of the square root of the number.
The graph of the sequence makes it clear that these numbers have a well-defined asymptotic density.
Following a citation to HAKMEM 29 (Schroeppel), we find a claim equivalent to saying that this density is 1 - ln 2 ~ 0.30685
But empirically, the density looks considerably smaller, more like 0.27.
The problem can't be whether or not to include exact squares of primes, because those have asymptotic density 0.
We have one more reported reference, to Exercise 28 on p. 26 of Tenenbaum and Wu, Théorie analytique et probabiliste des nombres, solution on p.
But I don't have a copy, and my French isn't up to the task of understanding their solution. Can somebody check it and compare it with Schroeppel's result (which, typically for HAKMEM, is stated without proof)? Rich, do you remember your approach? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Allan Wechsler -
Neil Sloane -
rcs＠xmission.com