Need Help proving these equations

[heavyc]

Need Help proving these equations!

I am in Discrete Math and i need a lot 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 can't seem to figure out how to do this and i can't even ask my teacher because he said that he isn't 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;
count << i << " * " << j << " = " << product <<endl;
if(product == test)
count << "success" << endl;
else
count << "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 couldn't figure this one out.

 

[ramollari]

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

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:

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.

 

[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 don't 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??

 

[Gokul43201]

i was wondering if u knew anything about discrete math because for that second problem what numbers would you start with because i don't 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??

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.

 

[CRGreathouse]

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 couldn't figure this one out.

Here's a naive method for calculating this problem. 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))
count << u << " " << v << " " << x << " " << y << " " << z << endl;

 

[learningphysics]

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.

How do you get 10^8?

 

[ramollari]

How do you get 10^8?

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.

 

[learningphysics]

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.

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

 

[ramollari]

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

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

 

[learningphysics]

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

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

 

[CRGreathouse]

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

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.

 

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

 

[CRGreathouse]

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.

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))
count << 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;
}