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

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.

- Prev by Date:
**Generating a specific list of intsgers** - Next by Date:
**regex pattern to extract repeating groups** - Previous by thread:
**Generating a specific list of intsgers** - Next by thread:
**Generating a specific list of intsgers** - Index(es):