## Re: [PrimeNumbers] RE: Is phi(p^2-1)/(p^2-1) bounded?

Expand Messages
• ... Deliberate mistake, to see if Jon was paying attention! ;-) Phil (lying through his teeth!) ===== The answer to life s mystery is simple and direct: Sex
Message 1 of 20 , Jan 3, 2003
• 0 Attachment
> 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.

Deliberate mistake, to see if Jon was paying attention! ;-)

Phil
(lying through his teeth!)

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• ... 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^2-1)/(p^2-1)
Message 2 of 20 , Jan 3, 2003
• 0 Attachment
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^2-1)/(p^2-1)
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^2-1)/(p^2-1). Say a prime p is lowest yet if there is no prime q
Message 3 of 20 , Jan 3, 2003
• 0 Attachment
Let f(p)=phi(p^2-1)/(p^2-1).
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^2-1)/4=
2*3*5*7*11*13*19*23*29*31*41*73*97

What comes next?
• ... It s what I would have guessed, but my brain has begun to stop working in the last few hours. (e.g. the p=3 - 0.5 line was on my screen when I typed p=3
Message 4 of 20 , Jan 3, 2003
• 0 Attachment
> Phil:
> > Lower bound - anyone care for a stab?
>
> 0.

It's what I would have guessed, but my brain has begun to stop working in
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)
> that there are an infinite number of primes of
> the form primorial+1.

As many different prime factors as possible, such that
Product[(p-1)/p] could be over as many terms as possible.

> That would be enough
> to make f(p)=phi(p^2-1)/(p^2-1)
> as close to zero as one likes.

Of course.

> At present we know that
> p=392113#+1 is prime,
> giving (a la Mertens)
> f(p) < 0.0436
>
> Can anyone get lower than that?

Not without using a larger number, probably (it's possible, though, as you
can use fewer factors in p-1, 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!?
http://mailplus.yahoo.com
• ... Nice concrete follow-on from Jon s original. I can t see a clever way to improve on brute-force search without leaving the possibility of missing some.
Message 5 of 20 , Jan 3, 2003
• 0 Attachment
> Let f(p)=phi(p^2-1)/(p^2-1).
> 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^2-1)/4=
> 2*3*5*7*11*13*19*23*29*31*41*73*97
>
> What comes next?

Nice concrete follow-on from Jon's original.

I can't see a clever way to improve on brute-force 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 squarefree-smooths 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!?
http://mailplus.yahoo.com
• ... ... I believe it continues as follows 181333151 267190769 331413809 376754951 636510601 1737265531 3019962791 One can obtain fairly low values of
Message 6 of 20 , Jan 3, 2003
• 0 Attachment
> Let f(p)=phi(p^2-1)/(p^2-1).
> Say a prime p is "lowest yet" if there is
> no prime q<p with f(q)<f(p).
> The "lowest yet" sequence begins

<snip>

> 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
p-1=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^2-1 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
• ... I proved the first 4 of your addenda with the unsmart brute-force Pari-GP source m=1;mp=430*10^6; Jon please note
Message 7 of 20 , Jan 4, 2003
• 0 Attachment
Richard:

> I believe it continues as follows
> 181333151
> 267190769
> 331413809
> 376754951
> 636510601
> 1737265531
> 3019962791

the unsmart brute-force Pari-GP source

forprime(p=2,mp,n=p^2-1;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^2-1;s=eulerphi(n)/n;if(s
Message 8 of 20 , Jan 4, 2003
• 0 Attachment
forprime(p=2,mp,n=p^2-1;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/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
• ... forprime is faster than nextprime if you can afford the memory up to p=430M
Message 9 of 20 , Jan 4, 2003
• 0 Attachment
> use 'p=nextprime(p+1)' rather than 'forprime(p='
'forprime' is faster than 'nextprime'
if you can afford the memory up to p=430M
• ... Possibly. I m using Chongo s calc (Curt Landon Noll, record prime finder 2-3 decades ago), which is the standard GNU utility. The whereabouts of the
Message 10 of 20 , Jan 4, 2003
• 0 Attachment
--- Jon Perry <perry@...> wrote:
> 'm=1;mp=430*10^6; \\ Jon please note
> forprime(p=2,mp,n=p^2-1;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'?

Possibly. I'm using Chongo's calc (Curt Landon Noll, record prime finder 2-3
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 well-defined.
(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!?
http://mailplus.yahoo.com
• I expect it to drift downards so it s not well-defined. (or maybe it is, maybe it s zero. On average numbers have 1/eps distinct divisors, i.e. a divergent
Message 11 of 20 , Jan 4, 2003
• 0 Attachment
'I expect it to drift downards so it's not well-defined.
(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/3-eps from numbers with a few prime factors larger than 2 or 3 in p+1
and p-1.'

Cough, cough. You make these up, or do they come naturally?

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
• ... Where the 3 was already pointed out as a typo. ... OK John. Which of the two statements do you think is wrong? And why? Come on, show us the flaws, I yearn
Message 12 of 20 , Jan 4, 2003
• 0 Attachment
--- Jon Perry <perry@...> wrote:

Quoting me:

> 'I expect it to drift downards so it's not well-defined.
> (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/3-eps from numbers with a few prime factors larger than 2 or 3 in p+1
> and p-1.'

Where the 3 was already pointed out as a typo.

> 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 razer-sharp
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!?
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
Message 13 of 20 , Jan 4, 2003
• 0 Attachment
'£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/