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

primorial-factorial prime 2

Expand Messages
  • mcnamara_gio
    What is known about primes of this form: n!/n#+1
    Message 1 of 6 , Jan 28, 2005
    • 0 Attachment
      What is known about primes of this form: n!/n#+1
    • Jens Kruse Andersen
      ... They are called compositorial: http://primes.utm.edu/glossary/page.php?sort=Compositorial Go to http://primes.utm.edu/primes/search.php Write compositorial
      Message 2 of 6 , Jan 28, 2005
      • 0 Attachment
        mcnamara_gio wrote:

        > What is known about primes of this form: n!/n#+1

        They are called compositorial:
        http://primes.utm.edu/glossary/page.php?sort=Compositorial

        Go to http://primes.utm.edu/primes/search.php
        Write compositorial as text comment.
        Click on "all verified primes" and search to get this:

        ----- -------------------------------- ------- ---- ---- --------------
        rank description digits who year comment
        ----- -------------------------------- ------- ---- ---- --------------
        1759 20943!/20939#-1 72401 p16 2000 Compositorial
        2738 18160!/18149#-1 61635 p16 2000 Compositorial
        3814 17258!/17257#+1 58207 p16 2000 Compositorial
        7090 15250!/15241#-1 50623 p16 2000 Compositorial
        8127 13917!/13913#+1 45631 p16 2000 Compositorial
        8676 13724!/13723#-1 44919 p16 2000 Compositorial
        11390 10977!/10973#-1 34876 p16 2000 Compositorial
        16188 8711!/8707#-1 26816 p7 1999 Compositorial
        18535 6851!/6841#+1 20374 p34 2000 Compositorial
        20253 6187!/6173#+1 18135 p7 1999 Compositorial
        27832 3692!/3691#+1 9996 p7 1999 Compositorial
        ----- -------------------------------- ------- ---- ---- --------------

        --
        Jens Kruse Andersen
      • Décio Luiz Gazzoni Filho
        ... Mike Oakes already gave the asymptotics of primes of this form in a very recent post, but I ll go through a similar argument and arrive at my own, slightly
        Message 3 of 6 , Jan 28, 2005
        • 0 Attachment
          On Friday 28 January 2005 06:40, you wrote:
          > What is known about primes of this form: n!/n#+1

          Mike Oakes already gave the asymptotics of primes of this form in a very
          recent post, but I'll go through a similar argument and arrive at my own,
          slightly modified formula. Whether it's better remains to be seen.

          Just a comment before we start: what about the symmetric from n!/n# - 1? I
          don't know why we shouldn't analyze it.

          There is a theorem of Legendre that says the following: n! is divisible by p
          with multiplicity

          sum_{k >= 1} floor(n/p^k),

          while n# is divisible by each p up to n with multiplicity one. Dividing one by
          another, it's not hard to see that only factors of multiplicity 1 are
          canceled in n!. These are exactly those for which floor(n/p) = 1 (no use
          thinking about higher powers, because if floor(n/p) = 1, then floor(n/p^2) =
          floor(n/p^3) = ... = 0). It's not hard to see these are the primes from
          floor(n/2) to n itself.

          Thus, n!/n# is divisible by all primes up to floor(n/2). I'll drop the floor()
          operation for the upcoming asymptotic analysis. From my previous post, you
          should know by now that n!/n# plus/minus 1 isn't divisible by any of these
          primes, by Euclid's argument.

          Assuming that n!/n# plus/minus 1 are `random' numbers (i.e. nothing is known
          about their factors), they would be prime with probability 1/log(n!/n#). I'm
          dropping the plus/minus 1 at the end because it doesn't affect the result,
          either asymptotically or in practice. But they're not random, they're
          divisible by all primes up to n/2. Thus we use Mertens's theorem to adjust
          the probability by exp(gamma) log(n/2) = exp(gamma) (log(n) - log(2)) =
          exp(gamma) (log(n) - 0.693). We also multiply this probability by 2 to
          account for the two forms n!/n# + 1 and n!/n# - 1.

          Now we need to estimate log(n!/n#) = log(n!) - log(n#). The first term is well
          known to be n(log(n) - 1). The second term, according to the paper by Chris
          Caldwell and Yves Gallot that Mike Oakes linked to on a previous post, is
          approximately n itself. (A side note: I computed something similar to
          log(n#), except that a prime p appeared to the highest power < n, i.e.
          2^floor(log_2 n) 3^floor(log_3 n) ... and indeed these values are very close
          to n itself, I believe even closer than log(n#).) Anyway...

          log(n!/n#) = log(n!) - log(n#) = n(log(n) - 1) - n = n(log(n) - 2).

          Thus, the number of compositorial primes of both forms (plus and minus) up to
          n is expected to be

          sum_{k=1..n} 2 exp(gamma) log(k/2)/(k(log(k) - 2)).

          And asymptotically (i.e.log(k/2) ~ log(k), k(log(k) - 2) ~ k log(k)) we have

          sum_{k=1..n} 2 exp(gamma) log(k)/(k log(k)) = sum_{k = 1..n} 2 exp(gamma)/k,

          which, somewhat surprisingly, is nearly the same formula for n! plus/minus n#
          plus/minus 1, except that we only have two possible forms here instead of
          four, accounting for the factor 2 of difference.

          Let's try this formula with the data provided by Mike Oakes. For n <= 10000,
          34.27 primes were expected, while the actual count is 44. But let's consider
          1000 <= n <= 10000 for a more accurate picture: in that case 9.995 primes
          were expected but 8 were found. Again, anyone willing to throw more CPU power
          at the problem so we can verify the asymptotics is welcome to do so.

          Décio


          [Non-text portions of this message have been removed]
        • mikeoakes2@aol.com
          ... As well as the prime pages link supplied by Jens, you should also visit this dedicated page (albeit last updated in 2000):-
          Message 4 of 6 , Jan 28, 2005
          • 0 Attachment
            >What is known about primes of this form: n!/n#+1

            As well as the prime pages link supplied by Jens, you should also visit this
            dedicated page (albeit last updated in 2000):-
            _http://www.denhulster.nl/primeform/compositorials.html_
            (http://www.denhulster.nl/primeform/compositorials.html)
            which I cited in my recent post on the subject of compositorials.

            -Mike Oakes



            [Non-text portions of this message have been removed]
          • ed pegg
            Frits Staudt sent me an interesting observation on Fermat factorizations. A data source on them: http://www.prothsearch.net/fermat.html He added up the k s,
            Message 5 of 6 , Jul 28, 2005
            • 0 Attachment
              Frits Staudt sent me an interesting observation on Fermat factorizations.
              A data source on them: http://www.prothsearch.net/fermat.html

              He added up the k's, and noticed the sum divisible by higher powers of 2.

              F5 is 5 2^7+1 * 52347 2^7+1
              Observation: 5+52347 = 52352 = 409 2^7

              F6 is 1071 2^8+1 * 262814145745 2^8+1
              Observation: 1071 + 262814145745 = 1026617761 2^8

              F7 Observation: 116503103764643 + 11141971095088142685
              = 21761889840218569 2^9

              F8 Observation: 604944512477 +
              45635566267264637582599393652151804972681268330878021767715 =
              22282991341437811319628610181714748521817025552481917129 2^11

              Is this obvious/interesting?

              Ed Pegg Jr
            • Mc Laughlin, James
              Hello Ed, It is fairly obvious. If F_n = 2^(2^n)+1 = (2^(n+2)k+1)*(2^(n+2)l+1) = 2^(2n+4)k*l + 2^(n+2)(k+l) +1 then 2^(2^n-n-2)=2^(n+2)k*l + (k+l) , so 2^(n+2)
              Message 6 of 6 , Jul 28, 2005
              • 0 Attachment
                Hello Ed,

                It is fairly obvious.

                If
                F_n = 2^(2^n)+1 = (2^(n+2)k+1)*(2^(n+2)l+1) = 2^(2n+4)k*l + 2^(n+2)(k+l) +1

                then

                2^(2^n-n-2)=2^(n+2)k*l + (k+l) ,

                so 2^(n+2) | (k+l).


                Jimmy Mc Laughlin.

                http://www.trincoll.edu/~jmclaugh/


                ________________________________

                From: primenumbers@yahoogroups.com on behalf of ed pegg
                Sent: Thu 7/28/2005 12:58 PM
                To: primenumbers@yahoogroups.com; durman@...
                Subject: [PrimeNumbers] An observation on Fermat factorizations.


                Frits Staudt sent me an interesting observation on Fermat factorizations.
                A data source on them: http://www.prothsearch.net/fermat.html

                He added up the k's, and noticed the sum divisible by higher powers of 2.

                F5 is 5 2^7+1 * 52347 2^7+1
                Observation: 5+52347 = 52352 = 409 2^7

                F6 is 1071 2^8+1 * 262814145745 2^8+1
                Observation: 1071 + 262814145745 = 1026617761 2^8

                F7 Observation: 116503103764643 + 11141971095088142685
                = 21761889840218569 2^9

                F8 Observation: 604944512477 +
                45635566267264637582599393652151804972681268330878021767715 =
                22282991341437811319628610181714748521817025552481917129 2^11

                Is this obvious/interesting?

                Ed Pegg Jr



                Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
                The Prime Pages : http://www.primepages.org/





                ________________________________

                YAHOO! GROUPS LINKS



                * Visit your group "primenumbers <http://groups.yahoo.com/group/primenumbers> " on the web.

                * To unsubscribe from this group, send an email to:
                primenumbers-unsubscribe@yahoogroups.com <mailto:primenumbers-unsubscribe@yahoogroups.com?subject=Unsubscribe>

                * Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service <http://docs.yahoo.com/info/terms/> .


                ________________________________
              Your message has been successfully submitted and would be delivered to recipients shortly.