osdir.com


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

Generating a specific list of intsgers


On Sat, 25 Aug 2018 at 20:27, Musatov <tomusatov at gmail.com> wrote:
>
> 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 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.
> > >
> > > 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)

Fair enough. So finding a(n) when a(n)!=0 is straight-forward (simply
loop through testing k=1,2...) but the issue is determining for any
given n whether a(n)=0 i.e. that there does not exist k such that
n*2^k-3 is prime.

Perhaps if you explain how you know that
   a(72726958979572419805016319140106929109473069209) = 0
then that would suggest a way to code it.

--
Oscar