mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2017-04-20, 14:08   #1
VicDiesel
 
Apr 2017

3 Posts
Default 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.
VicDiesel is offline   Reply With Quote
Old 2017-04-20, 14:48   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

23×11×17 Posts
Default

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.
Nick is online now   Reply With Quote
Old 2017-04-20, 15:03   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Quote:
Originally Posted by VicDiesel View Post
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.
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.
science_man_88 is offline   Reply With Quote
Old 2017-04-20, 15:14   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7·277 Posts
Default

Quote:
Originally Posted by VicDiesel View Post

Is there a number theory question (can be trivial, can be hard) that really requires generating pairs of prime numbers?
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.

Last fiddled with by a1call on 2017-04-20 at 15:17
a1call is offline   Reply With Quote
Old 2017-04-20, 15:31   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7·277 Posts
Default

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.

Last fiddled with by a1call on 2017-04-20 at 15:51
a1call is offline   Reply With Quote
Old 2017-04-20, 16:00   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

41×109 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
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.

Last fiddled with by VBCurtis on 2017-04-20 at 16:02
VBCurtis is offline   Reply With Quote
Old 2017-04-20, 16:01   #7
bgbeuning
 
Dec 2014

25210 Posts
Default 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.

How about this? It is a mathematically nonsense problem but a programming problem.

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 > ...
}
bgbeuning is offline   Reply With Quote
Old 2017-04-20, 16:24   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
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.

Last fiddled with by science_man_88 on 2017-04-20 at 16:29
science_man_88 is offline   Reply With Quote
Old 2017-04-20, 16:47   #9
VicDiesel
 
Apr 2017

3 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
so a subset of these say that every prime is equidistant to two other primes.
I like this one. Easy to explain and to program, and it really requires two prime number generators. Thanks!

Victor.
VicDiesel is offline   Reply With Quote
Old 2017-04-20, 17:33   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7·277 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
Apologies for not being clear.
What I mean is to find an integer addend (excluding 1, so restricting the addend to primes would also suffice) to a n!, which sum up to a prime. You could start your brute force trial from next-prime(n+1). Any addend m where 1 < m <= n, to n!, would sum up to a composite. Not trying out 1 < m <= n would not be a major time saver but could show up in a measurable fractions of a second faster executions.
Please let me know if there are any issues or questions.

Last fiddled with by a1call on 2017-04-20 at 18:25
a1call is offline   Reply With Quote
Old 2017-04-20, 19:58   #11
axn
 
axn's Avatar
 
Jun 2003

17×281 Posts
Default

Quote:
Originally Posted by VicDiesel View Post
Is there a number theory question (can be trivial, can be hard) that really requires generating pairs of prime numbers?
RSA encryption.
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Right Perfect Prime Numbers Housemouse Math 34 2016-04-07 16:29
Prime Numbers Or Not Arxenar Miscellaneous Math 38 2013-06-28 23:26
All odd numbers are prime Citrix Lounge 5 2010-04-05 21:34
Old Gem Interview about prime numbers diep Lounge 3 2009-08-05 21:01
Prime numbers Unregistered Miscellaneous Math 8 2008-11-09 07:45

All times are UTC. The time now is 12:01.

Wed Nov 25 12:01:15 UTC 2020 up 76 days, 9:12, 4 users, load averages: 1.84, 1.68, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.