mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Inverse of Smoothness Probability (https://www.mersenneforum.org/showthread.php?t=22472)

 paul0 2017-07-24 12:24

Inverse of Smoothness Probability

The probability that a random number below X is B-smooth is given by u[SUP]-u[/SUP], where u=ln(X)/ln(B). However, I would like the do the inverse, that is, given the smoothness probability and B, how do I solve for X?

I have a solution via Newton method. Is there a closed form?

 Batalov 2017-07-24 19:53

[QUOTE=paul0;464067]The [COLOR="Red"]estimate of the[/COLOR] probability that a random number below X is B-smooth is given by u[SUP]-u[/SUP], where u=ln(X)/ln(B). [/QUOTE]

No need for Newton method, because it will immediately exceed the precision of the [I]estimate[/I] that you started with. There are [URL="https://en.wikipedia.org/wiki/Smooth_number#Distribution"]better estimates[/URL] (and then see Dickman's and/or Buchstab's).

 paul0 2017-07-25 09:10

[QUOTE=Batalov;464110]No need for Newton method, because it will immediately exceed the precision of the [I]estimate[/I] that you started with. There are [URL="https://en.wikipedia.org/wiki/Smooth_number#Distribution"]better estimates[/URL] (and then see Dickman's and/or Buchstab's).[/QUOTE]

I think you misunderstood. Instead of solving the probability of smoothness, I want to solve for X given B and the probability.

 Dubslow 2017-07-25 10:07

[QUOTE=paul0;464131]I think you misunderstood. Instead of solving the probability of smoothness, I want to solve for X given B and the probability.[/QUOTE]

He's saying that going in reverse on that equation (p = some_function_of(X, B), as you're trying to do, isn't very useful because it's [i]not[/i] an equation -- only an approximation, and not a very good one. Better to write p ~ some_function_of(X, B), and then note that the "~" is vague enough that undoing "some_function_of" isn't worth the effort.

The links he provides are sources for p ≈ some_better_function_of(X, B). Find those better functions before trying to invert them.

 paul0 2017-07-25 10:21

[QUOTE=Dubslow;464134]He's saying that going in reverse on that equation (p = some_function_of(X, B), as you're trying to do, isn't very useful because it's [i]not[/i] an equation -- only an approximation, and not a very good one. Better to write p ~ some_function_of(X, B), and then note that the "~" is vague enough that undoing "some_function_of" isn't worth the effort.

The links he provides are sources for p ≈ some_better_function_of(X, B). Find those better functions before trying to invert them.[/QUOTE]

I stand corrected. Thanks for clarifying :)

 Batalov 2017-07-25 16:33

Incidentally, I have just heard from much more knowledgeable people, and I will simply quote:

[QUOTE="Robert"]Note that the question (u[SUP]-u[/SUP]) can be answered using the [URL="https://en.wikipedia.org/wiki/Lambert_W_function"]Lambert W function[/URL]. But, of course, one still must compute the answer numerically via series/Pade approximant, etc.
Note that the W function is not real-analytic.

Bob[/QUOTE]

 Batalov 2017-07-25 16:41

And for the Inverse of Smoothness Probability question, you want a reasonable numerical estimate the inverse of Dickman function.
So you want to take Newton method on the inverse of Dickman ρ - because if you know the [URL="https://en.wikipedia.org/wiki/Dickman_function#Definition"]derivative of Dickman ρ[/URL] by definition, then you know the derivative of the inverse of Dickman ρ.

 All times are UTC. The time now is 00:02.