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

QUESTION

Expand Messages
  • rajeevbat
    I UNDERSTOOD THE LOGIC BUT JUST CANT FINISH IT... IT IS SIMILAR TO THE FROBENIUS PROBLEM ONLY THAT THIS QUESTION DEALS WITH THREE NUMBERS ... COULD ... AS
    Message 1 of 5 , Mar 4 7:22 AM
    • 0 Attachment
      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)
    • rajeevbat
      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
      Message 2 of 5 , Mar 4 7:28 AM
      • 0 Attachment
        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
      • 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 3 of 5 , Mar 4 8:28 AM
        • 0 Attachment
          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 4 of 5 , Mar 4 11:31 AM
          • 0 Attachment
            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 5 of 5 , Mar 9 5:21 AM
            • 0 Attachment
              --- 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.