 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Programming (https://www.mersenneforum.org/forumdisplay.php?f=29)
-   -   What can you do with 2 prime numbers? (https://www.mersenneforum.org/showthread.php?t=22213)

 VicDiesel 2017-04-20 14:08

What can you do with 2 prime numbers?

Context: I'm teaching a programming class, the students have learned to do object-oriented programming, and I think they know how to program a prime sequence object that has a "nextPrime" method that coughs up the next prime number. (Just simple testing of factors, this is not a number theory class.)

So now I want them to do an exercise that requires having 2 prime number sequences. At first I thought Goldbach, but you can actually do that with just one sequence: you have the number to be tested, a prime, and you test if the difference is a prime.

Is there a number theory question (can be trivial, can be hard) that really requires generating pairs of prime numbers?

thanks,

Victor.

 Nick 2017-04-20 14:48

One option would be for them to discover the law of quadratic reciprocity by testing several pairs of primes using their programs and seeing if they can spot the pattern from the results.

 science_man_88 2017-04-20 15:03

[QUOTE=VicDiesel;457097]Context: I'm teaching a programming class, the students have learned to do object-oriented programming, and I think they know how to program a prime sequence object that has a "nextPrime" method that coughs up the next prime number. (Just simple testing of factors, this is not a number theory class.)

So now I want them to do an exercise that requires having 2 prime number sequences. At first I thought Goldbach, but you can actually do that with just one sequence: you have the number to be tested, a prime, and you test if the difference is a prime.

Is there a number theory question (can be trivial, can be hard) that really requires generating pairs of prime numbers?

thanks,

Victor.[/QUOTE]

there's an equivalent to a subset of Goldbach's that could be tested in theory. I'm not a number theorist, I'm just annoying. Goldbach's is equivalent to every positive whole number including primes is equidistant to two not necessarily distinct primes. that comes from:

2a=p+q
a=(p+q)/2 aka their arithmetic mean is any whole number value a, the whole numbers have the subset called the prime numbers. so a subset of these say that every prime is equidistant to two other primes.

 a1call 2017-04-20 15:14

[QUOTE=VicDiesel;457097]

Is there a number theory question (can be trivial, can be hard) that really requires generating pairs of prime numbers?[/QUOTE]
How about finding twin primes and their variations?
For example finding consecutive pair of primes which are any given even number apart?
You can make it more out less challenging by setting a minimum value.

 a1call 2017-04-20 15:31

Another challenging and interesting utilization of the next-prime would be to find prime gaps of some given minimum size, or their first occurrences.

You can also try asking them to find p such that
n! + p is prime for a given n. Leave it up to them to figure out they can start by next-prime(n+1) since anything between 1 and n would give a composite.

 VBCurtis 2017-04-20 16:00

[QUOTE=a1call;457104]n! + p is prime for a given n. Leave it up to them to figure out they can start by next-prime(n+1) since anything between 1 and n would give a composite.[/QUOTE]

Are you saying n! +1 up to n!+n are all composite? I must not understand what you mean by "anything between 1 and n", because there are lots of examples where n!+1 are prime.

 bgbeuning 2017-04-20 16:01

Suggestion

If both objects start at the same value and both go up, then nextPrime() generates
the same values and they do not need two objects.

If they extend their class to have a prevPrime() method, then ask them to
"make two objects, one generating primes going up from 1, the other generating
primes down from 1,000,000 and find the largest sum of the two primes"

Primer low(1);
Primer high(1000000);

while( true ) {
int l = low.nextPrime();
int h = high.prevPrime();
if( l > h ) break; // done
int sum = l + h;
if( sum > ...
}

 science_man_88 2017-04-20 16:24

[QUOTE=VBCurtis;457107]Are you saying n! +1 up to n!+n are all composite? I must not understand what you mean by "anything between 1 and n", because there are lots of examples where n!+1 are prime.[/QUOTE]

I think they messed up on saying 1 but we can prove that n!+2 to n!+(nextprime(n+1)-1) are all composite. edit:of course this isn't necessarily the first time this gap happens the primorial also works on the same logic: 2*3*5+2 until 2*3*5+(7-1) are all composite.

 VicDiesel 2017-04-20 16:47

[QUOTE=science_man_88;457101] so a subset of these say that every prime is equidistant to two other primes.[/QUOTE]

I like this one. Easy to explain and to program, and it really requires two prime number generators. Thanks!

Victor.

 a1call 2017-04-20 17:33

[QUOTE=VBCurtis;457107]Are you saying n! +1 up to n!+n are all composite? I must not understand what you mean by "anything between 1 and n", because there are lots of examples where n!+1 are prime.[/QUOTE]
Apologies for not being clear.
What I mean is to find an integer addend ([B]excluding 1[/B], so [B]restricting[/B] the addend to [B]primes[/B] would also suffice) to a [B]n!, [/B]which sum up to a [B]prime[/B]. You could start your brute force trial from [B]next-prime(n+1).[/B] Any addend [B]m[/B] where [B]1 < m <= n[/B], to [B]n![/B], would sum up to a [B]composite[/B]. Not trying out [B]1 < m <= n[/B] would [U]not[/U] be a major time saver but could show up in a [B]measurable[/B] fractions of a second [B]faster[/B] executions.
Please let me know if there are any issues or questions.

 axn 2017-04-20 19:58

[QUOTE=VicDiesel;457097]Is there a number theory question (can be trivial, can be hard) that really requires generating pairs of prime numbers?[/QUOTE]

RSA encryption.

All times are UTC. The time now is 21:27.