- 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

>

> 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

> IMPRESS AISHWARYA BEING A GOOD CUSTOMER.

AS

> BUT WHEN I REACHED THERE I SAW VIVEK AT THE COUNTER.

> I COULD NOT POSSIBLY GO OUT WITHOUT BUYING ANYTHING FROM THE SHOP

> 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) - On Friday 04 March 2005 12:28, you wrote:
> WHAT ARE THE MINIMUM NUMBER OF FACTORS THAT THE EXPRESSION

It helps if you factor n^4 - 5n^2 + 4 as (n-2)(n-1)(n+1)(n+2). Right off the

> n^4-5*(n^2)+4

> WILL HAVE IF N IS A SET OF PRIME NUMBERS GREATER THAN 500

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] - 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/ - --- In primenumbers@yahoogroups.com, "rajeevbat" <rajeevbat@y...>

wrote:>

DEALS

> I UNDERSTOOD THE LOGIC BUT JUST CANT FINISH IT...

> IT IS SIMILAR TO THE FROBENIUS PROBLEM ONLY THAT THIS QUESTION

> WITH THREE NUMBERS

I

> >

> >

> > 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.

> > HAD PLANNED TO PURCHASE A LARGE QUANTITY OF BISCUITS SO THAT I

given

> 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

> > 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