Finding a better approximation to a prime number relation
up vote
19
down vote
favorite
FINAL EDIT AND SUMMARY.
The basis of this problem, and that which allows for the approximations to be made here, can be summarised in one approximation:
$$Biggl(frac{n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor)}{n^k -{lfloor n^{frac{1}{k}} rfloor}gcd({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor)}Biggr)^{frac{1}{k}}
sim1quadforall n,k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A0)$$
$$frac{Bigllfloor bigl(n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor)bigr)^{frac{1}{k}}Bigrrfloor
}{Bigllfloor bigl(n^k -{lfloor n^{frac{1}{k}} rfloor}gcd({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor)bigr)^{frac{1}{k}}Bigrrfloor} =1quadforall n,k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A1)$$
$${gcdBigl({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^k}{n^k} BigrrfloorBigr)}quad Biggl|quad{{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} BigrrfloorBigr)}
$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A2)$$
Defining the above ratio as varsigma:
$$varsigma_{n,k}= frac{{{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} BigrrfloorBigr)}
}{{gcdBigl({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^k}{n^k} BigrrfloorBigr)}}$$
We have the following:
$n lt 2^k Rightarrow varsigma_{n,k}=1$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A3)$$
$varsigma_{n,k}$ is a perfect power $forall n,k in mathbb N, backslash ,{{1}}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A4)$$
To generalize:
$$varsigma_{n,k,i,j}= frac{{{lfloor n^{frac{1}{k}} rfloor}^{j-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{j},Bigllfloor frac{p_n^{,,j}}{n^{,j}} BigrrfloorBigr)}
}{{gcdBigl({lfloor n^{frac{1}{k}} rfloor^{,i}},Bigllfloor frac{p_n^{,i}}{n^{,i}} BigrrfloorBigr)}}$$
provided that $j geq i$,we have:
$m^k leq n lt (m+1)^k Rightarrow varsigma_{n,k,i,j} in {{m^N:N in {{1,2,3,...,k}}}}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A5)$$
reducing the above by setting $i=j$:
$$varsigma_{n,k,j}= lfloor n^{frac{1}{k}} rfloor^{j-1}$$
$m^k leq n lt (m+1)^k Rightarrow varsigma_{n,k,j}=m^{j-1}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A6)$$
So the question I am now asking, for that fun person that wants to close this page, is how do I establish a proof for (A5) that will be rigorous and indisputable?
Yesterday I noticed quite a strong fit for the approximation:
$$vartheta _{{n}}=minBiggl(mathcal DBigl(ncdotBigllfloor frac{p_n}{n} BigrrfloorBigr) backslash {{1}}Biggr)$$
$$n-gcd(bigllfloor sqrt {n} bigrrfloor ,vartheta _{{n}})) approx A cdot (n-1) +B$$
where $A approx 1$ and $B approx -1/2$ and $mathcal D(n)$ denote the set of all divisors of $n$, $p_n$ is the $n^{th}$ prime.
$$sqrt{bigl( n^{2}-bigllfloor sqrt {n} bigrrfloorcdotgcd(bigllfloor sqrt {n} bigrrfloor ,vartheta _{{n}})bigr)}sim n $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R1)$$
$$sqrt{bigl( n-gcd(n ,vartheta _{{n}})bigr)}+frac{1}{sqrt{n}}sim sqrt{n}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R2)$$
$$sqrt{{n}^{2}-max left( lfloor sqrt{n} rfloor ,n
right) min left( gcd left( lfloor sqrt{n} rfloor,vartheta_n right) ,gcd left( n,vartheta_n right) right)
}+1+delta_{{n}}sim n$$
Where $delta_n in {{-frac{1}{2},0,frac{1}{2}}}$ is a discrete function for which I am unable to determine as yet.
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R3)$$
So I guess the best idea now would be for me to find either a value on $mathbb N$ that satisfies neither of the following equalities:
$$n- Biggl(Bigllfloorsqrt {{n}^{2}- lfloor sqrt{n}
rfloor cdot gcd left( lfloor sqrt{n} rfloor ,vartheta_n right) } Bigrrfloor+1Biggr) = 0 $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R4)$$
$$n-Biggl(Bigllfloor sqrt{{n}^{2}-min left( lfloor
sqrt{n} rfloor ,n right)cdotminleft(gcd ( lfloor sqrt{n}rfloor,vartheta_n) ,gcd ( n,vartheta_n)
right) }Bigrrfloor +1Biggr) = 0$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R5)$$
Figure 1:
Figure 2:
Defining a generalisation of vartheta:
$$vartheta _{{n,k}}=minBiggl(mathcal DBigl(n^{k}cdotBigllfloor frac{p_n^{k}}{n^{k}} BigrrfloorBigr), backslash, {{1}}Biggr)$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R6)$$
Will allow for the following asymptotic relation as we would intuitively expect from the nature of the generalisation and the nature of $(R2)$:
$$(n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} sim n quad forall k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R7)$$
Which is based on an apparent equality:
$$lfloor (n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R8)$$
$$lfloor (n^k -gcd(lfloor n^{frac{1}{k}} rfloor,Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R9)$$
$$lfloor (n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R10)$$
$$lim _{krightarrow infty }((n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} )=n$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R11)$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R12)$$
Figure 5
prime-numbers
|
show 23 more comments
up vote
19
down vote
favorite
FINAL EDIT AND SUMMARY.
The basis of this problem, and that which allows for the approximations to be made here, can be summarised in one approximation:
$$Biggl(frac{n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor)}{n^k -{lfloor n^{frac{1}{k}} rfloor}gcd({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor)}Biggr)^{frac{1}{k}}
sim1quadforall n,k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A0)$$
$$frac{Bigllfloor bigl(n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor)bigr)^{frac{1}{k}}Bigrrfloor
}{Bigllfloor bigl(n^k -{lfloor n^{frac{1}{k}} rfloor}gcd({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor)bigr)^{frac{1}{k}}Bigrrfloor} =1quadforall n,k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A1)$$
$${gcdBigl({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^k}{n^k} BigrrfloorBigr)}quad Biggl|quad{{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} BigrrfloorBigr)}
$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A2)$$
Defining the above ratio as varsigma:
$$varsigma_{n,k}= frac{{{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} BigrrfloorBigr)}
}{{gcdBigl({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^k}{n^k} BigrrfloorBigr)}}$$
We have the following:
$n lt 2^k Rightarrow varsigma_{n,k}=1$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A3)$$
$varsigma_{n,k}$ is a perfect power $forall n,k in mathbb N, backslash ,{{1}}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A4)$$
To generalize:
$$varsigma_{n,k,i,j}= frac{{{lfloor n^{frac{1}{k}} rfloor}^{j-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{j},Bigllfloor frac{p_n^{,,j}}{n^{,j}} BigrrfloorBigr)}
}{{gcdBigl({lfloor n^{frac{1}{k}} rfloor^{,i}},Bigllfloor frac{p_n^{,i}}{n^{,i}} BigrrfloorBigr)}}$$
provided that $j geq i$,we have:
$m^k leq n lt (m+1)^k Rightarrow varsigma_{n,k,i,j} in {{m^N:N in {{1,2,3,...,k}}}}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A5)$$
reducing the above by setting $i=j$:
$$varsigma_{n,k,j}= lfloor n^{frac{1}{k}} rfloor^{j-1}$$
$m^k leq n lt (m+1)^k Rightarrow varsigma_{n,k,j}=m^{j-1}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A6)$$
So the question I am now asking, for that fun person that wants to close this page, is how do I establish a proof for (A5) that will be rigorous and indisputable?
Yesterday I noticed quite a strong fit for the approximation:
$$vartheta _{{n}}=minBiggl(mathcal DBigl(ncdotBigllfloor frac{p_n}{n} BigrrfloorBigr) backslash {{1}}Biggr)$$
$$n-gcd(bigllfloor sqrt {n} bigrrfloor ,vartheta _{{n}})) approx A cdot (n-1) +B$$
where $A approx 1$ and $B approx -1/2$ and $mathcal D(n)$ denote the set of all divisors of $n$, $p_n$ is the $n^{th}$ prime.
$$sqrt{bigl( n^{2}-bigllfloor sqrt {n} bigrrfloorcdotgcd(bigllfloor sqrt {n} bigrrfloor ,vartheta _{{n}})bigr)}sim n $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R1)$$
$$sqrt{bigl( n-gcd(n ,vartheta _{{n}})bigr)}+frac{1}{sqrt{n}}sim sqrt{n}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R2)$$
$$sqrt{{n}^{2}-max left( lfloor sqrt{n} rfloor ,n
right) min left( gcd left( lfloor sqrt{n} rfloor,vartheta_n right) ,gcd left( n,vartheta_n right) right)
}+1+delta_{{n}}sim n$$
Where $delta_n in {{-frac{1}{2},0,frac{1}{2}}}$ is a discrete function for which I am unable to determine as yet.
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R3)$$
So I guess the best idea now would be for me to find either a value on $mathbb N$ that satisfies neither of the following equalities:
$$n- Biggl(Bigllfloorsqrt {{n}^{2}- lfloor sqrt{n}
rfloor cdot gcd left( lfloor sqrt{n} rfloor ,vartheta_n right) } Bigrrfloor+1Biggr) = 0 $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R4)$$
$$n-Biggl(Bigllfloor sqrt{{n}^{2}-min left( lfloor
sqrt{n} rfloor ,n right)cdotminleft(gcd ( lfloor sqrt{n}rfloor,vartheta_n) ,gcd ( n,vartheta_n)
right) }Bigrrfloor +1Biggr) = 0$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R5)$$
Figure 1:
Figure 2:
Defining a generalisation of vartheta:
$$vartheta _{{n,k}}=minBiggl(mathcal DBigl(n^{k}cdotBigllfloor frac{p_n^{k}}{n^{k}} BigrrfloorBigr), backslash, {{1}}Biggr)$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R6)$$
Will allow for the following asymptotic relation as we would intuitively expect from the nature of the generalisation and the nature of $(R2)$:
$$(n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} sim n quad forall k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R7)$$
Which is based on an apparent equality:
$$lfloor (n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R8)$$
$$lfloor (n^k -gcd(lfloor n^{frac{1}{k}} rfloor,Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R9)$$
$$lfloor (n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R10)$$
$$lim _{krightarrow infty }((n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} )=n$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R11)$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R12)$$
Figure 5
prime-numbers
We can slightly simplify the left side to $$n-gcd(lfloor sqrt{n} rfloor,q)$$ where $q$ is the smallest prime factor of $$ncdot lfloor frac{p_n}{n} rfloor$$
– Peter
Jun 10 at 8:28
Further we can conclude that the left side is either $n-1$ or $n-q$
– Peter
Jun 10 at 8:30
True yes. I have been trying to read PNT Wikipedia pages and feel as if there will definitely be a better least square regression choice than linear I just can't see it yet because I have done very little in approximations, always feel cheap about it but they are a discipline in themselves really
– Adam
Jun 10 at 8:31
1
en.wikipedia.org/wiki/Prime-counting_function shows, among other things, the (proven) bounds from Pierre Dusart.
– Peter
Jun 10 at 10:21
2
Your goal is to construct a formula that avoids brute force calculation. If not, you do not need the formula and can calculate the values directly. "Predictible" means that a program can get the correct answer much faster and always correct and needs no cumbersome calculations.
– Peter
Jun 10 at 15:52
|
show 23 more comments
up vote
19
down vote
favorite
up vote
19
down vote
favorite
FINAL EDIT AND SUMMARY.
The basis of this problem, and that which allows for the approximations to be made here, can be summarised in one approximation:
$$Biggl(frac{n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor)}{n^k -{lfloor n^{frac{1}{k}} rfloor}gcd({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor)}Biggr)^{frac{1}{k}}
sim1quadforall n,k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A0)$$
$$frac{Bigllfloor bigl(n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor)bigr)^{frac{1}{k}}Bigrrfloor
}{Bigllfloor bigl(n^k -{lfloor n^{frac{1}{k}} rfloor}gcd({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor)bigr)^{frac{1}{k}}Bigrrfloor} =1quadforall n,k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A1)$$
$${gcdBigl({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^k}{n^k} BigrrfloorBigr)}quad Biggl|quad{{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} BigrrfloorBigr)}
$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A2)$$
Defining the above ratio as varsigma:
$$varsigma_{n,k}= frac{{{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} BigrrfloorBigr)}
}{{gcdBigl({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^k}{n^k} BigrrfloorBigr)}}$$
We have the following:
$n lt 2^k Rightarrow varsigma_{n,k}=1$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A3)$$
$varsigma_{n,k}$ is a perfect power $forall n,k in mathbb N, backslash ,{{1}}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A4)$$
To generalize:
$$varsigma_{n,k,i,j}= frac{{{lfloor n^{frac{1}{k}} rfloor}^{j-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{j},Bigllfloor frac{p_n^{,,j}}{n^{,j}} BigrrfloorBigr)}
}{{gcdBigl({lfloor n^{frac{1}{k}} rfloor^{,i}},Bigllfloor frac{p_n^{,i}}{n^{,i}} BigrrfloorBigr)}}$$
provided that $j geq i$,we have:
$m^k leq n lt (m+1)^k Rightarrow varsigma_{n,k,i,j} in {{m^N:N in {{1,2,3,...,k}}}}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A5)$$
reducing the above by setting $i=j$:
$$varsigma_{n,k,j}= lfloor n^{frac{1}{k}} rfloor^{j-1}$$
$m^k leq n lt (m+1)^k Rightarrow varsigma_{n,k,j}=m^{j-1}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A6)$$
So the question I am now asking, for that fun person that wants to close this page, is how do I establish a proof for (A5) that will be rigorous and indisputable?
Yesterday I noticed quite a strong fit for the approximation:
$$vartheta _{{n}}=minBiggl(mathcal DBigl(ncdotBigllfloor frac{p_n}{n} BigrrfloorBigr) backslash {{1}}Biggr)$$
$$n-gcd(bigllfloor sqrt {n} bigrrfloor ,vartheta _{{n}})) approx A cdot (n-1) +B$$
where $A approx 1$ and $B approx -1/2$ and $mathcal D(n)$ denote the set of all divisors of $n$, $p_n$ is the $n^{th}$ prime.
$$sqrt{bigl( n^{2}-bigllfloor sqrt {n} bigrrfloorcdotgcd(bigllfloor sqrt {n} bigrrfloor ,vartheta _{{n}})bigr)}sim n $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R1)$$
$$sqrt{bigl( n-gcd(n ,vartheta _{{n}})bigr)}+frac{1}{sqrt{n}}sim sqrt{n}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R2)$$
$$sqrt{{n}^{2}-max left( lfloor sqrt{n} rfloor ,n
right) min left( gcd left( lfloor sqrt{n} rfloor,vartheta_n right) ,gcd left( n,vartheta_n right) right)
}+1+delta_{{n}}sim n$$
Where $delta_n in {{-frac{1}{2},0,frac{1}{2}}}$ is a discrete function for which I am unable to determine as yet.
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R3)$$
So I guess the best idea now would be for me to find either a value on $mathbb N$ that satisfies neither of the following equalities:
$$n- Biggl(Bigllfloorsqrt {{n}^{2}- lfloor sqrt{n}
rfloor cdot gcd left( lfloor sqrt{n} rfloor ,vartheta_n right) } Bigrrfloor+1Biggr) = 0 $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R4)$$
$$n-Biggl(Bigllfloor sqrt{{n}^{2}-min left( lfloor
sqrt{n} rfloor ,n right)cdotminleft(gcd ( lfloor sqrt{n}rfloor,vartheta_n) ,gcd ( n,vartheta_n)
right) }Bigrrfloor +1Biggr) = 0$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R5)$$
Figure 1:
Figure 2:
Defining a generalisation of vartheta:
$$vartheta _{{n,k}}=minBiggl(mathcal DBigl(n^{k}cdotBigllfloor frac{p_n^{k}}{n^{k}} BigrrfloorBigr), backslash, {{1}}Biggr)$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R6)$$
Will allow for the following asymptotic relation as we would intuitively expect from the nature of the generalisation and the nature of $(R2)$:
$$(n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} sim n quad forall k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R7)$$
Which is based on an apparent equality:
$$lfloor (n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R8)$$
$$lfloor (n^k -gcd(lfloor n^{frac{1}{k}} rfloor,Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R9)$$
$$lfloor (n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R10)$$
$$lim _{krightarrow infty }((n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} )=n$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R11)$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R12)$$
Figure 5
prime-numbers
FINAL EDIT AND SUMMARY.
The basis of this problem, and that which allows for the approximations to be made here, can be summarised in one approximation:
$$Biggl(frac{n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor)}{n^k -{lfloor n^{frac{1}{k}} rfloor}gcd({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor)}Biggr)^{frac{1}{k}}
sim1quadforall n,k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A0)$$
$$frac{Bigllfloor bigl(n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor)bigr)^{frac{1}{k}}Bigrrfloor
}{Bigllfloor bigl(n^k -{lfloor n^{frac{1}{k}} rfloor}gcd({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor)bigr)^{frac{1}{k}}Bigrrfloor} =1quadforall n,k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A1)$$
$${gcdBigl({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^k}{n^k} BigrrfloorBigr)}quad Biggl|quad{{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} BigrrfloorBigr)}
$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A2)$$
Defining the above ratio as varsigma:
$$varsigma_{n,k}= frac{{{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} BigrrfloorBigr)}
}{{gcdBigl({lfloor n^{frac{1}{k}} rfloor},Bigllfloor frac{p_n^k}{n^k} BigrrfloorBigr)}}$$
We have the following:
$n lt 2^k Rightarrow varsigma_{n,k}=1$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A3)$$
$varsigma_{n,k}$ is a perfect power $forall n,k in mathbb N, backslash ,{{1}}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A4)$$
To generalize:
$$varsigma_{n,k,i,j}= frac{{{lfloor n^{frac{1}{k}} rfloor}^{j-1}gcdBigl({lfloor n^{frac{1}{k}} rfloor}^{j},Bigllfloor frac{p_n^{,,j}}{n^{,j}} BigrrfloorBigr)}
}{{gcdBigl({lfloor n^{frac{1}{k}} rfloor^{,i}},Bigllfloor frac{p_n^{,i}}{n^{,i}} BigrrfloorBigr)}}$$
provided that $j geq i$,we have:
$m^k leq n lt (m+1)^k Rightarrow varsigma_{n,k,i,j} in {{m^N:N in {{1,2,3,...,k}}}}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A5)$$
reducing the above by setting $i=j$:
$$varsigma_{n,k,j}= lfloor n^{frac{1}{k}} rfloor^{j-1}$$
$m^k leq n lt (m+1)^k Rightarrow varsigma_{n,k,j}=m^{j-1}$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(A6)$$
So the question I am now asking, for that fun person that wants to close this page, is how do I establish a proof for (A5) that will be rigorous and indisputable?
Yesterday I noticed quite a strong fit for the approximation:
$$vartheta _{{n}}=minBiggl(mathcal DBigl(ncdotBigllfloor frac{p_n}{n} BigrrfloorBigr) backslash {{1}}Biggr)$$
$$n-gcd(bigllfloor sqrt {n} bigrrfloor ,vartheta _{{n}})) approx A cdot (n-1) +B$$
where $A approx 1$ and $B approx -1/2$ and $mathcal D(n)$ denote the set of all divisors of $n$, $p_n$ is the $n^{th}$ prime.
$$sqrt{bigl( n^{2}-bigllfloor sqrt {n} bigrrfloorcdotgcd(bigllfloor sqrt {n} bigrrfloor ,vartheta _{{n}})bigr)}sim n $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R1)$$
$$sqrt{bigl( n-gcd(n ,vartheta _{{n}})bigr)}+frac{1}{sqrt{n}}sim sqrt{n}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R2)$$
$$sqrt{{n}^{2}-max left( lfloor sqrt{n} rfloor ,n
right) min left( gcd left( lfloor sqrt{n} rfloor,vartheta_n right) ,gcd left( n,vartheta_n right) right)
}+1+delta_{{n}}sim n$$
Where $delta_n in {{-frac{1}{2},0,frac{1}{2}}}$ is a discrete function for which I am unable to determine as yet.
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R3)$$
So I guess the best idea now would be for me to find either a value on $mathbb N$ that satisfies neither of the following equalities:
$$n- Biggl(Bigllfloorsqrt {{n}^{2}- lfloor sqrt{n}
rfloor cdot gcd left( lfloor sqrt{n} rfloor ,vartheta_n right) } Bigrrfloor+1Biggr) = 0 $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R4)$$
$$n-Biggl(Bigllfloor sqrt{{n}^{2}-min left( lfloor
sqrt{n} rfloor ,n right)cdotminleft(gcd ( lfloor sqrt{n}rfloor,vartheta_n) ,gcd ( n,vartheta_n)
right) }Bigrrfloor +1Biggr) = 0$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R5)$$
Figure 1:
Figure 2:
Defining a generalisation of vartheta:
$$vartheta _{{n,k}}=minBiggl(mathcal DBigl(n^{k}cdotBigllfloor frac{p_n^{k}}{n^{k}} BigrrfloorBigr), backslash, {{1}}Biggr)$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R6)$$
Will allow for the following asymptotic relation as we would intuitively expect from the nature of the generalisation and the nature of $(R2)$:
$$(n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} sim n quad forall k in mathbb Nbackslash {{1}}$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R7)$$
Which is based on an apparent equality:
$$lfloor (n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R8)$$
$$lfloor (n^k -gcd(lfloor n^{frac{1}{k}} rfloor,Bigllfloor frac{p_n^{k}}{n^{k}} Bigrrfloor))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R9)$$
$$lfloor (n^k -{lfloor n^{frac{1}{k}} rfloor}^{k-1}gcd({lfloor n^{frac{1}{k}} rfloor}^{k-1},Bigllfloor frac{p_n^{k-1}}{n^{k-1}} Bigrrfloor))^{frac{1}{k}} rfloor+1=nquad forall k in mathbb Nbackslash {{1}} $$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R10)$$
$$lim _{krightarrow infty }((n^k -lfloor n^{frac{1}{k}} rfloorgcd(lfloor n^{frac{1}{k}} rfloor,vartheta _{{n,k-1}}))^{frac{1}{k}} )=n$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R11)$$
$$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad(R12)$$
Figure 5
prime-numbers
prime-numbers
edited Nov 14 at 5:23
asked Jun 10 at 8:21
Adam
49613
49613
We can slightly simplify the left side to $$n-gcd(lfloor sqrt{n} rfloor,q)$$ where $q$ is the smallest prime factor of $$ncdot lfloor frac{p_n}{n} rfloor$$
– Peter
Jun 10 at 8:28
Further we can conclude that the left side is either $n-1$ or $n-q$
– Peter
Jun 10 at 8:30
True yes. I have been trying to read PNT Wikipedia pages and feel as if there will definitely be a better least square regression choice than linear I just can't see it yet because I have done very little in approximations, always feel cheap about it but they are a discipline in themselves really
– Adam
Jun 10 at 8:31
1
en.wikipedia.org/wiki/Prime-counting_function shows, among other things, the (proven) bounds from Pierre Dusart.
– Peter
Jun 10 at 10:21
2
Your goal is to construct a formula that avoids brute force calculation. If not, you do not need the formula and can calculate the values directly. "Predictible" means that a program can get the correct answer much faster and always correct and needs no cumbersome calculations.
– Peter
Jun 10 at 15:52
|
show 23 more comments
We can slightly simplify the left side to $$n-gcd(lfloor sqrt{n} rfloor,q)$$ where $q$ is the smallest prime factor of $$ncdot lfloor frac{p_n}{n} rfloor$$
– Peter
Jun 10 at 8:28
Further we can conclude that the left side is either $n-1$ or $n-q$
– Peter
Jun 10 at 8:30
True yes. I have been trying to read PNT Wikipedia pages and feel as if there will definitely be a better least square regression choice than linear I just can't see it yet because I have done very little in approximations, always feel cheap about it but they are a discipline in themselves really
– Adam
Jun 10 at 8:31
1
en.wikipedia.org/wiki/Prime-counting_function shows, among other things, the (proven) bounds from Pierre Dusart.
– Peter
Jun 10 at 10:21
2
Your goal is to construct a formula that avoids brute force calculation. If not, you do not need the formula and can calculate the values directly. "Predictible" means that a program can get the correct answer much faster and always correct and needs no cumbersome calculations.
– Peter
Jun 10 at 15:52
We can slightly simplify the left side to $$n-gcd(lfloor sqrt{n} rfloor,q)$$ where $q$ is the smallest prime factor of $$ncdot lfloor frac{p_n}{n} rfloor$$
– Peter
Jun 10 at 8:28
We can slightly simplify the left side to $$n-gcd(lfloor sqrt{n} rfloor,q)$$ where $q$ is the smallest prime factor of $$ncdot lfloor frac{p_n}{n} rfloor$$
– Peter
Jun 10 at 8:28
Further we can conclude that the left side is either $n-1$ or $n-q$
– Peter
Jun 10 at 8:30
Further we can conclude that the left side is either $n-1$ or $n-q$
– Peter
Jun 10 at 8:30
True yes. I have been trying to read PNT Wikipedia pages and feel as if there will definitely be a better least square regression choice than linear I just can't see it yet because I have done very little in approximations, always feel cheap about it but they are a discipline in themselves really
– Adam
Jun 10 at 8:31
True yes. I have been trying to read PNT Wikipedia pages and feel as if there will definitely be a better least square regression choice than linear I just can't see it yet because I have done very little in approximations, always feel cheap about it but they are a discipline in themselves really
– Adam
Jun 10 at 8:31
1
1
en.wikipedia.org/wiki/Prime-counting_function shows, among other things, the (proven) bounds from Pierre Dusart.
– Peter
Jun 10 at 10:21
en.wikipedia.org/wiki/Prime-counting_function shows, among other things, the (proven) bounds from Pierre Dusart.
– Peter
Jun 10 at 10:21
2
2
Your goal is to construct a formula that avoids brute force calculation. If not, you do not need the formula and can calculate the values directly. "Predictible" means that a program can get the correct answer much faster and always correct and needs no cumbersome calculations.
– Peter
Jun 10 at 15:52
Your goal is to construct a formula that avoids brute force calculation. If not, you do not need the formula and can calculate the values directly. "Predictible" means that a program can get the correct answer much faster and always correct and needs no cumbersome calculations.
– Peter
Jun 10 at 15:52
|
show 23 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2814343%2ffinding-a-better-approximation-to-a-prime-number-relation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
We can slightly simplify the left side to $$n-gcd(lfloor sqrt{n} rfloor,q)$$ where $q$ is the smallest prime factor of $$ncdot lfloor frac{p_n}{n} rfloor$$
– Peter
Jun 10 at 8:28
Further we can conclude that the left side is either $n-1$ or $n-q$
– Peter
Jun 10 at 8:30
True yes. I have been trying to read PNT Wikipedia pages and feel as if there will definitely be a better least square regression choice than linear I just can't see it yet because I have done very little in approximations, always feel cheap about it but they are a discipline in themselves really
– Adam
Jun 10 at 8:31
1
en.wikipedia.org/wiki/Prime-counting_function shows, among other things, the (proven) bounds from Pierre Dusart.
– Peter
Jun 10 at 10:21
2
Your goal is to construct a formula that avoids brute force calculation. If not, you do not need the formula and can calculate the values directly. "Predictible" means that a program can get the correct answer much faster and always correct and needs no cumbersome calculations.
– Peter
Jun 10 at 15:52