mersenneforum.org What can you do with 2 prime numbers?
 Register FAQ Search Today's Posts Mark Forums Read

 2017-04-20, 14:08 #1 VicDiesel   Apr 2017 3 Posts 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.
 2017-04-20, 14:48 #2 Nick     Dec 2012 The Netherlands 1,759 Posts 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.
2017-04-20, 15:03   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by VicDiesel 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.

2017-04-20, 15:14   #4
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2×19×59 Posts

Quote:
 Originally Posted by VicDiesel 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

 2017-04-20, 15:31 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×19×59 Posts 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
2017-04-20, 16:00   #6
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

5,279 Posts

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

 2017-04-20, 16:01 #7 bgbeuning   Dec 2014 FF16 Posts 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 > ... }
2017-04-20, 16:24   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

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

2017-04-20, 16:47   #9
VicDiesel

Apr 2017

3 Posts

Quote:
 Originally Posted by science_man_88 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.

2017-04-20, 17:33   #10
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

43028 Posts

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

2017-04-20, 19:58   #11
axn

Jun 2003

2×7×383 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Housemouse Math 34 2016-04-07 16:29 Arxenar Miscellaneous Math 38 2013-06-28 23:26 Citrix Lounge 5 2010-04-05 21:34 diep Lounge 3 2009-08-05 21:01 Unregistered Miscellaneous Math 8 2008-11-09 07:45

All times are UTC. The time now is 22:30.

Sun May 22 22:30:51 UTC 2022 up 38 days, 20:32, 0 users, load averages: 2.17, 1.55, 1.38