Loading ...
Sorry, an error occurred while loading the content.

Is phi(p^2-1)/(p^2-1) bounded?

Expand Messages
  • Jon Perry
    Briefly: forprime (p=1000000,1000500, ep=eulerphi((p-1)*(p+1));print1(ep : ep/(p^2-1)*1.0 , )) indicates 0.22~
    Message 1 of 20 , Jan 3, 2003
    • 0 Attachment
      Briefly:

      forprime (p=1000000,1000500,
      ep=eulerphi((p-1)*(p+1));print1(ep":"ep/(p^2-1)*1.0","))

      indicates 0.22~< phi(p^2-1)/(p^2-1) <~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
    • Paul Leyland
      ... I don t see why your belief is justified based on a small sample and no analysis. Just because a function is bounded over a small range doesn t mean it
      Message 2 of 20 , Jan 3, 2003
      • 0 Attachment
        > Briefly:
        >
        > forprime (p=1000000,1000500,
        > ep=eulerphi((p-1)*(p+1));print1(ep":"ep/(p^2-1)*1.0","))
        >
        > indicates 0.22~< phi(p^2-1)/(p^2-1) <~0.33
        >
        > leading one to the belief that it tends to a limit...

        I don't see why your belief is justified based on a small sample and no analysis.

        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
      • Jon Perry
        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
        Message 3 of 20 , Jan 3, 2003
        • 0 Attachment
          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
        • richard_heylen <richard_heylen@yahoo.co.
          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
          Message 4 of 20 , Jan 3, 2003
          • 0 Attachment
            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
          • Phil Carmody
            ... Use calc instead. Or bc. Or the other calc . Or use gp and use p=nextprime(p+1) rather than forprime(p= . ... One of (p-1) and (p+1) is divisible by
            Message 5 of 20 , Jan 3, 2003
            • 0 Attachment
              --- Jon Perry <perry@...> wrote:
              > 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.

              Use 'calc' instead. Or bc. Or the other 'calc'. Or use gp and use
              'p=nextprime(p+1)' rather than 'forprime(p='.

              > 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.

              One of (p-1) and (p+1) is divisible by 2,
              the other is divisible by 4 or 2^i i>2

              One of (p-1) and (p+1) is divisible by 3.


              The 2s combine such that

              Phi((p-1)*(p+1)) = Phi(2.2^i.(p-1)/2.(p+1)/2^i)
              = 2^i.Phi((p-1)(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/3-eps from numbers with a few prime factors larger than 2 or 3 in p+1
              and p-1.

              e.g.
              499637 0.3333266618578673045764089881

              (23:01) gp > factor(499637-1)
              %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/3-eps 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
            • David Broadhurst <d.broadhurst@open.ac.u
              Jon Perry mistakenly claimed that ... Invoke it with -p10000000 to precompute primes to 10M. Limit is about 430M, as I recall, but then you need to allocate
              Message 6 of 20 , Jan 3, 2003
              • 0 Attachment
                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.
              • David Broadhurst <d.broadhurst@open.ac.u
                ... .......................? No. p=3 gives 1/2 and p=2 gives 2/3 which is maximal, for prime p.
                Message 7 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.
                • Phil Carmody
                  ... 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 8 of 20 , Jan 3, 2003
                  • 0 Attachment
                    --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
                    > 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!?
                    Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
                    http://mailplus.yahoo.com
                  • David Broadhurst <d.broadhurst@open.ac.u
                    ... 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 9 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
                    • David Broadhurst <d.broadhurst@open.ac.u
                      Let f(p)=phi(p^2-1)/(p^2-1). Say a prime p is lowest yet if there is no prime q
                      Message 10 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?
                      • Phil Carmody
                        ... 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 11 of 20 , Jan 3, 2003
                        • 0 Attachment
                          --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
                          > 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!?
                          Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
                          http://mailplus.yahoo.com
                        • Phil Carmody
                          ... 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 12 of 20 , Jan 3, 2003
                          • 0 Attachment
                            --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
                            > 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!?
                            Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
                            http://mailplus.yahoo.com
                          • richard_heylen <richard_heylen@yahoo.co.
                            ... ... I believe it continues as follows 181333151 267190769 331413809 376754951 636510601 1737265531 3019962791 One can obtain fairly low values of
                            Message 13 of 20 , Jan 3, 2003
                            • 0 Attachment
                              --- In primenumbers@yahoogroups.com, "David Broadhurst
                              <d.broadhurst@o...>" <d.broadhurst@o...> wrote:
                              > 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
                            • David Broadhurst <d.broadhurst@open.ac.u
                              ... 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 14 of 20 , Jan 4, 2003
                              • 0 Attachment
                                Richard:

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

                                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
                                forprime(p=2,mp,n=p^2-1;s=eulerphi(n)/n;if(s<m,m=s;print(p)))

                                David
                              • Jon Perry
                                m=1;mp=430*10^6; Jon please note forprime(p=2,mp,n=p^2-1;s=eulerphi(n)/n;if(s
                                Message 15 of 20 , Jan 4, 2003
                                • 0 Attachment
                                  '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'?

                                  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
                                • David Broadhurst <d.broadhurst@open.ac.u
                                  ... forprime is faster than nextprime if you can afford the memory up to p=430M
                                  Message 16 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
                                  • Phil Carmody
                                    ... 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 17 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!?
                                      Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
                                      http://mailplus.yahoo.com
                                    • Jon Perry
                                      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 18 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/
                                        http://www.users.globalnet.co.uk/~perry/DIVMenu/
                                        BrainBench MVP for HTML and JavaScript
                                        http://www.brainbench.com
                                      • Phil Carmody
                                        ... 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 19 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!?
                                          Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
                                          http://mailplus.yahoo.com
                                        • Jon Perry
                                          £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 20 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/
                                            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.