A080076 -id:A080076 - cp's OEIS frontend

A248972 a(n) is the smallest b such that b^((p-1)/2) == -1 (mod p) where p = A080076(n) is the n-th Proth prime.

2, 2, 2, 3, 3, 5, 3, 5, 7, 3, 3, 3, 5, 3, 5, 7, 3, 5, 3, 3, 3, 5, 13, 3, 3, 3, 5, 3, 5, 7, 5, 13, 3, 3, 13, 3, 11, 5, 3, 3, 3, 11, 3, 11, 3, 3, 5, 3, 7, 3, 3, 5, 3, 5, 11, 3, 3, 5, 11, 3, 7, 5, 5, 3, 5, 3, 5, 3, 3, 3, 5, 3, 3, 3, 19, 3, 3, 3, 7, 7, 3, 3, 11, 5, 3, 3, 5, 3, 11, 5, 3, 7

Offset: 1

M. F. Hasler, Oct 18 2014

nonn

Proth's theorem asserts that p=1+k*2^m (with odd k < 2^m) is prime if there exists b such that b^((p-1)/2) == -1 (mod n). This sequence lists the smallest b which certifies primality of A080076(n) via this relation.

For n > 3, a(n) is an odd prime. - Thomas Ordowski, Apr 23 2019

Cf. A080076.

A subsequence of A020649 and of A053760.

A248972(n)=my(N=A080076[n]);for(a=0,9e9,Mod(a,N)^(N\2)==-1&&return(a))
A080076=[];forprime(p=1,99999,isproth(p)&&(A080076=concat(A080076,p))&&print1(A248972(#A080076)","))
isproth(x)={ !bittest(x--, 0) & (x>>valuation(x, 2))^2 < x }

a(n) = A020649(A080076(n)) = A053760(k), where prime(k) = A080076(n). - Thomas Ordowski, Apr 23 2019

A334053 Least b such that b^(2^n) + 1 is a Proth prime (A080076).

Original entry on oeis.org

2, 2, 2, 2, 2, 96, 6912, 960, 16256, 2013184, 235520, 61184, 125440, 992256, 155615232, 550207488, 12192710656

Offset: 0

Jeppe Stig Nielsen, Sep 07 2020

Every term b is in A116882 (the prime factor 2 of b must account for more than the square root of b).

For n up to about 11, a(n) can be found with the PARI function below. From there up to n=14, you can find a(n) by filtering lists of known primes of the form b^(2^n) + 1.

Chris K. Caldwell, The Prime Pages, 12192710656^65536 + 1

Cf. A056993, A080076, A116882.

a(n) = forstep(b=2,+oo,2,2*valuation(b,2)>logint(b,2)&&ispseudoprime(b^(2^n)+1)&&return(b))

a(15) calculated by Pavel Atnashev added by Jeppe Stig Nielsen, Sep 18 2020

a(16) calculated by Pavel Atnashev added by Jeppe Stig Nielsen, Jan 05 2021

A130570 Primes of the form k*2^m + 1 for k odd, m >=1, that are not Proth primes (A080076) (2^m <= k).

Original entry on oeis.org

7, 11, 19, 23, 29, 31, 37, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 101, 103, 107, 109, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 197, 199, 211, 223, 227, 229, 233, 239, 251, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331

Offset: 1

Jani Melik, Aug 10 2007

nonn

			a(1)=7 because 7 is prime, 7 = 3*2^1 + 1 and 2^1 <= 3,
a(2)=11 because 11 is prime, 11 = 5*2^1 + 1 and 2^1 <= 5,
a(3)=19 because 19 is prime, 19 = 9*2^1 + 1 and 2^1 <= 9, ...

Cf. A080075.

ts_neProth_prime:=proc(n) local i,j,k,a,am; k := 2: am:= [ ]: for i from 1 to n do for j from 1 by 2 to n do a := j*k^(i)+1: if (k^(i) <= j and isprime(a)=true) then am := [op(am), a ]: fi: od: od: RETURN( sort(am) ) end: ts_neProth_prime(400);
# Second Maple program
q := n -> (isprime(n) and n >= 2^(2*padic:-ordp(n-1,2))):
select(q, [$3..331])[]; # Lorenzo Sauras Altuzarra, Mar 03 2023

isok(p) = if (isprime(p), my(m=valuation(p-1,2)); (m>=1) && ((p-1) >= 4^m)); \\ Michel Marcus, Mar 03 2023

A172243 Partial sums of Proth primes A080076.

Original entry on oeis.org

3, 8, 21, 38, 79, 176, 289, 482, 723, 980, 1333, 1782, 2359, 3000, 3673, 4442, 5371, 6524, 7741, 9150, 10751, 12864, 15553, 18306, 21443, 24772, 28229, 32710, 37703, 44232, 51529, 59210, 67147, 76620, 86221, 96078, 106447, 117200, 128593, 140370

Offset: 1

Jonathan Vos Post, Jan 29 2010

Eric Weisstein's World of Mathematics, Proth Prime.

Cf. A080076.

a(n) = Sum_{i=1..n} A080076(i).

More terms from R. J. Mathar, Apr 15 2010

A035050 a(n) is the smallest k such that k*2^n + 1 is prime.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 3, 2, 1, 15, 12, 6, 3, 5, 4, 2, 1, 6, 3, 11, 7, 11, 25, 20, 10, 5, 7, 15, 12, 6, 3, 35, 18, 9, 12, 6, 3, 15, 10, 5, 6, 3, 9, 9, 15, 35, 19, 27, 15, 14, 7, 14, 7, 20, 10, 5, 27, 29, 54, 27, 31, 36, 18, 9, 12, 6, 3, 9, 31, 23, 39, 39, 40, 20, 10, 5, 58, 29, 15, 36, 18, 9, 13

Offset: 0

Labos Elemer

nonn

From Ulrich Krug (leuchtfeuer37(AT)gmx.de), Jun 05 2010: (Start)
If a(i) = 2 * m then a(i+1) = m.
Proof: (I) a(i) = 2*m, 2*m * 2^i + 1 = m*2^(i+1) + 1 prime, so a(i+1) <= m;
(II) if a(i+1) = m-d for an integer d > 0, (m-d) * 2^(i+1) + 1 = (2*m-2*d) * 2^i + 1 prime;
(2m-2d) < 2m contradiction to a(i) = 2 * m, d = 0.
(End)
Conjecture: for n > 0, a(n) = k < 2^n, so k*2^n + 1 is a Proth prime A080076. - Thomas Ordowski, Apr 13 2019

			a(3)=2 because 1*2^3 + 1 = 9 is composite, 2*2^3 + 1 = 17 is prime.
a(99)=219 because 2^99k + 1 is not prime for k=1,2,...,218. The first term which is not a composite number of this arithmetic progression is 2^99*219 + 1.

T. D. Noe, Table of n, a(n) for n = 0..1000
Gareth A. Jones and Alexander K. Zvonkin, Groups of prime degree and the Bateman-Horn conjecture, 2021.
Index entries for sequences related to primes in arithmetic progressions

Analogous case is A034693. Special subscripts (n's for a(n)=1) are the exponents of known Fermat primes: A000215. See also Fermat numbers A000051.

Cf. A007522, A057778, A080076, A085427, A087522, A126717, A127575, A127576, A127577, A127578, A127580, A127581, A127586.

sol:=[];m:=1; for n in [0..82] do k:=0; while not IsPrime(k*2^n+1) do k:=k+1; end while; sol[m]:=k; m:=m+1; end for; sol; // Marius A. Burtea, Jun 05 2019

a = {}; Do[k = 0; While[ ! PrimeQ[k 2^n + 1], k++ ]; AppendTo[a, k], {n, 0, 100}]; a (* Artur Jasinski *)
Table[Module[{k=1,n2=2^n},While[!PrimeQ[k*n2+1],k++];k],{n,0,90}] (* Harvey P. Dale, May 25 2024 *)

a(n) = {my(k = 1); while (! isprime(2^n*k+1), k++); k;}

a(n) << 19^n by Xylouris' improvement to Linnik's theorem. - Charles R Greathouse IV, Dec 10 2013

A057778 a(n) is the least odd k such that k*2^n + 1 is prime.

Original entry on oeis.org

1, 1, 1, 5, 1, 3, 3, 5, 1, 15, 13, 9, 3, 5, 7, 5, 1, 9, 3, 11, 7, 11, 25, 45, 45, 5, 7, 15, 13, 23, 3, 35, 43, 9, 75, 59, 3, 15, 15, 5, 27, 3, 9, 9, 15, 35, 19, 27, 15, 23, 7, 17, 7, 51, 49, 5, 27, 29, 99, 27, 31, 53, 105, 9, 25, 9, 3, 9, 31, 23, 39, 39, 127, 23, 67, 5, 93, 29, 15, 249

Offset: 0

Labos Elemer, Nov 02 2000

nonn

There are no Sierpiński numbers in the sequence. See A076336. - Thomas Ordowski, Aug 13 2017

Conjecture: for n > 0, a(n) = k < 2^n, so k*2^n + 1 is a Proth prime A080076. - Thomas Ordowski, Apr 13 2019

			For n = 10, the first primes in the 1024k + 1 arithmetic progression occur at k = 12, 13, 15, 18, 19, ...; 13 is the first odd number, so a(10)=13, while A035050(10)=12. The corresponding primes are 12289 and 13313.
For n = 79, the first primes in the (2^79)k + 1 = 604462909807314587353088k + 1 progression occur at k = 36, 44, 104, 249, 296, 299, so a(79)=249, the first odd number, while A035050(79)=36. The two primes arising are 21760664753063325144711169 and 150511264542021332250918913, respectively.

T. D. Noe, Table of n, a(n) for n = 0..1000
Poo-Sung Park, Multiplicative functions with f(p + q - n_0) = f(p) + f(q) - f(n_0), arXiv:2002.09908 [math.NT], 2020.
Index entries for sequences related to primes in arithmetic progressions

Terms are not necessarily in A035050.

Cf. A006093, A035050, A076336, A080076 A085427, A126717.

Table[k = 1; While[! PrimeQ[k 2^n + 1], k += 2]; k, {n, 0, 80}] (* Michael De Vlieger, Jul 04 2016 *)

a(n) = k=1; while(!isprime(k*2^n+1), k+=2); k; \\ Michel Marcus, Dec 10 2013

a(n) = Min{k: 1+2^n*k is prime and k is odd}.
a(n) << 19^n by Xylouris's improvement to Linnik's theorem. - Charles R Greathouse IV, Dec 10 2013
Conjecture: a(n) = O(n*log(n)). - Thomas Ordowski, Oct 16 2014

A080075 Proth numbers: of the form k*2^m + 1 for k odd, m >= 1 and 2^m > k.

Original entry on oeis.org

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993, 1025, 1089, 1153, 1217, 1281, 1345, 1409

Offset: 1

Eric W. Weisstein, Jan 24 2003

nonn

A Proth number is a square iff it is of the form (2^(m-1)+-1)*2^(m+1)+1 = 4^m+-2^(m+1)+1 = (2^m+-1)^2 for m > 1. See A086341. - Thomas Ordowski, Apr 22 2019

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Bertalan Borsos, Attila Kovács and Norbert Tihanyi, Tight upper and lower bounds for the reciprocal sum of Proth primes, The Ramanujan Journal (2022).
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 38.
Amelia Carolina Sparavigna, Discussion of the groupoid of Proth numbers (OEIS A080075), Politecnico di Torino, Italy (2019).
Eric Weisstein's World of Mathematics, Proth Number.
Wikipedia, Proth number.

Cf. A080076, A086341, A112714, A116882, A157892, A157893.

Select[Range[3, 1500, 2], And[OddQ[#[[1]] ], #[[-1]] >= 1, 2^#[[-1]] > #[[1]] ] &@ Append[QuotientRemainder[#1, 2^#2], #2] & @@ {#, IntegerExponent[#, 2]} &[# - 1] &] (* Michael De Vlieger, Nov 04 2019 *)

is_A080075 = isproth(x)={!bittest(x--,0) && (x>>valuation(x+!x,2))^2 < x } \\ M. F. Hasler, Aug 16 2010; edited by Michel Marcus, Apr 23 2019, M. F. Hasler, Jul 07 2022

next_A080075(N)=N+2^(exponent(N)\2+1)
A080075_first(N)=vector(N,i,if(i>1,next_A080075(N),3)) \\ M. F. Hasler, Jul 07 2022

from itertools import count, islice
def A080075_gen(startvalue=3): # generator of terms >= startvalue
    return filter(lambda n:(n-1&-n+1)**2+1>=n,count(max(startvalue,3)))
A080075_list = list(islice(A080075_gen(),30)) # Chai Wah Wu, Oct 06 2024

a(n) = A116882(n+1)+1. - Klaus Brockhaus, Georgi Guninski and M. F. Hasler, Aug 16 2010
a(n) = A157892(n)*2^A157893(n) + 1. - M. F. Hasler, Aug 16 2010
a(n) ~ n^2/2. - Thomas Ordowski, Oct 19 2014
Sum_{n>=1} 1/a(n) = 1.09332245643583252894473574405304699874426408312553... (Borsos et al., 2022). - Amiram Eldar, Jan 29 2022
a(n+1) = a(n) + 2^round(L(n)/2), where L(n) is the number of binary digits of a(n); equivalently, floor(log_2(a(n))/2 + 1) in the exponent. [Lemma 2.2 in Borsos et al.] - M. F. Hasler, Jul 07 2022

A134876 Number of Proth primes: number of primes of the form 1 + k*2^n with k odd and k < 2^n.

Original entry on oeis.org

1, 2, 1, 3, 4, 8, 18, 23, 44, 73, 142, 277, 484, 871, 1644, 3060, 5851, 10917, 20776, 39263, 74752, 142521, 271223, 520242, 996486, 1916486, 3686628, 7103236, 13702428, 26469008, 51193351, 99099882, 192044541, 372559804, 723389144

Offset: 1

T. D. Noe, Nov 17 2007

nonn

The ratio a(n+1)/a(n) is about 2 * n /(n+1). - Corrected by Thomas Ordowski, Oct 17 2014

Conjecture: a(n) ~ C * 2^n / n, where C = 1/(2 log 2) = 0.7213475... - Thomas Ordowski, Oct 17 2014

			a(1)=1 because 3 is the only Proth prime for n=1.
a(2)=2 because 5 and 13 are the only primes for n=2.
a(3)=1 because 41 is the only prime for n=3.

Eric Weisstein's World of Mathematics, Proth's Theorem

Cf. A080076, A331539, A331540.

Table[cnt=0; Do[If[PrimeQ[1+k*2^n], cnt++ ], {k,1,2^n,2}]; cnt, {n,20}]

a(n) = my(s=0);forstep(k=1,2^n-1,2,s+=ispseudoprime(k<Jeppe Stig Nielsen, Jan 19 2020

More terms from Charles R Greathouse IV, Mar 18 2010

A112715 Primes in A112714.

Original entry on oeis.org

3, 7, 11, 23, 31, 47, 79, 127, 191, 223, 239, 383, 479, 607, 863, 991, 1087, 1151, 1279, 1471, 1663, 2111, 2239, 2687, 2879, 3391, 3583, 3967, 5119, 5503, 6143, 6271, 6911, 7039, 8191, 8447, 8831, 9343, 10111, 11519, 11903, 12671, 12799, 13183, 13567

Offset: 1

Jose Brox (tautocrona(AT)terra.es), Dec 31 2005

			a(1)=3 because 3=1*2^2-1 and it is the first prime of this form.

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

Cf. A080076.

N:= 10^6: # to get all terms <= N
sort(convert(select(isprime,{seq(seq(k*2^m-1,k=1..min((N+1)/2^m,2^m-1),2),m=1..ilog2(N+1))}),list)); # Robert Israel, May 23 2017

Take[Sort@ Select[Flatten@ Table[k 2^m - 1, {m, 0, 15}, {k, 1, 2^m - 1, 2}], PrimeQ], 45] (* Michael De Vlieger, May 23 2017, after Robert G. Wilson v at A112714 *)

for(n=2,8,for(k=2^(n-2)+1,2^n,M=k*2^n-1;if(isprime(M),print1(M","),0)))

A030239 a(n) is the smallest number k such that k*2^(2^n) + 1 is prime.

Original entry on oeis.org

1, 1, 1, 1, 1, 18, 12, 21, 102, 202, 826, 708, 502, 1522, 6223, 3493, 1063, 50655, 10051, 328426

Offset: 0

Alar Leibak (aleibak(AT)cyber.ee)

The primality test for Proth numbers can be used. - Thomas Ordowski, Apr 13 2019

Cf. A080075, A080076.

isok(k, n) = isprime(k*2^(2^n) + 1);
a(n) = my(k=1); while (!isok(k, n), k++); k; \\ Michel Marcus, Apr 15 2019

a(n) = min{a : a > 0 and (a*2^2^n)! == -1 (mod a*2^2^n+1)}.

a(11)-a(17) from Donovan Johnson, Mar 26 2010
a(18)-a(19) from Donovan Johnson, Jan 14 2012
Name edited by Thomas Ordowski, Apr 13 2019

cp's OEIS Frontend

A248972 a(n) is the smallest b such that b^((p-1)/2) == -1 (mod p) where p = A080076(n) is the n-th Proth prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A334053 Least b such that b^(2^n) + 1 is a Proth prime (A080076).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A130570 Primes of the form k*2^m + 1 for k odd, m >=1, that are not Proth primes (A080076) (2^m <= k).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

PARI

A172243 Partial sums of Proth primes A080076.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A035050 a(n) is the smallest k such that k*2^n + 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A057778 a(n) is the least odd k such that k*2^n + 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A080075 Proth numbers: of the form k*2^m + 1 for k odd, m >= 1 and 2^m > k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

A134876 Number of Proth primes: number of primes of the form 1 + k*2^n with k odd and k < 2^n.

Views

Author

Keywords

Comments