osdir.com


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

Generating a specific list of intsgers


On Saturday, August 25, 2018 at 2:39:37 PM UTC-5, Musatov wrote:
> On Friday, August 24, 2018 at 10:59:07 PM UTC-5, Steven D'Aprano 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.
> > 
> > 
> > 
> > -- 
> > Steven D'Aprano
> > "Ever since I learned about confirmation bias, I've been seeing
> > it everywhere." -- Jon Ronson
> 
> Steven, let me know if this will suffice for the maths:
> 
> a(n) is the minimum k > 0 such that n*2^k - 3 is prime, or 0 if no such k exists
> 
> Other than multiples of 3, do there exist any numbers n > 3 such that a(n) = 0?
> 
> The answer is yes. The situation is similar to that of Riesel or Sierpinski numbers.
> 
> Every integer k is in at least one of the following residue classes:
> 
>    2 (mod 3)
> 
>    1 (mod 4)
> 
>    4 (mod 5)
> 
>    3 (mod 8)
> 
>    4 (mod 9)
> 
>    8 (mod 10)
> 
>    6 (mod 12)
> 
>   10 (mod 15)
> 
>    7 (mod 16)
> 
>   16 (mod 18)
> 
>   12 (mod 20)
> 
>   12 (mod 24)
> 
>   16 (mod 25)
> 
>    1 (mod 25)
> 
>    0 (mod 30)
> 
>   10 (mod 36)
> 
>   27 (mod 36)
> 
>   16 (mod 40)
> 
>    1 (mod 45)
> 
>   33 (mod 45)
> 
>   15 (mod 48)
> 
>   31 (mod 48)
> 
> where 3,4,5,...,48 are the multiplicative orders of 2 modulo the primes 7, 5, 31, 17, 73, 11, 13, 151, 257, 19, 41, 241, 1801, 601, 331, 109, 37, 61681, 23311, 631, 673, 97 respectively.
> 
> Now 7 | n*2^k-3 for k ==  2 (mod 3)  if n ==  6 (mod 7),
> 
>     5 | n*2^k-3 for k ==  1 (mod 4)  if n ==  4 (mod 5), ...,
> 
>    97 | n*2^k-3 for k == 31 (mod 48) if n == 75 (mod 97).
> 
> Using the Chinese remainder theorem, we get infinitely many n for which all these congruences hold, and thus for which n*2^k-3 is always divisible by at least one of those 22 primes.
> 
> One such n is 72726958979572419805016319140106929109473069209 (which is not divisible by 3).

In the interest of full disclosure, I only asked the question and received the answer.