Re: [PrimeNumbers] QUESTION
- On Friday 04 March 2005 12:28, you wrote:
> WHAT ARE THE MINIMUM NUMBER OF FACTORS THAT THE EXPRESSIONIt helps if you factor n^4 - 5n^2 + 4 as (n-2)(n-1)(n+1)(n+2). Right off the
> 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,
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
f = factorint(eval(n^4 - 5*n^2 + 4)/(2^3*3^2*5));
if(k==4,print(n" "f" "k));
With some modifications, you can use it to study other quantities related to
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.
[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.
--- rajeevbat <rajeevbat@...> wrote:
> WHAT ARE THE MINIMUM NUMBER OF FACTORS THAT THE
> 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
- --- In firstname.lastname@example.org, "rajeevbat" <rajeevbat@y...>
> I UNDERSTOOD THE LOGIC BUT JUST CANT FINISH IT...
> IT IS SIMILAR TO THE FROBENIUS PROBLEM ONLY THAT THIS QUESTION
> WITH THREE NUMBERSI
> > 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 Igiven
> > 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
> > 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.