# Need Help proving these equations

1. Apr 12, 2005

### heavyc

Need Help proving these equations!!!!!!!!

I am in Discrete Math and i need alot of help solving these equations and then proving them using a C++ program. If anyone could help I would really appreciate it. Please i need any sugggestions on this because i really cant seem to figure out how to do this and i cant even ask my teacher because he said that he isnt going to help us in any way.

For all integers n, 1 <= n <= 100, such that n^2 - 79n + 1601 is prime.
for a program what i got was

for( k = 1; k < 101; k++)
{
test = k^2 - (79 * k) + 1601;
for( i = 2; i < (test / 2 + 1); i++)
{
for( j = 2; j < (test / 2 + 1); j++)
{
product = i * j;
cout << i << " * " << j << " = " << product <<endl;
if(product == test)
cout << "success" << endl;
else
cout << "fail" << endl;
}
}
}

2. There exist positive integers u, v, x, y, z, 1 <= u <= v <= x <= y <= z <= 200, such that u^5 + v^5+ x^5 + y^5 = z^5. and same thing with the C++ program but i couldnt figure this one out.

2. Apr 12, 2005

### ramollari

I don't know how to prove your math relation, but you should know that the piece of code has some flaws. It will mostly print fail on the screen and occasionally it will print success and nothing more. You could write it more neatly like this:

Code (Text):

for ( int k = 1; k <= 100; k++ )
{
bool ok = true;
int test = k * k - 79 * k + 1601;
for ( int i = 2; i <= test / 2; i++ )
{
for ( int j = 2; j <= test / 2; j++ )
{
if ( i * j == test )
{
ok = false;
break;
}
}

if ( ok )
cout << test << " was prime\n";
else
cout << test << " was not prime\n";
}

Regarding the second part, writing the program is easy. Make a five times nested for loop.

Last edited: Apr 12, 2005
3. Apr 12, 2005

### heavyc

thank you very much

i was wondering if u knew anything about discrete math because for that second problem what numbers would you start with because i dont know if i should let u = 1 v = 2 x = 3 y = 4 and z = 5 and then start the loop with those numbers and then try it that way??

4. Apr 12, 2005

### Gokul43201

Staff Emeritus
First set u,v,x,y all to 1. Then run nested loops to generate all 10^8 combinations. Evaluate each result, take the fifth root and check if that is an integer.

5. Apr 13, 2005

### CRGreathouse

Here's a naive method for calculating this problem. :rofl: Braces are for losers.

for (int u = 1; u <= 200; u++)
for (int v = u; v <= 200; v++)
for (int x = v; x <= 200; x++)
for (int y = x; y <= 200; y++)
for (int z = y; z <= 200; z++)
if (Math.pow(u, 5) + Math.pow(v, 5) + Math.pow(x, 5) + Math.pow(y, 5) == Math.pow(z, 5))
cout << u << " " << v << " " << x << " " << y << " " << z << endl;

6. Apr 13, 2005

### learningphysics

How do you get 10^8?

7. Apr 13, 2005

### ramollari

200^5 = 3.2 * 10^8.
It takes fewer iterations than that, because some numbers have a smaller range, so ~10^8. In a normal CPU it would take a few seconds or even minutes. BTW I like very much the code suggested by CRGreathouse.

8. Apr 13, 2005

### learningphysics

200^5=32*10^10=3.2*10^11

9. Apr 13, 2005

### ramollari

Oops sorry, my mistake. Then it must be much more than 10^8.

10. Apr 13, 2005

### learningphysics

I think the total is less than 10^8 once you use the condition that u<=v<=x<=y<=z

11. Apr 13, 2005

### CRGreathouse

Sure, that well may be.

$$T=\sum^n\sum^n\sum^n\sum^n\sum^n1$$

$$=\sum^n\sum^n\sum^n\sum^nk$$

$$=\sum^n\sum^n\sum^n\left(\frac12k^2+\frac12k\right)$$

$$=\sum^n\sum^n \left(\frac{1}{12}(2k^3+3k^2+k)+\frac14(k^2+k)\right) =\frac{1}{12}\sum^n\sum^n \left(2k^3+6k^2\right)$$

$$=\frac{1}{24}\sum^n \left(k^4+2k^3+k^2 +4k^3+6k^2+2k+4k^2+4k\right) =\frac{1}{24}\sum^n \left(k^4+6k^3+7k^2+6k+4k\right)$$

$$=\frac{1}{720} \left(6k^5+15k^4+10k^3-k +45(k^4+2k^3+k^2) +35(2k^3+3k^2+k) +90k^2+90k\right) =\frac{1}{720} \left(6k^5+15k^4+10k^3-k +45k^4+90k^3+45k^2 +70k^3+105k^2+35k +90k^2+90k\right)$$

$$=\frac{1}{720} \left(6k^5+60k^4+170k^3+240k^2+124k\right) =\frac{1}{360} \left(3k^5+30k^4+85k^3+120k^2+62k\right)$$

In the unlikely case that I haven't made a mistake or been confused by my own (admittedly loose) notation, you should get the answer by substituting 200 for k. This method is valid, I'm sure; it's just that it's so easy to make a transposition error with so many terms.

Last edited: Apr 13, 2005
12. Apr 14, 2005

### ramollari

I tested the code in my ~2GHz processor and it took me around 15min. But it finally did give one answer: 27, 84, 110, 133, 144.

13. Apr 14, 2005

### CRGreathouse

I rewrote the code to optimize it a bit. (The original code was posted mostly for amusement; it's so slow....) On my older computer, it finished (finding only the one solution) in 42s.

long long pow5(int num);

int main() {
const int limit = 145;
const long long limit5 = pow5(limit);
long long sumU, sumV, sumX, sumY, x5;
int u, v, x, y, z;
for (u = 1; u <= limit; u++) {
sumU = pow5(u);
for (v = u; v <= limit; v++) {
sumV = sumU + pow5(v);
for (x = v; x <= limit; x++) {
x5 = pow5(x);
sumX = sumV + x5;
if (sumX + x5 > limit5)
break; // Impossible for z to manage, sumY will be too big
for (y = x; y <= 200; y++) {
sumY = sumX + pow5(y);
z = (int)pow((double)sumY, .2);
if (sumY == pow5(z))
cout << u << " " << v << " " << x << " " << y << " --> " << z << endl;
} // end y loop
} // end x loop
} // end v loop
} // end u loop
}

long long pow5(int num) {
//return pow((double)num, 5);
long long n = num;
return n * n * n * n * n;
}