# Generating a specific list of intsgers

```On Saturday, August 25, 2018 at 2:18:09 PM UTC-5, Musatov wrote:
> On Saturday, August 25, 2018 at 1:52:17 PM UTC-5, Oscar Benjamin wrote:
> > On Sat, 25 Aug 2018 at 18:12, <tomusatov at gmail.com> wrote:
> > >
> > > 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
> >
> > Looks like it's zero for any multiple of 3 (apart from 3 itself). This
> > makes sense since if n is a equal to b*3 for some integer b then
> >     n*2^k - 3 = b*3*2^k - 3 = (b*2^k - 1)*3
> > which can only be prime if
> >     b*2^k - 1 = 1
> > which can only be true if b=1 (since k>0) implying that n=3. So for
> > any *other* multiple of 3 you must necessarily have a(n) = 0.
> >
> > The above means that you can handle all multiples of 3 but how do you
> > know that you won't hit an infinite loop when n is not a multiple of
> > 3?
>
>

Rather, I should say one such n is 72726958979572419805016319140106929109473069209 (which is not divisible by 3)
> For that you need the converse of the above:
> >     whenever n is not a multiple of 3 then a(n) != 0
> > I haven't put much thought into it but that might be easy to prove.
> >
> > --
> > Oscar

```