A078680 -id:A078680 - cp's OEIS frontend

A050412 Riesel problem: start with n; repeatedly double and add 1 until reaching a prime. Sequence gives number of steps to reach a prime or 0 if no prime is ever reached.

1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 4, 1, 1, 2, 2, 1, 2, 1, 1, 4, 1, 3, 2, 1, 3, 4, 1, 1, 2, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 7, 24, 1, 3, 4, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 12, 2, 3, 4, 2, 1, 4, 1, 5, 2, 1, 1, 2, 4, 7, 2552, 1, 1, 2, 2, 1, 4, 3, 1, 2, 1, 5, 6, 1, 23, 4, 1, 1, 2, 3, 3, 2, 1, 1, 4, 1, 1

Offset: 1

Robert G. Wilson v, Dec 22 1999

a(n) is the smallest m >= 1 such that (n+1)*2^m - 1 is prime (or 0 if no such prime exists).
It is conjectured that n = 509203 is the smallest Riesel number, i.e., n*2^k - 1 is composite for every k>0. - Robert G. Wilson v, Mar 01 2015. [This would imply that a(509203) is the first zero term in this sequence. - N. J. A. Sloane, Jul 31 2024]
Comment from N. J. A. Sloane, Aug 01 2024 (Start)
Both the Ballinger-Keller and Prime Wiki links assert that 104917*2^340181-1 is prime, but leave open the possibility that there is an m < 340181 which makes 104917*2^m - 1 a prime.
This question was finally settled by Lucas A. Brown on Jul 31 2024, who showed that m = 340181 is the smallest value that gives a prime. This implies that a(104917) = 340181.
Brown used a Python program (see below), with BPSW for the primality testing and gmpy2 to handle the arithmetic. The program was started on Jul 30 2024 and finished on Jul 31 2024.
He reports that it took about 15 hours in wall-clock time, and used 24 threads running in parallel.  (End)

			For n=4; the smallest m>=1 such that (4+1)*2^m-1 is prime is m=2: 5*2^2-1=19 (prime). - _Jaroslav Krizek_, Feb 13 2011

Robert G. Wilson v, Table of n, a(n) for n = 1..2291 (first 657 terms from T. D. Noe)
Ray Ballinger and Wilfrid Keller, The Riesel Problem: Definition and Status, Proth Search Page.
Hans Riesel, Some large prime numbers. Translated from the Swedish original (Några stora primtal, Elementa 39 (1956), pp. 258-260) by Lars Blomberg.
N. J. A. Sloane, A Nasty Surprise in a Sequence and Other OEIS Stories, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; Slides [Mentions this sequence]
Prime Wiki, Riesel primes of the form 104917•2^n-1

Main sequences for Riesel problem: A038699, A040081, A046069, A050412, A052333, A076337, A101036, A108129.

Cf. A051914, A052333 (primes reached), A052334, A052339, A052340, A050413, A078680, A101036.

A050412 := proc(n)
    local twox1,k ;
    twox1 := 2*n+1 ;
    k := 1;
    while not isprime(twox1) do
        twox1 := 2*twox1+1 ;
        k := k+1 ;
    end do:
    return k;
end proc: # R. J. Mathar, Jul 23 2015

a[n_] := Block[{s=n, c=1}, While[ ! PrimeQ[2*s+1], s = 2*s+1; c++]; c]; Table[ a[n], {n, 1, 99} ] (* Jean-François Alcover, Feb 06 2012, after Pari *)
a[n_] := Block[{k = 1}, While[ !PrimeQ[2^k (n + 1) - 1], k++];k]; Array[a, 100] (* Robert G. Wilson v, Feb 14 2015 *) (* Corrected by Paolo Xausa, Jul 30 2024 *)

a(n)=if(n<0,0,s=n; c=1; while(isprime(2*s+1)==0,s=2*s+1; c++); c)
(Python, designed specifically for n = 104917)
#! /usr/bin/env python3
from labmath import primegen, isprime, mpz, count
from multiprocessing import Pool
primes = list(primegen(1000000))
def test(n):
    for p in primes:
        if (104917 * pow(2, n, p)) % p == 1:
            return (n, False)
    return (n, isprime(104917 * mpz(2)**n - 1, tb=[]))
with Pool(24) as P:
    for (n, result) in P.imap(test, count()):
        print('\b'*80, n, end='', flush=True)
        if result:
            break # Lucas A. Brown, Aug 01 2024

If a(n) = k with k>1, then a(2n+1) = k-1. - Robert G. Wilson v, Mar 01 2015

If a(n) = 0, then a(2n+1) is also 0. Conjecture: If a(n) = 1, then a(2n+1) is not 0. - Jeppe Stig Nielsen, Feb 12 2023

More terms from Christian G. Bower, Dec 23 1999

Second definition corrected by Jaroslav Krizek, Feb 13 2011

A318291 a(n) is the minimum k > 0 such that n*2^k - 3 is prime, or 0 if no such k exists.

Original entry on oeis.org

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, 3, 0, 2, 1, 0, 1, 1, 0, 1, 1, 0, 1, 2, 0, 2, 7, 0, 3, 1, 0, 1, 2, 0, 1, 1, 0, 5, 2, 0, 1, 1, 0, 2, 1, 0, 3, 1, 0, 1, 4, 0

Offset: 1

Martin Michael Musatov, Aug 23 2018

nonn

Question: Other than multiples of 3, do there exist any numbers n > 3 such that a(n) = 0?
From Robert Israel, Aug 24 2018: (Start)
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:
(mod 3)
(mod 4)
(mod 5)
(mod 8)
(mod 9)
(mod 10)
(mod 12)
(mod 15)
(mod 16)
(mod 18)
(mod 20)
(mod 24)
(mod 25)
(mod 25)
(mod 30)
(mod 36)
(mod 36)
(mod 40)
(mod 45)
(mod 45)
(mod 48)
(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),
| n*2^k-3 for k ==  1 (mod 4)  if n ==  4 (mod 5), ...,
| 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). (End)
For the record high values in this sequence, see A316493; for the indices at which those values occur, see A318561. - Jon E. Schoenfield, Aug 26 2018
Conjecture: For every odd prime p, there exist infinitely many numbers j that are non-multiples of p and have the property that j*2^k - p is composite for every k > 0. - Martin Michael Musatov, Sep 04 2018

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000040, A050412, A078680.

f:= proc(n) local k;
  if n mod 3 = 0 then return 0 fi;
  for k from 1 do if isprime(n*2^k-3) then return k fi od
end proc:
f(3):= 1:
map(f, [$1..100]); # Robert Israel, Sep 03 2018

Array[If[And[Mod[#, 3] == 0, # > 3], 0, Block[{k = 1}, While[! PrimeQ[# 2^k - 3], k++]; k]] &, 105] (* Michael De Vlieger, Sep 04 2018 *)

a(n)={my(k=0); if(n%3||n==3, k++; while(!isprime((n<Andrew Howroyd, Aug 24 2018

a(3) corrected and a(19)-a(87) from Andrew Howroyd, Aug 25 2018

a(47), a(62), and a(86) corrected by Jon E. Schoenfield, Aug 29 2018

A078683 Least prime of the form n*2^m+1 for m>0, or 0 if there is no such prime.

Original entry on oeis.org

3, 5, 7, 17, 11, 13, 29, 17, 19, 41, 23, 97, 53, 29, 31, 257, 137, 37, 1217, 41, 43, 89, 47, 97, 101, 53, 109, 113, 59, 61, 7937, 257, 67, 137, 71, 73, 149, 1217, 79, 641, 83, 337, 173, 89, 181, 11777

Offset: 1

Benoit Cloitre, Dec 17 2002

nonn

The next prime has 178 digits. See A078680 for the values of m.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
N. J. A. Sloane, A Nasty Surprise in a Sequence and Other OEIS Stories, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; Slides [Mentions this sequence]

Cf. A078680.

Table[m=1; While[! PrimeQ[p = n*2^m + 1], m++]; p, {n, 50}]

a(n)=if(n<0, 0, m=1; while(isprime(n*2^m+1)==0, m++); n*2^m+1)

Edited by T. D. Noe, Feb 25 2011

A250204 Sierpiński problem in base 6: Least k > 0 such that n*6^k+1 is prime, or 0 if no such k exists.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 4, 0, 1, 1, 1, 1, 0, 2, 1, 1, 1, 0, 5, 1, 4, 1, 0, 1, 1, 1, 2, 0, 1, 2, 1, 1, 0, 1, 2, 1, 1, 0, 1, 5, 5, 2, 0, 1, 1, 1, 3, 0, 2, 1, 1, 7, 0, 1, 1, 2, 1, 0, 2, 1, 1, 1, 0, 2, 1, 8, 1, 0, 1, 2, 1, 1, 0, 7, 1, 1, 4, 0, 4, 1, 2, 1, 0, 2, 5, 1, 2, 0, 1, 1, 2, 3, 0, 1, 1, 9, 2, 0, 1, 1, 1, 1, 0, 1, 6, 1, 2, 0, 1, 3, 1, 4, 0, 1, 2, 23, 1, 0, 4

Offset: 1

Eric Chen, Mar 11 2015

nonn

a(5k+4) = 0, since (5k+4)*6^n+1 is always divisible by 5, but there are infinitely many numbers not in the form 5k+4 such that a(n) = 0. For example, a(174308) = 0 since 174308*6^n+1 is always divisible by 7, 13, 31, 37, or 97 (See A123159). Conjecture: if n is not in the form 5k+4 and n < 174308, then a(n) > 0.

However, according to the Barnes link no primes n*6^k+1 are known for n = 1296, 7776 and 46656, so these may be counterexamples. - Robert Israel, Mar 17 2015

Eric Chen, Table of n, a(n) for n = 1..1000
Gary Barnes, Sierpinski conjectures and proofs

Cf. A040076, A046067, A078680, A033809, A123159.

Cf. A250205 (Least k > 0 such that n*6^k-1 is prime).

N:= 1000: # to get a(1) to a(N), using k up to 10000
a[1]:= 1:
for n from 2 to N do
  if n mod 5 = 4 then a[n]:= 0
  else
    for k from 1 to 10000 do
    if isprime(n*6^k+1) then
       a[n]:= k;
       break
    fi
    od
  fi
od:
L:= [seq(a[n],n=1..N)]; # Robert Israel, Mar 17 2015

(* m <= 10000 is sufficient up to n = 1000 *)
a[n_] := For[k = 1, k <= 10000, k++, If[PrimeQ[n*6^k + 1], Return[k]]] /. Null -> 0; Table[a[n], {n, 1, 120}]

a(n) = if(n%5==4, 0, for(k = 1, 10000, if(ispseudoprime(n*6^k+1), return(k))))

cp's OEIS Frontend

A050412 Riesel problem: start with n; repeatedly double and add 1 until reaching a prime. Sequence gives number of steps to reach a prime or 0 if no prime is ever reached.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A318291 a(n) is the minimum k > 0 such that n*2^k - 3 is prime, or 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A078683 Least prime of the form n*2^m+1 for m>0, or 0 if there is no such prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A250204 Sierpiński problem in base 6: Least k > 0 such that n*6^k+1 is prime, or 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI