[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

On Saturday, August 25, 2018 at 9:46:21 AM UTC-5, Richard Damon wrote: > On 8/25/18 10:27 AM, Dennis Lee Bieber wrote: > > On Sat, 25 Aug 2018 03:56:28 +0000 (UTC), Steven D'Aprano > > <steve+comp.lang.python at pearwood.info> declaimed the following: > > > >> On Fri, 24 Aug 2018 14:40:00 -0700, tomusatov wrote: > >> > >>> I am looking for a program able to output a set of integers meeting the > >>> following requirement: > >>> > >>> a(n) is the minimum k > 0 such that n*2^k - 3 is prime, or 0 if no such > >>> k exists > >>> > >>> Could anyone get me started? (I am an amateur) > >> > >> That's more a maths question than a programming question. Find out how to > >> tackle it mathematically, and then we can code it. > > I'd want more punctuation in that just to ensure I'm interpreting it > > properly -- I'm presuming it is meant to be parsed as: > > (n * (2 ^ k)) - 3 > > > > Suspect this needs to be attacked in the reverse direction -- generate > > a list of primes, add 3, determine if it is a multiple of powers of two. > > Though in that case, k = 1 would fit all since if it is a multiple 2^2 (4) > > it would also be a multiple of 2^1 (2), for all greater powers of 2.. > > > > prime 5 > > + 3 => 8 > > log_2 8 => 3 <<< integral k > > 8 => 1 * (2 ^ 3) > > 2 * (2 ^ 2) > > 4 * (2 ^ 1) > > > > n=4, k=1 > > > > OTOH, if it is supposed to be (n*2) ^ k, or even worse (n*2) ^ (k-3) > > the solution becomes more difficult. > > > > > I think the issue is given n, find k. > > a(1): 1*2-3=-1 no, 1*4-3=1 no, 1*8-3 - 5 YES, a(1) = 3 > > a(2) 2*2-3 = 1, no 2*4-3=5 YES a(2) = 2 > > a(3) 3*2-3 - 3 YES, a(3) = 1 > > and so on. > > One path to solution is to just count up the k values and test each > result for being prime, except that will never return 0 to say no such k > exists. That will require some higher level of math to detect (or an > arbitrary cap on k, and we say we can say 0 if the only k is too big, > but with big nums, that would be VERY large and take a very long time. > > -- > Richard Damon Here is a sample output: 3, 2, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 2, 0, 1, 1, 0, 2, 1, 0, 1, 1, 0, 1, 2, 0, 1, 2, 0, 1, 1, 0, 3, 1, 0, 1, 1, 0, 2, 1, 0, 1, 2, 0, 1, 1, 0, 2, 1, 0, 1, 1, 0, 1, 1, 0, 1, 2, 0, 2, 1, 0, 3, 1, 0, 1, 2, 0, 1, 1, 0, 5, 2, 0, 1, 1, 0, 2, 1, 0, 3, 1, 0, 1

- Prev by Date:
**Generating a specific list of intsgers** - Next by Date:
**Generating a specific list of integers** - Previous by thread:
**Generating a specific list of intsgers** - Next by thread:
**Generating a specific list of intsgers** - Index(es):