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

Re: Yet another factoring puzzle

Expand Messages
  • j_chrtn
    ... C130 factorization completed this morning (cado-nfs winner vs ecm). Finally : F(263) = 2^2 11 941 88079 40541279 53849801 3709997079374701
    Message 1 of 23 , Sep 4 11:15 AM
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "djbroadhurst" <david.broadhurst@...> wrote:
      >
      >
      > > F(263): one composite factor remaining (in progress).
      >
      > Here I used GNFS on the C130.
      >
      > David
      >

      C130 factorization completed this morning (cado-nfs winner vs ecm).

      Finally :
      F(263) =
      2^2
      11
      941
      88079
      40541279
      53849801
      3709997079374701
      23529341871144986702279
      7270487490315018281073601513510602536818804246566820732218199
      790942341954447264420872400154902667291367695120485038995898872524619
      711892421814353474455471503465724397364909744377767780766071778400352308618205366660863738451363497318680099295967052261874590114183928845236941340734473602381665606275060651

      JL
    • djbroadhurst
      ... Congrats, again, J-L. This link should show all the factorizations from n=261 to n=290: http://preview.tinyurl.com/mx3cdoe David
      Message 2 of 23 , Sep 4 1:02 PM
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "j_chrtn" <j_chrtn@...> wrote:

        > F(263) =

        Congrats, again, J-L.
        This link should show all the factorizations from n=261 to n=290:
        http://preview.tinyurl.com/mx3cdoe

        David
      • djbroadhurst
        ... As you can see, Exercise 8 was censored :-) As far as I can tell, no-one (apart from the setter) yet solved Exercise 6, which can be done in less than 2
        Message 3 of 23 , Sep 16 12:10 PM
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:

          > Definition: Let F(n) = ((5^n-9)/4)^2-5 for integer n > 0.
          >
          > Exercise 1: For even n > 2, prove that F(n) is composite.
          >
          > Exercise 2: For odd n > 1, prove that F(n)/4 is composite.
          >
          > Exercise 3: For k > 1, prove that F(3*k) has at least 4 odd
          > prime divisors.
          >
          > Exercise 4: Factorize F(6) = 15241211 completely, by hand.
          >
          > Exercise 5: Find the complete factorization of F(n) for at
          > least one odd integer n > 250.
          >
          > Exercise 6: Find the complete factorization of F(n) for at
          > least one even integer n > 600.
          >
          > Exercise 7: Factorize F(263) completely.
          >
          > Exercise 9: Factorize F(265) completely.

          As you can see, Exercise 8 was censored :-)

          As far as I can tell, no-one (apart from the setter)
          yet solved Exercise 6, which can be done in less
          than 2 minutes, using OpenPFGW. What is remarkable
          about this exercise is that it can be solved so
          quickly. Heuristically, that was not to be expected.

          Thanks to Bernardo Boncompagni, Mike Oakes and
          Jean-Louis Charton, for disposing neatly of the
          other exercises, and to Ben Buhrow, for his
          excellent package, Yafu.

          David
        • j_chrtn
          ... For sure one can find this solution quickly using openpfgw. But the smart guy now knowing that you (or others) have filled in factordb with many numbers of
          Message 4 of 23 , Sep 16 4:00 PM
          • 0 Attachment



            --- In primenumbers@yahoogroups.com, <david.broadhurst@...> wrote:

            --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:


            > As you can see, Exercise 8 was censored :-)
            >
            > As far as I can tell, no-one (apart from the setter)
            > yet solved Exercise 6, which can be done in less
            > than 2 minutes, using OpenPFGW. What is remarkable
            > about this exercise is that it can be solved so
            > quickly. Heuristically, that was not to be expected.

            For sure one can find this solution quickly using openpfgw.

            But the smart guy now knowing that you (or others) have filled in factordb with many numbers of this form just has to type http://factordb.com/index.php?query=%28%285^n-9%29%2F4%29^2-5&use=n&perpage=20&format=1&sent=1&PR=1&PRP=1&C=1&CF=1&U=1&FF=1&VP=1&EV=1&OD=1&VC=1&n=600

            to find the solution.

             

            :-)

             

            J-L 

             

            PS: I really did F(263) and F(265) factorization completely. I did not check factordb.

             

          • djbroadhurst
            ... Indeed, it was I who added http://factordb.com/index.php?id=1100000000464478896 with factors p404 and p414. Jean-Louis gets full marks for exploiting
            Message 5 of 23 , Sep 16 5:08 PM
            • 0 Attachment
              Jean-Louis Charton wrote:

              > For sure one can find this solution quickly using openpfgw.
              > But the smart guy now knowing that you (or others) have filled
              > in factordb with many numbers of this form just has to type...

              Indeed, it was I who added
              http://factordb.com/index.php?id=1100000000464478896
              with factors p404 and p414.

              Jean-Louis gets full marks for exploiting factordb,
              instead of doing what I intended, along the lines of

              $ more abc

              ABC2 25^$a-4*5^$a-1&25^$a+4*5^$a-1
              a: from 301 to 304

              $ pfgw -f -d -e20000000 abc

              25^301-4*5^301-1 has factors: 2^2*7229
              25^302-4*5^302-1 has factors: 2^2*3173791
              25^303-4*5^303-1 has factors: 2^2*1931*934579
              25^304-4*5^304-1 has factors: 2^2*11*29*1289*1759*9511*27851
              (25^304-4*5^304-1)/(2^2*11*29*1289*1759*9511*27851) is 3-PRP!
              (0.0057s+0.2797s)
              25^304+4*5^304-1 has factors: 2^2*1439*17390951
              (25^304+4*5^304-1)/(2^2*1439*17390951) is 3-PRP!
              (0.0058s+0.3055s)

              But now, J-L, are you able to explain my comment:

              > What is remarkable about this exercise is that it can be
              > solved so quickly. Heuristically, that was not to be expected.

              Can you quantify my suprise?

              AmitiƩs

              David
            • j_chrtn
              ... Well, I would say that for n = 600, both algebraic factors are more than 415 digits and trial factoring them with pfgw up to 20000000 with -d option you
              Message 6 of 23 , Sep 18 4:39 PM
              • 0 Attachment

                 


                --- In primenumbers@yahoogroups.com, <david.broadhurst@...> wrote:

                >But now, J-L, are you able to explain my comment:
                >
                >> What is remarkable about this exercise is that it can be
                >> solved so quickly. Heuristically, that was not to be expected.
                >
                >Can you quantify my suprise?
                >

                Well, I would say that for n >= 600, both algebraic factors are more than 415 digits and trial factoring them with pfgw up to 20000000 with -d option you may remove a 20000000-smooth composite factor of say 10 or 15 digits. This leave 2 factors of more than 400 digits. The "probability" for one such factor to be prime is roughly 1/l(10^400), that is about 0.001. So for both factors to be prime the probability is about 0.000001.

                Am I right ?

                Amicalement,

                J-L
              • djbroadhurst
                ... We seek complete factorization of both of the cofactors 25^k-4*5^k-1 and 25^k+4*5^k-1 for some k 300, where each has more than 400 decimal digits. We had
                Message 7 of 23 , Sep 19 12:26 PM
                • 0 Attachment
                  Jean-Louis Carton wrote:

                  > So for both factors to be prime the probability is about 0.000001.

                  We seek complete factorization of both of the cofactors
                  25^k-4*5^k-1 and 25^k+4*5^k-1
                  for some k > 300, where each has more than
                  400 decimal digits. We had better avoid
                  the case k = 0 mod 3, where each cofactor
                  has an algebraic factorization, which is
                  here a distinct disadvantage.

                  Suppose that we sieve out primes to depth d
                  and hope for what is left to yield a
                  a pair of PRPs as here, with k = 304:

                  (25^304-4*5^304-1)/(2^2*11*29*1289*1759*9511*27851) is 3-PRP!
                  (25^304+4*5^304-1)/(2^2*1439*17390951) is 3-PRP!

                  The probability for success for a single value of k
                  coprime to 3 is of order

                  (exp(Euler)*log(p)/log(25))^2/k^2

                  Setting p = 2*10^7 and summing over /all/ k > 300,
                  the probability that Exercise 6 has /no/ solution is

                  exp(-2/3*(exp(Euler)*log(2*10^7)/log(25))^2/301) =~ 83%

                  In fact it has a solution almost immediately, at k = 304.

                  David
                • Phil Carmody
                  ... But is that more or less remarkable than the expectation of any one of Phil Taylor s darts landing in the region around where it actually landed? You only
                  Message 8 of 23 , Sep 25 3:08 PM
                  • 0 Attachment
                    On Mon, 9/16/13, djbroadhurst wrote:
                    --- "djbroadhurst" <d.broadhurst@...> wrote:
                    > > Exercise 6: Find the complete factorization of F(n) for at
                    > > least one even integer n > 600.
                    > As far as I can tell, no-one (apart from the setter)
                    > yet solved Exercise 6, which can be done in less
                    > than 2 minutes, using OpenPFGW. What is remarkable
                    > about this exercise is that it can be solved so
                    > quickly. Heuristically, that was not to be expected.

                    But is that more or less remarkable than the expectation of
                    any one of Phil Taylor's darts landing in the region around
                    where it actually landed? You only chose that target after
                    the arrow had landed, I'm sure.

                    How many mathematical diversions have you looked at
                    via the medium of numerical computation? How many of
                    them would you expect to be remarkably easier than
                    expected to solve? Probably a non-zero answer. Don't
                    be surprised that one particular example was one.

                    Knowing what he's trying to say, even if he's not getting
                    it across clearly,
                    Phil
                    --
                    () ASCII ribbon campaign () Hopeless ribbon campaign
                    /\ against HTML mail /\ against gratuitous bloodshed

                    [stolen with permission from Daniel B. Cristofani]
                  • djbroadhurst
                    ... It happened thus: 1) I determined to factorize F(n)=((n^2-9)/4)^2-5 for n
                    Message 9 of 23 , Sep 27 2:52 PM
                    • 0 Attachment

                       ---In primenumbers@yahoogroups.com, <thefatphil@...> wrote:

                       

                      > You only chose that target after
                      > the arrow had landed, I'm sure.

                       

                      It happened thus:

                       

                      1) I determined to factorize F(n)=((n^2-9)/4)^2-5 for
                      n <= 300, completely. As later shown in "factordb", I succeeded.

                       

                      2) Meanwhile I ran OpenPFGW on n in [301,600], hoping for a
                      quick outlier and found none.

                       

                      3) I estimated the probability of an easily discoverable
                      completely factorization for n>600 and found it to be small.

                       

                      4) Recalling how I had once been caught out before by
                      a "probably no more" heuristic, I set a lone process running on
                      n in [601, 10000]  so as not to be caught out again by Jens.

                       

                      5) When I later looked  and pfgw.log, it had found a hit at
                      n=608.

                       

                      So yes, Phil, you are quite correct that the puzzle was set
                      after this finding. However the heuristic that I gave was
                      made prior to my discovery, else I would not have said that
                      I was surprised.

                       

                      The point that you are making (I think) is that I do such 
                      expsriments often and only notice when the result is unexpected.
                      I don't tell folk about all the boring times when a negative
                      heuristic is borne out by a null result. That is the selection

                      effect.

                       

                      David (guilty of not boring folk with what is routine)

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