Is there a more efficient way of solving this math problem?

[BamBam215]

Find all primes p for which 5p+1 is a perfect square. Prove your answer to be correct.

There has to be a better way than the obvious grunt work.

 

[notfred]

use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

 

[kranky]

Originally posted by: BamBam215
There has to be a better way than the obvious grunt work.

Maybe you could ask on a message board somewhere? 😉

 

[BamBam215]

Originally posted by: Tyler
use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

not a programming class 🙂

 

[notfred]

Originally posted by: BamBam215

Originally posted by: Tyler
use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

not a programming class 🙂

So?

 

[BamBam215]

Originally posted by: Tyler

Originally posted by: BamBam215

Originally posted by: Tyler
use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

not a programming class 🙂

So?

so even though u've proven you're very l33t in programming, that doesn't help me with the problem.

 

[notfred]

Originally posted by: BamBam215

Originally posted by: Tyler

Originally posted by: BamBam215

Originally posted by: Tyler
use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

not a programming class 🙂

So?

so even though u've proven you're very l33t in programming, that doesn't help me with the problem.

Um, do you know what that does? It takes a list of prime numbers and tells you which ones, when muliplied by 5 and incremented by 1, are perfect squares. That doesn't help with your problem?

 

[Paul Ma]

 

[BamBam215]

Originally posted by: Tyler

Originally posted by: BamBam215

Originally posted by: Tyler

Originally posted by: BamBam215

Originally posted by: Tyler
use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

not a programming class 🙂

So?

so even though u've proven you're very l33t in programming, that doesn't help me with the problem.

Um, do you know what that does? It takes a list of prime numbers and tells you which ones, when muliplied by 5 and incremented by 1, are perfect squares. That doesn't help with your problem?

well yeah because i obviously cannot write down all the primes which would give me a perfect square when i plug it into 5p+1. there has to be a general equation or something that would give me such a prime without testing every single one. get my drift? thanks for the help though.

 

[LuNoTiCK]

Originally posted by: Tyler

Originally posted by: BamBam215

Originally posted by: Tyler

Originally posted by: BamBam215

Originally posted by: Tyler
use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

not a programming class 🙂

So?

so even though u've proven you're very l33t in programming, that doesn't help me with the problem.

Um, do you know what that does? It takes a list of prime numbers and tells you which ones, when muliplied by 5 and incremented by 1, are perfect squares. That doesn't help with your problem?

You've said a good way, but he probably need it for school.

 

[her209]

x^2 = 5p + 1

does that help? 😛

(x^2 - 1) / 5 = p

(x+1)(x-1) / 5 = p

 

[Ameesh]

Originally posted by: her209
x^2 = 5p + 1

does that help? 😛

(x^2 - 1) / 5 = p

(x+1)(x-1) / 5 = p

😕 i dont think thats any better then the original form.

 

[OrganizedChaos]

Originally posted by: Tyler
use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

glad i'm not a programmer, i don't understand how you people can stand to look at that jibberish

 

[dighn]

only 3 or 7 i'll type up the proof now

 

[her209]

Originally posted by: OrganizedChaos

Originally posted by: Tyler
use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

glad i'm not a programmer, i don't understand how you people can stand to look at that jibberish

It says, given an array of primes, go through each one and multiply each one by 5 and add 1 to it. Then take the square root. If the answer is a whole number, then 5p+1 is a perfect square. :beer:

 

[notfred]

nevermind

 

[dighn]

ok 5P+1 is a perfect square
lets see
5P + 1 = n^2, n = 1,2,3,4,5...
now all prime numbersw are whole numbers, so P must be whole
P = (n^2-1)/5
for it to be whole, n^2-1 must be divisible by 5 that is end in 0 or 5
n^2 end in 1 or 6
now expand n into the form a*10 + b, where a = 0,1,2,3..9 b = 0,12,3,..9 etc
n^2 = 100a^2 + 20ab + b^2 <-- note that first two terms contribut enothing to
the oneth place, only b^2 does, so b^2 must end in 1
b must be 1,4,6,9

so now
P = (n^2-1)/5 = ((10a+b)^2-1)/5 = (10a+b+1)(10a+b-1)/5
b is 1, 4,6,9
P = (10a+2)(10a)/5 = 2a(10a+2) for b = 1 --> this cant be prime
P = (10a+5)(10a+3)/5 = (2a+1)(10a+3) for b =4 -->a must be 0 for it to be prime, P = 3
P = (10a+7)(10a+5)/5 = (10a+7)(2a+1) for b = 6 --> a must be 0 for prime, P = 7
P = (10a+10)(10a+8) for b = 9 ---> cannot be prime

only answers are 3 and 7


on second thought it could be easier

(n+1)(n-1)/5=P

for P to be prime, one of n+1 or n-1 must be 5 so that you have a number * 1, n is either 4, or 6, and p is 3 or 7

 

[her209]

Originally posted by: her209
x^2 = 5p + 1

does that help? 😛

(x^2 - 1) / 5 = p

Basically, any perfect square that ends with a 1 or 6 satisfies that equation.

(x+1)(x-1) / 5 = p

I.e., at least one of the terms, (x+1) or (x-1), is a multiple of 5 and not 0.

 

[Ameesh]

Originally posted by: OrganizedChaos

Originally posted by: Tyler
use Math::Complex;
foreach $p(@list_of_primes){
$q = 5 * $p;
$q++;
$q = sqrt($q);
if(int($q) == $q){
print "$p is print and 5($p)+1 is a perfect square\n";
}
}
}

glad i'm not a programmer, i don't understand how you people can stand to look at that jibberish

perl is syntactical garbage, not all programming languages are like that

 

[lukatmyshu]

Originally posted by: Tyler
use Math::Complex; foreach $p(@list_of_primes){ $q = 5 * $p; $q++; $q = sqrt($q); if(int($q) == $q){ print "$p is print and 5($p)+1 is a perfect square\n"; } } }

Plus the idea is that we don't really know all the primes ... perhap the answer is 3,7 and 2^1234342-1 ... your program doesn't prove 3 and 7 are the only values ... btw ... I think you can look at the fact that 5*n always has trailing digits 0 or 5 ... which means that n^2 has trailing digit 1 or 6 .... but I can't think about this right now.

 

[RaynorWolfcastle]

I'd bet you can eliminate a ton of numbers by checking the amount of numbers for which 5p+1 are perfect squares.

Consider that for
5p + 1 = x^2

we have that x < p for any p larger than 5 (by inspection)

Now you've just eliminated the possibility that x > p for all numbers larger than 5

To brute force this in a slightly more efficient manner, now you just have take all the integers <= p and compute their squares. That'll get rid of A LOT of numbers.

I'm sure this can be used as a basis to formally prove which numbers are valid but I'm too lazy to do it myself... After all it's your homework 😉

 

[RaynorWolfcastle]

Originally posted by: dighn
ok 5P+1 is a perfect square
lets see
5P + 1 = n^2, n = 1,2,3,4,5...
now all prime numbersw are whole numbers, so P must be whole
P = (n^2-1)/5
for it to be whole, n^2-1 must be divisible by 5 that is end in 0 or 5
n^2 end in 1 or 6
now expand n into the form a*10 + b, where a = 0,1,2,3..9 b = 0,12,3,..9 etc
n^2 = 100a^2 + 20ab + b^2 <-- note that first two terms contribut enothing to
the oneth place, only b^2 does, so b^2 must end in 1
b must be 1,4,6,9

so now
P = (n^2-1)/5 = ((10a+b)^2-1)/5 = (10a+b+1)(10a+b-1)/5
b is 1, 4,6,9
P = (10a+2)(10a)/5 = 2a(10a+2) for b = 1 --> this cant be prime
P = (10a+5)(10a+3)/5 = (2a+1)(10a+3) for b =4 -->a must be 0 for it to be prime, P = 3
P = (10a+7)(10a+5)/5 = (10a+7)(2a+1) for b = 6 --> a must be 0 for prime, P = 7
P = (10a+10)(10a+8) for b = 9 ---> cannot be prime

only answers are 3 and 7

I nice proof, except I'm not too sure these steps are right

P = (10a+5)(10a+3)/5 = (2a+1)(10a+3) for b =4 -->a must be 0 for it to be prime, P = 3
P = (10a+7)(10a+5)/5 = (10a+7)(2a+1) for b = 6 --> a must be 0 for prime, P = 7

if you multiply out the case b = 4, you get 20a^2 + 16a + 3 = P.
and for b = 6, you get 20a^2 + 24a + 7 = P.
Please explain how you can state that all a's except 0 are not prime, maybe I'm missing something obvious.


The other 2 cases are obvious since we have
(even*(even or odd) + even)*(even*(even or odd) + even) = (even + even)*(even + even) = even ... divisible by two.

Can you clarify?

 

[dighn]

Originally posted by: RaynorWolfcastle


I nice proof, except I'm not too sure these steps are right

P = (10a+5)(10a+3)/5 = (2a+1)(10a+3) for b =4 -->a must be 0 for it to be prime, P = 3
P = (10a+7)(10a+5)/5 = (10a+7)(2a+1) for b = 6 --> a must be 0 for prime, P = 7

if you multiply out the case b = 4, you get 20a^2 + 16a + 3 = P.
and for b = 6, you get 20a^2 + 24a + 7 = P.
Please explain how you can state that all a's except 0 are not prime, maybe I'm missing something obvious.

for b = 4, P = (2a+1)(10a+3)
u have 2 whole numbers multipleid together, that's not gonna be a prime unless one of the is a 1, 10a+3 cannot be 1, 2a+1 can only be 1 if a is = 0, same with for b = 6

 

[RaynorWolfcastle]

for b = 4, P = (2a+1)(10a+3)
u have 2 whole numbers multipleid together, that's not gonna be a prime unless one of the is a 1, 10a+3 cannot be 1, 2a+1 can only be 1 if a is = 0, same with for b = 6

I knew I was missing something obvious 😱