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

Yet another factoring puzzle

Expand Messages
  • djbroadhurst
    History: In the olden days, factorization of large integers required critical judgement. One had to decide when to give up on an elliptic-curve method (ECM) in
    Message 1 of 23 , Aug 23, 2013
    View Source
    • 0 Attachment
      History: In the olden days, factorization of large integers
      required critical judgement. One had to decide when to give
      up on an elliptic-curve method (ECM) in favour of a self-
      initializing quadratic sieve (SIQS) or a number-field sieve
      that might be special (SNFS) or general (GNFS).

      Automated choice: Then a benign and skilful programmer, Ben
      Buhrow, automated much of this process, for the benefit of
      users who care more about results than methods. With
      unwonted modesty, Ben called his package "yet another
      factoring utility" (YAFU). He did such a good job that
      nowadays many users may avoid learning both the principles
      behind the methods of factorization and also the criteria
      for choosing between those methods.

      Caveat: There remain two areas where critical thought is
      advisable: algebraic factorization and polynomial selection.

      Practice: Here are some exercises where wetware helps. I
      have tried to grade them, starting with easy pencil-and-
      paper mathematics and ending with something approaching
      state-of-the-art factorization.

      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.

      Comments: Exercises 1 to 4 require only pencil and paper.
      Exercises 5 and 6 may be solved quickly, using OpenPFGW.
      Exercise 7 and 8 are more demanding and involve informed
      choices between ECM, SNFS and GNFS.

      David
    • Kevin Acres
      [snip] ... I did work out an algorithm to derive one divisor of F(n)/4 for odd n, but that s probably a long way from proving it composite. [snip] Regards,
      Message 2 of 23 , Aug 24, 2013
      View Source
      • 0 Attachment
        [snip]
        >
        > Practice: Here are some exercises where wetware helps. I
        > have tried to grade them, starting with easy pencil-and-
        > paper mathematics and ending with something approaching
        > state-of-the-art factorization.
        >
        > 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.

        I did work out an algorithm to derive one divisor of F(n)/4 for odd n, but
        that's probably a long way from proving it composite.

        [snip]


        Regards,

        Kevin.
      • djbroadhurst
        ... What is needed is a formula: F(n)=L(n)*M(n). Then it suffices to show that each of L(n) and M(n) has an odd prime divisor for odd n 1. Here is a clue:
        Message 3 of 23 , Aug 24, 2013
        View Source
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "Kevin Acres" <research@...> wrote:

          > > Definition: Let F(n) = ((5^n-9)/4)^2-5 for integer n > 0.
          > > Exercise 2: For odd n > 1, prove that F(n)/4 is composite.
          >
          > I did work out an algorithm to derive one divisor of F(n)/4 for odd n, but
          > that's probably a long way from proving it composite.

          What is needed is a formula: F(n)=L(n)*M(n). Then it suffices
          to show that each of L(n) and M(n) has an odd prime divisor
          for odd n > 1. Here is a clue:

          4*F(11) = 24414063^2 - 15625^2

          David
        • mikeoakes2
          ... Aurelius [or somebody] he say: 16*F(n) = 5^(2*n)-18*5^n+1= (5^n-2*5^[(n+1)/2]+1) * (5^n-2*5^[(n+1)/2]+1) Mike
          Message 4 of 23 , Aug 24, 2013
          View Source
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
            >
            > --- In primenumbers@yahoogroups.com, "Kevin Acres" <research@> wrote:
            >
            > > > Definition: Let F(n) = ((5^n-9)/4)^2-5 for integer n > 0.
            > > > Exercise 2: For odd n > 1, prove that F(n)/4 is composite.
            > >
            > > I did work out an algorithm to derive one divisor of F(n)/4 for odd n, but
            > > that's probably a long way from proving it composite.
            >
            > What is needed is a formula: F(n)=L(n)*M(n). Then it suffices
            > to show that each of L(n) and M(n) has an odd prime divisor
            > for odd n > 1. Here is a clue:
            >
            > 4*F(11) = 24414063^2 - 15625^2
            >

            Aurelius [or somebody] he say:

            16*F(n) = 5^(2*n)-18*5^n+1=
            (5^n-2*5^[(n+1)/2]+1) * (5^n-2*5^[(n+1)/2]+1)

            Mike
          • djbroadhurst
            ... David
            Message 5 of 23 , Aug 24, 2013
            View Source
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              "mikeoakes2" <mikeoakes2@...> wrote:

              > Aurelius [or somebody] he say:
              >
              > 16*F(n) = 5^(2*n)-18*5^n+1=
              > (5^n-2*5^[(n+1)/2]+1) * (5^n-2*5^[(n+1)/2]+1)

              Wiki, it say:

              > There is evidence dating this algorithm as far back as
              > the Ur III dynasty.

              David
            • Kermit Rose
              ... F(n) = ((5^n-9)/4)^2-5 ... Similar formulas can be constructed easily. (5^((n-a)/2) + 3)(5^((n+a)/2) - 3) = 5^n + 3 * (5^((n+a)/2) - 5^((n-a)/2)) - 9 = 5^n
              Message 6 of 23 , Aug 25, 2013
              View Source
              • 0 Attachment
                On Sat Aug 24, 2013 7:19 am ((PDT)), mikeoakes2 wrote:
                > 1b. Re: Yet another factoring puzzle
                > Posted by: "mikeoakes2" mikeoakes2@... mikeoakes2
                > Date: Sat Aug 24, 2013 7:19 am ((PDT))

                F(n) = ((5^n-9)/4)^2-5


                >
                > Aurelius [or somebody] he say:
                >
                > 16*F(n) = 5^(2*n)-18*5^n+1=
                > (5^n-2*5^[(n+1)/2]+1) * (5^n-2*5^[(n+1)/2]+1)
                >
                > Mike


                Similar formulas can be constructed easily.

                (5^((n-a)/2) + 3)(5^((n+a)/2) - 3)
                = 5^n + 3 * (5^((n+a)/2) - 5^((n-a)/2)) - 9
                = 5^n + 3 * (5^a -1) (5^((n-a)/2) - 9

                Working in reverse we would have the mysterious factoring
                of

                5^n + 3 * (5^a -1) (5^((n-a)/2) - 9

                = (5^((n-a)/2) + 3)(5^((n+a)/2) - 3)

                Similar surprising factoring occurs in polynomials.

                (2 x^2 - 2 x y + y^2) (2 x^2 + 2 x y + y^2 )
                = 4 x^4 + 4 x^2 y^2 - 4 x^2 y^2 + y^4
                = 4 x^4 + y^4

                Kermit
              • djbroadhurst
                ... Not just similar but really the same thing. Exercise 1: print(factor(((x^2-9)/4)^2-5)[,1]~) [x^2 - 4*x - 1, x^2 + 4*x - 1] See
                Message 7 of 23 , Aug 25, 2013
                View Source
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com,
                  Kermit Rose <kermit@...> wrote:

                  > Similar surprising factoring occurs in polynomials.

                  Not just similar but really the same thing.

                  Exercise 1:
                  print(factor(((x^2-9)/4)^2-5)[,1]~)
                  [x^2 - 4*x - 1, x^2 + 4*x - 1]
                  See http://tech.groups.yahoo.com/group/primenumbers/message/23727

                  Exercise 2:
                  print(factor(((5*x^2-9)/4)^2-5)[,1]~)
                  [5*x^2 - 10*x + 1, 5*x^2 + 10*x + 1]
                  See http://tech.groups.yahoo.com/group/primenumbers/message/25340

                  So how about Exercise 3, then?
                  See http://tech.groups.yahoo.com/group/primenumbers/message/25337

                  David (prompting)
                • Chroma
                  ... 1. For even n 0 F(n)-2 are divisible by 3 2. For even k 0 F(2k-1)-2 are divisible by 2 3. For even k 0 F[3k-1)-2 are divisible by 3^2 4. For even k 0
                  Message 8 of 23 , Aug 26, 2013
                  View Source
                  • 0 Attachment
                    djbroadhurst wrote :

                    > Definition: Let F(n) = ((5^n-9)/4)^2-5 for integer n > 0
                    >
                    > Exercise 1: .........

                    1. For even n>0 F(n)-2 are divisible by 3
                    2. For even k>0 F(2k-1)-2 are divisible by 2
                    3. For even k>0 F[3k-1)-2 are divisible by 3^2
                    4. For even k>0 F(6k-2)-2 are divisible by 7
                    5. For even k>0 F(14k-5)-2 are divisible by 29

                    How can you prove this relationship?.

                    marian otremba
                  • djbroadhurst
                    ... F(n)=((5^n-9)/4)^2-5; if(znorder(Mod(5,29))==14&&Mod(F(9),29)==2,print( proven )); proven David
                    Message 9 of 23 , Aug 26, 2013
                    View Source
                    • 0 Attachment
                      --- In primenumbers@yahoogroups.com,
                      Chroma <chromatella@...> wrote:

                      > For even k>0 F(14k-5)-2 are divisible by 29
                      > How can you prove this relationship?.

                      F(n)=((5^n-9)/4)^2-5;
                      if(znorder(Mod(5,29))==14&&Mod(F(9),29)==2,print(" proven"));

                      proven

                      David
                    • bobb7772004
                      Aurelius surely did NOT mean this to be a square: > 16*F(n) = 5^(2*n)-18*5^n+1= > (5^n-2*5^[(n+1)/2]+1) * (5^n-2*5^[(n+1)/2]+1) --- In
                      Message 10 of 23 , Sep 1, 2013
                      View Source
                      • 0 Attachment
                        Aurelius surely did NOT mean this to be a square: > 16*F(n) = 5^(2*n)-18*5^n+1= > (5^n-2*5^[(n+1)/2]+1) * (5^n-2*5^[(n+1)/2]+1) --- In primenumbers@yahoogroups.com, <d.broadhurst@...> wrote: --- In primenumbers@yahoogroups.com ,
                        "mikeoakes2" <mikeoakes2@...> wrote:

                        > Aurelius [or somebody] he say:
                        >
                        > 16*F(n) = 5^(2*n)-18*5^n+1=
                        > (5^n-2*5^[(n+1)/2]+1) * (5^n-2*5^[(n+1)/2]+1)

                        Wiki, it say:

                        > There is evidence dating this algorithm as far back as
                        > the Ur III dynasty.

                        David
                        The second factor should be 5^n PLUS 2*5 etc. Another schoolboy howler.
                      • djbroadhurst
                        ... Obviously. ... No. Just someome typing good maths even faster than his agile brain was working. David
                        Message 11 of 23 , Sep 1, 2013
                        View Source
                        • 0 Attachment
                          --- In primenumbers@yahoogroups.com, <bobb777@...> wrote:

                          > > (5^n-2*5^[(n+1)/2]+1) * (5^n-2*5^[(n+1)/2]+1)
                          > The second factor should be 5^n PLUS 2*5 etc.

                          Obviously.

                          > Another schoolboy howler.

                          No. Just someome typing good maths even faster
                          than his agile brain was working.

                          David
                        • j_chrtn
                          Hi David, ... F(265) factorization : 2^2 239 739 3001 65482831 256219297361 1693591423953203161 30357718855490049445651878883131113101
                          Message 12 of 23 , Sep 1, 2013
                          View Source
                          • 0 Attachment
                            Hi David,

                            --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                            >
                            >
                            > Exercise 9: Factorize F(265) completely.
                            >

                            F(265) factorization :
                            2^2
                            239
                            739
                            3001
                            65482831
                            256219297361
                            1693591423953203161
                            30357718855490049445651878883131113101
                            102797863053051886296311988529254933989146480741
                            3877828174415305750004694470712933786753853898797149341
                            269073781314228860816753896980501633755080784585248485757620731
                            9064688734866670980979961151235275322157501870878158907210451074982503913520844038924855331866069982604479273540797473039

                            F(263): one composite factor remaining (in progress).

                            JL
                          • djbroadhurst
                            ... Congrats. When I did it, I was running ECM and SNFS in parallel and pulled the plug on SNFS when ECM found a p48. ... Here I used GNFS on the C130. David
                            Message 13 of 23 , Sep 1, 2013
                            View Source
                            • 0 Attachment
                              --- In primenumbers@yahoogroups.com,
                              "j_chrtn" <j_chrtn@...> wrote:

                              > > Exercise 9: Factorize F(265) completely.
                              > F(265) factorization :
                              > 2^2
                              > 239
                              > 739
                              > 3001
                              > 65482831
                              > 256219297361
                              > 1693591423953203161
                              > 30357718855490049445651878883131113101
                              > 102797863053051886296311988529254933989146480741
                              > 3877828174415305750004694470712933786753853898797149341
                              > 269073781314228860816753896980501633755080784585248485757620731
                              > 9064688734866670980979961151235275322157501870878158907210451074982503913520844038924855331866069982604479273540797473039

                              Congrats. When I did it, I was running ECM and SNFS in parallel
                              and pulled the plug on SNFS when ECM found a p48.

                              > F(263): one composite factor remaining (in progress).

                              Here I used GNFS on the C130.

                              David
                            • j_chrtn
                              ... I first removed small factors with factorize program from libgmp demos (= trial divisions + Pollard s rho). Then I found all other factors with ECM (using
                              Message 14 of 23 , Sep 1, 2013
                              View Source
                              • 0 Attachment
                                --- In primenumbers@yahoogroups.com, "djbroadhurst" <david.broadhurst@...> wrote:
                                >
                                >
                                > Congrats. When I did it, I was running ECM and SNFS in parallel
                                > and pulled the plug on SNFS when ECM found a p48.
                                >
                                > > F(263): one composite factor remaining (in progress).
                                >
                                > Here I used GNFS on the C130.
                                >
                                > David
                                >

                                I first removed small factors with factorize program from libgmp demos (= trial divisions + Pollard's rho).
                                Then I found all other factors with ECM (using P-1 mode for some of them) except for C118 = 3877828174415305750004694470712933786753853898797149341 * 269073781314228860816753896980501633755080784585248485757620731 for which I directly chose cado-nfs.

                                For the remaining factor C130 of F(263), I've chosen both ECM and cado-nfs. Still waiting for the result...

                                cado-nfs is really a cadeau. Thanks to its authors.

                                JL
                              • j_chrtn
                                ... C130 factorization completed this morning (cado-nfs winner vs ecm). Finally : F(263) = 2^2 11 941 88079 40541279 53849801 3709997079374701
                                Message 15 of 23 , Sep 4, 2013
                                View Source
                                • 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 16 of 23 , Sep 4, 2013
                                  View Source
                                  • 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 17 of 23 , Sep 16, 2013
                                    View Source
                                    • 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 18 of 23 , Sep 16, 2013
                                      View Source
                                      • 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 19 of 23 , Sep 16, 2013
                                        View Source
                                        • 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 20 of 23 , Sep 18, 2013
                                          View Source
                                          • 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 21 of 23 , Sep 19, 2013
                                            View Source
                                            • 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 22 of 23 , Sep 25, 2013
                                              View Source
                                              • 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 23 of 23 , Sep 27, 2013
                                                View Source
                                                • 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.