Generating a specific list of intsgers

[Richard Damon]

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