Prime numbers and primality testing is a Restricted Group with 1118 members.
 Prime numbers and primality testing

 Restricted Group,
 1118 members
Is phi(p^21)/(p^21) bounded?
Expand Messages
 Briefly:
forprime (p=1000000,1000500,
ep=eulerphi((p1)*(p+1));print1(ep":"ep/(p^21)*1.0","))
indicates 0.22~< phi(p^21)/(p^21) <~0.33
leading one to the belief that it tends to a limit...
Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
http://www.users.globalnet.co.uk/~perry/DIVMenu/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com > Briefly:
I don't see why your belief is justified based on a small sample and no analysis.
>
> forprime (p=1000000,1000500,
> ep=eulerphi((p1)*(p+1));print1(ep":"ep/(p^21)*1.0","))
>
> indicates 0.22~< phi(p^21)/(p^21) <~0.33
>
> leading one to the belief that it tends to a limit...
Just because a function is bounded over a small range doesn't mean it tends to a limit. Even if it's bounded over an infinite range doesn't mean it tends to a limit. For instance, sin(x) is bounded by +1 and 1 for all real x, but no limit exists as x tends to infinity.
Paul It was actually a fish for some voluntary labour. Pari chokes on
primes>1000000, and I have no other means of performing such high powers
tests that would be required, let alone access to a modern machine.
I did check it over a range of values, and my bounds were deduced from these
tests. As phi(n)/n has no limit, I would assume this doesn't either, but I
was surprised by the narrow region of results.
Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
http://www.users.globalnet.co.uk/~perry/DIVMenu/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com  Has anyone heard of any conjectures similar to the following ones I
have come up with?
Conjecture: For real x>1 the smallest n such that there's always a
prime between x^n and (x+1)^n, is somewhat larger than 1.7632. n
being the solution to x^n=113 and (x+1)^n=127.
Conjecture: For all positive integers x the smallest n such that
there's always a prime between x^n and (x+1)^n is roughly 1.5478
n= ln 1151 / ln 95
I would initially have said that there's always a prime between x^n
and (x+1)^n for integers x for all n in the range ln 1151 / ln95 < n
n < ln 523 / ln 57. That is 1.547777 < n < 1.548232.
However, it turns out that theres no prime between
593^1.54792=19609.5 and
594^1.54792=19660.7
so we have to exclude a tiny range of 6.3 millionths so that
n > ln 19661 / ln 594
or
n < ln 19609 / ln 593
Amazing!
Richard Heylen   Jon Perry <perry@...> wrote:
> It was actually a fish for some voluntary labour. Pari chokes on
Use 'calc' instead. Or bc. Or the other 'calc'. Or use gp and use
> primes>1000000, and I have no other means of performing such high powers
> tests that would be required, let alone access to a modern machine.
'p=nextprime(p+1)' rather than 'forprime(p='.
> I did check it over a range of values, and my bounds were deduced from these
One of (p1) and (p+1) is divisible by 2,
> tests. As phi(n)/n has no limit, I would assume this doesn't either, but I
> was surprised by the narrow region of results.
the other is divisible by 4 or 2^i i>2
One of (p1) and (p+1) is divisible by 3.
The 2s combine such that
Phi((p1)*(p+1)) = Phi(2.2^i.(p1)/2.(p+1)/2^i)
= 2^i.Phi((p1)(p+1)/2^(i+1))
The factor of three gives you a 2/3 factor.
Therefore the highest value you will find will be
1/2*2/3 = 1/3 from p=3,5,17
and 1/3eps from numbers with a few prime factors larger than 2 or 3 in p+1
and p1.
e.g.
499637 0.3333266618578673045764089881
(23:01) gp > factor(4996371)
%3 =
[2 2]
[124909 1]
(23:02) gp > factor(499637+1)
%4 =
[2 1]
[3 1]
[83273 1]
Note that by HL it will reach 1/3eps infinitely often
Lower bound  anyone care for a stab? There should be some bound somewhere,
I'm sure.
Phil
=====
The answer to life's mystery is simple and direct:
Sex and death.  Ian 'Lemmy' Kilminster
__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus  Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com  Jon Perry mistakenly claimed that
> Pari chokes on primes>1000000
Invoke it with p10000000 to precompute primes to 10M.
Limit is about 430M, as I recall, but then you
need to allocate core with the s<size> modifier.  Phil:
> Therefore the highest value you will find will be
.......................?
> 1/2*2/3 = 1/3 from p=3,5,17
No. p=3 gives 1/2
and p=2 gives 2/3 which is maximal, for prime p.   "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
> Phil:
Deliberate mistake, to see if Jon was paying attention! ;)
> > Therefore the highest value you will find will be
> > 1/2*2/3 = 1/3 from p=3,5,17
> .......................?
> No. p=3 gives 1/2
> and p=2 gives 2/3 which is maximal, for prime p.
Phil
(lying through his teeth!)
=====
The answer to life's mystery is simple and direct:
Sex and death.  Ian 'Lemmy' Kilminster
__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus  Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com  Phil:
> Lower bound  anyone care for a stab?
0.
We believe (but cannot prove)
that there are an infinite number of primes of
the form primorial+1. That would be enough
to make f(p)=phi(p^21)/(p^21)
as close to zero as one likes.
At present we know that
p=392113#+1 is prime,
giving (a la Mertens)
f(p) < 0.0436
Can anyone get lower than that?
David  Let f(p)=phi(p^21)/(p^21).
Say a prime p is "lowest yet" if there is
no prime q<p with f(q)<f(p).
The "lowest yet" sequence begins
2, 3, 5, 11, 29, 131, 139, 181, 419, 1429, 17291, 23561,
23869, 188189, 315589, 483209, 614041, 1624349, 1729001,
8242961, 15431989, 22486309, 27033161, 36058021, 57762431,
61577671, 117048931, ...
(117048931^21)/4=
2*3*5*7*11*13*19*23*29*31*41*73*97
What comes next?   "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
> Phil:
It's what I would have guessed, but my brain has begun to stop working in
> > Lower bound  anyone care for a stab?
>
> 0.
the last few hours. (e.g. the p=3 > 0.5 line was on my screen when I typed
p=3 > 1/3, so I'm really not with it!)
> We believe (but cannot prove)
As many different prime factors as possible, such that
> that there are an infinite number of primes of
> the form primorial+1.
Product[(p1)/p] could be over as many terms as possible.
> That would be enough
Of course.
> to make f(p)=phi(p^21)/(p^21)
> as close to zero as one likes.
> At present we know that
Not without using a larger number, probably (it's possible, though, as you
> p=392113#+1 is prime,
> giving (a la Mertens)
> f(p) < 0.0436
>
> Can anyone get lower than that?
can use fewer factors in p1, and dope p+1 with them instead  all you
need's a few coincidences). However, finding primes of that size is not for
the faint hearted.
Phil
=====
The answer to life's mystery is simple and direct:
Sex and death.  Ian 'Lemmy' Kilminster
__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus  Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com   "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
> Let f(p)=phi(p^21)/(p^21).
Nice concrete followon from Jon's original.
> Say a prime p is "lowest yet" if there is
> no prime q<p with f(q)<f(p).
> The "lowest yet" sequence begins
> 2, 3, 5, 11, 29, 131, 139, 181, 419, 1429, 17291, 23561,
> 23869, 188189, 315589, 483209, 614041, 1624349, 1729001,
> 8242961, 15431989, 22486309, 27033161, 36058021, 57762431,
> 61577671, 117048931, ...
>
> (117048931^21)/4=
> 2*3*5*7*11*13*19*23*29*31*41*73*97
>
> What comes next?
I can't see a clever way to improve on bruteforce search without leaving
the possibility of missing some.
However, it might be possible to stick some markers in the ground for people
to aim at by finding squarefreesmooths that have isprime(sqrt(4s+1)).
Phil
=====
The answer to life's mystery is simple and direct:
Sex and death.  Ian 'Lemmy' Kilminster
__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus  Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com   In primenumbers@yahoogroups.com, "David Broadhurst
<d.broadhurst@o...>" <d.broadhurst@o...> wrote:> Let f(p)=phi(p^21)/(p^21).
<snip>
> Say a prime p is "lowest yet" if there is
> no prime q<p with f(q)<f(p).
> The "lowest yet" sequence begins
> 61577671, 117048931, ...
I believe it continues as follows
181333151
267190769
331413809
376754951
636510601
1737265531
3019962791
One can obtain fairly low values of f(p) realtively easily. Consider
for example
p=58531393985146662592474024598667898081212671 prime
p1=2.5.7.13.19.43.53.67.71.73.43520821168673.98287085283258329
p+1=2^8.3^3.11.17.23.29.31.37.41.47.59.61.79.83.89.97.101.103.107.109.
113.127.131.661
So the first 33 primes are factors of p^21 and I believe this gives
an f(p) around 0.113
This is significantly smaller than the f(p) around 0.148 for the best
of the minimal examples listed.
To break the 0.10 barrier you need primes up to 257.
To break the 0.05 barrier you need primes up to 75029
By this stage, the numbers are getting rather large.
Richard Heylen  Richard:
> I believe it continues as follows
I proved the first 4 of your addenda with
> 181333151
> 267190769
> 331413809
> 376754951
> 636510601
> 1737265531
> 3019962791
the unsmart bruteforce PariGP source
m=1;mp=430*10^6; \\ Jon please note
forprime(p=2,mp,n=p^21;s=eulerphi(n)/n;if(s<m,m=s;print(p)))
David  'm=1;mp=430*10^6; \\ Jon please note
forprime(p=2,mp,n=p^21;s=eulerphi(n)/n;if(s<m,m=s;print(p)))'
I'm looking...
'Use 'calc' instead. Or bc. Or the other 'calc'. Or use gp and use
'p=nextprime(p+1)' rather than 'forprime(p='.'
Is this the K.R. Matthews Number Theory calculator 'calc'?
Is there such a concept as the 'average value of f(p)'?
Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
http://www.users.globalnet.co.uk/~perry/DIVMenu/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com   Jon Perry <perry@...> wrote:
> 'm=1;mp=430*10^6; \\ Jon please note
Possibly. I'm using Chongo's calc (Curt Landon Noll, record prime finder 23
> forprime(p=2,mp,n=p^21;s=eulerphi(n)/n;if(s<m,m=s;print(p)))'
>
> I'm looking...
>
> 'Use 'calc' instead. Or bc. Or the other 'calc'. Or use gp and use
> 'p=nextprime(p+1)' rather than 'forprime(p='.'
>
> Is this the K.R. Matthews Number Theory calculator 'calc'?
decades ago), which is the standard 'GNU' utility. The whereabouts of the
other calc is answered in the archives some time around a year back, maybe
more.
> Is there such a concept as the 'average value of f(p)'?
I expect it to drift downards so it's not welldefined.
(or maybe it is, maybe it's zero. On average numbers have 1/eps distinct
divisors, i.e. a divergent number. That's got to take a toll on the phi
value. Any sample up to 300000# is puny compared with the sizes of almost
all integers...)
Phil
=====
The answer to life's mystery is simple and direct:
Sex and death.  Ian 'Lemmy' Kilminster
__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus  Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com  'I expect it to drift downards so it's not welldefined.
(or maybe it is, maybe it's zero. On average numbers have 1/eps distinct
divisors, i.e. a divergent number. That's got to take a toll on the phi
value. Any sample up to 300000# is puny compared with the sizes of almost
all integers...)'
'Therefore the highest value you will find will be
1/2*2/3 = 1/3 from p=3,5,17
and 1/3eps from numbers with a few prime factors larger than 2 or 3 in p+1
and p1.'
Cough, cough. You make these up, or do they come naturally?
Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
http://www.users.globalnet.co.uk/~perry/DIVMenu/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com   Jon Perry <perry@...> wrote:
Quoting me:
> 'I expect it to drift downards so it's not welldefined.
Where the 3 was already pointed out as a typo.
> (or maybe it is, maybe it's zero. On average numbers have 1/eps distinct
> divisors, i.e. a divergent number. That's got to take a toll on the phi
> value. Any sample up to 300000# is puny compared with the sizes of almost
> all integers...)'
> 'Therefore the highest value you will find will be
> 1/2*2/3 = 1/3 from p=3,5,17
> and 1/3eps from numbers with a few prime factors larger than 2 or 3 in p+1
> and p1.'
> Cough, cough. You make these up, or do they come naturally?
OK John. Which of the two statements do you think is wrong?
And why?
Come on, show us the flaws, I yearn to be enlightened by your razersharp
mathematical quill. I'll even fill in the ellipses, if you like, as have a
feeling you're getting confused by my elision.
�10 to Oxfam for each statement you persuade me to retract. I trust you'll
reciprocate?
Phil
=====
The answer to life's mystery is simple and direct:
Sex and death.  Ian 'Lemmy' Kilminster
__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus  Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com  '£10 to Oxfam for each statement you persuade me to retract. I trust you'll
reciprocate?'
What... Oxfam will pay me £10 to persuade you to retract them?
I believe they are both correct, hence I will not allow Oxfam to waste their
money on me, and this in turn leads me to believe that f(p) could have an
average value.
Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
http://www.users.globalnet.co.uk/~perry/DIVMenu/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
Your message has been successfully submitted and would be delivered to recipients shortly.