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

Re: [PrimeNumbers] QUESTION

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... It helps if you factor n^4 - 5n^2 + 4 as (n-2)(n-1)(n+1)(n+2). Right off the bat you already ensure that it has 4 factors, but you can do better. If n is a
    Message 1 of 5 , Mar 4, 2005
      On Friday 04 March 2005 12:28, you wrote:
      > WHAT ARE THE MINIMUM NUMBER OF FACTORS THAT THE EXPRESSION
      > n^4-5*(n^2)+4
      > WILL HAVE IF N IS A SET OF PRIME NUMBERS GREATER THAN 500

      It helps if you factor n^4 - 5n^2 + 4 as (n-2)(n-1)(n+1)(n+2). Right off the
      bat you already ensure that it has 4 factors, but you can do better. If n is
      a prime, then it's either == 1 or 2 mod 3; in the former case, both n-1 and
      n+2 are divisible by 3, and in the latter, both n-2 and n+1 are divisible by
      3. Also, obviously n-1 and n+1 are even, but furthermore, one of these is
      divisible by 4, so that (n-1)(n+1) = n^2 - 1 is divisible by 8. So you have
      five factors already, 2*2*2*3*3. Finally, and again by the pigeonhole
      principle and the fact that n is prime, one of the factors of your polynomial
      are divisible by 5. So the values of your polynomial are always divisible by
      2*2*2*3*3*5 when n is a prime > 5.

      This is the best we can do regarding factors of 2, 3 and 5. For instance, the
      polynomial evaluated at n = 509 is divisible by 8 but not 16, 9 but not 27
      and 5 but not 25.

      Since (for large enough n) none of this is going to fully cancel out any of
      the original factors of the polynomial, there's going to be at least 4 extra
      factors. The first n > 500 for which this lower bound is reached is n = 787,
      since

      n-2 = 785 = 5*157,
      n-1 = 786 = 2*3*131,
      n+1 = 788 = 2^2*197,
      n+2 = 789 = 3*263.

      The values n = 1229, 1669, 2083, 3371, 3461, 8221, 9013, ... also have only 4
      cofactors upon division by 2*2*2*3*3*5. This PARI/GP script can be used to
      compute the remaining values (just replace minp and maxp by whatever bounds
      interest you):

      forprime(n=minp,maxp,
      f = factorint(eval(n^4 - 5*n^2 + 4)/(2^3*3^2*5));
      k=sum(i=1,matsize(f)[1],f[i,2]);
      if(k==4,print(n" "f" "k));
      )

      With some modifications, you can use it to study other quantities related to
      your problem.

      To sum it up, the minimum number of factors with multiplicity is 10. I'm
      fairly sure the minimum number of distinct factors is 7, but I haven't proved
      it -- it's up to you if you're interested.

      Please observe that these results are not valid for small n, though; consider
      n = 7 (3 distinct factors), 11 (4 distinct factors), 13 (5 distinct factors),
      37 (6 distinct factors). Considering multiplicity, n = 7 has 8 factors and n
      = 19 has 9 factors. This happens because my assumption above (that none of
      the cofactors would be fully canceled out by the obligatory factors of
      2*2*2*3*3*5) was violated. The largest n for which the assumption is violated
      is n = 59, since

      n-2 = 57 = 3*19
      n-1 = 58 = 2*29
      n+1 = 60 = 2^2*3*5 (this is where the assumption breaks down)
      n+2 = 61 is prime.

      However, you said you were interested in n > 500.

      Décio


      [Non-text portions of this message have been removed]
    • Joseph Moore
      SHOUTING, SHOUTING+1 and SHOUTING-1. Add these together, subtract 2, and multiply by the square root of infinity to get your final result. J. ...
      Message 2 of 5 , Mar 4, 2005
        SHOUTING, SHOUTING+1 and SHOUTING-1. Add these
        together, subtract 2, and multiply by the square root
        of infinity to get your final result.

        J.


        --- rajeevbat <rajeevbat@...> wrote:
        >
        > WHAT ARE THE MINIMUM NUMBER OF FACTORS THAT THE
        > EXPRESSION
        > n^4-5*(n^2)+4
        > WILL HAVE IF N IS A SET OF PRIME NUMBERS GREATER
        > THAN 500
        >
        >
        >
        >




        __________________________________
        Celebrate Yahoo!'s 10th Birthday!
        Yahoo! Netrospective: 100 Moments of the Web
        http://birthday.yahoo.com/netrospective/
      • Michael Gian
        ... DEALS ... I ... given ... Rajeev, Finding any solution to 56a+95b+145c=x requires you to buy biscuits! You need the largest x NOT a solution. Solve the
        Message 3 of 5 , Mar 9, 2005
          --- In primenumbers@yahoogroups.com, "rajeevbat" <rajeevbat@y...>
          wrote:
          >
          > I UNDERSTOOD THE LOGIC BUT JUST CANT FINISH IT...
          > IT IS SIMILAR TO THE FROBENIUS PROBLEM ONLY THAT THIS QUESTION
          DEALS
          > WITH THREE NUMBERS
          > >
          > >
          > > VIVEK AND AISHWARYA LIMITED SELLS BISCUITS.
          > > THEY SELL BISCUITS IN PACKETS OF 56, 95 AND 145.
          > > (THAT MEANS IT IS POSSIBLE TO BUY 56+95=151 BISCUITS BUT NOT 200
          > > BISCUITS EXACTLY)
          > > I WENT TO THEIR SHOP EXPECTING AISHWARYA TO BE SELLING BISCUITS.
          I
          > > HAD PLANNED TO PURCHASE A LARGE QUANTITY OF BISCUITS SO THAT I
          > COULD
          > > IMPRESS AISHWARYA BEING A GOOD CUSTOMER.
          > > BUT WHEN I REACHED THERE I SAW VIVEK AT THE COUNTER.
          > > I COULD NOT POSSIBLY GO OUT WITHOUT BUYING ANYTHING FROM THE SHOP
          > AS
          > > IT WOULD CREATE A BAD IMPRESSION.
          > > SO I DECIDED TO ORDER THE LARGEST QUANTITY OF BISCUITS THAT VIVEK
          > > WOULD NOT BE ABLE TO PROVIDE ME WITH.
          > >
          > > AND I WOULD GO OUT WITHOUT HAVING TO BUY ANYTHING.
          > > HOW MUCH SHOULD I ORDER?
          > >
          > >
          > > (according to me-
          > > if you can find x in
          > > 56a+95b+145c= x
          > > where x is the largest possible prime number according to the
          given
          > > constraints you would have solved the question)

          Rajeev,

          Finding any solution to 56a+95b+145c=x requires you to buy biscuits!
          You need the largest x NOT a solution.
          Solve the following set of 56 Diophantine equations for the smallest
          n; n will then be the largest x:
          for i = 1->56, 56a_i+95b_i+145c_i = n+i.

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