A080075 -id:A080075 - cp's OEIS frontend

A157892 Values of k in A080075.

1, 1, 1, 3, 1, 3, 1, 5, 3, 7, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5, 21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1, 17, 9, 19, 5, 21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1, 33, 17, 35, 9, 37, 19, 39, 5, 41, 21, 43, 11, 45, 23, 47, 3, 49, 25, 51, 13

Offset: 1

Zak Seidov, Mar 08 2009

nonn

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Zak Seidov, A157892
Amelia Carolina Sparavigna, Discussion of the groupoid of Proth numbers (OEIS A080075), Politecnico di Torino, Italy (2019).

Cf. A157893 (Values of m in A080075).

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

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

A157893 Values of m in A080075.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 5, 3, 4, 3, 6, 4, 5, 4, 7, 4, 5, 4, 6, 4, 5, 4, 8, 5, 6, 5, 7, 5, 6, 5, 9, 5, 6, 5, 7, 5, 6, 5, 8, 5, 6, 5, 7, 5, 6, 5, 10, 6, 7, 6, 8, 6, 7, 6, 9, 6, 7, 6, 8, 6, 7, 6, 11, 6, 7, 6, 8, 6, 7, 6, 9, 6, 7, 6, 8, 6, 7, 6, 10, 6, 7, 6, 8, 6, 7, 6, 9, 6, 7, 6, 8, 6, 7, 6, 12, 7, 8, 7, 9, 7, 8, 7, 10

Offset: 1

Zak Seidov, Mar 08 2009

nonn

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Amelia Carolina Sparavigna, Discussion of the groupoid of Proth numbers (OEIS A080075), Politecnico di Torino, Italy (2019).

Cf. A157892 (values of k in A080075), A080075 (Proth numbers).

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

A130569 Numbers of the form k*2^m + 1 for k odd, m >=1, that are not Proth numbers (A080075) (2^m <= k).

Original entry on oeis.org

7, 11, 15, 19, 21, 23, 27, 29, 31, 35, 37, 39, 43, 45, 47, 51, 53, 55, 59, 61, 63, 67, 69, 71, 73, 75, 77, 79, 83, 85, 87, 89, 91, 93, 95, 99, 101, 103, 105, 107, 109, 111, 115, 117, 119, 121, 123, 125, 127, 131, 133, 135, 137, 139, 141, 143, 147, 149, 151, 153, 155

Offset: 1

Jani Melik, Aug 10 2007

nonn

			a(1)=7 because 7 = 3*2^1 + 1 and 2^1 <= 3,
a(2)=11 because 11 = 5*2^1 + 1 and 2^1 <= 5,
a(3)=15 because 15 = 7*2^1 + 1 and 2^1 <= 7, ...

ts_neProth:=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) then am := [op(am), a ]: fi: od: od: RETURN( sort(am) ) end: ts_neProth(200);

A116882 A number k is included if (highest odd divisor of k)^2 <= k.

Original entry on oeis.org

1, 2, 4, 8, 12, 16, 24, 32, 40, 48, 56, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 544, 576, 608, 640, 672, 704, 736, 768, 800, 832, 864, 896, 928, 960, 992, 1024, 1088, 1152, 1216, 1280, 1344, 1408

Offset: 1

Leroy Quet, Feb 24 2006

Also k is included if (and only if) the greatest power of 2 dividing k is >= the highest odd divisor of k. All terms of the sequence are even besides the 1.
Equivalently, positive integers of the form k*2^m, where odd k <= 2^m. - Thomas Ordowski, Oct 19 2014
If we define a divisor d|n to be superior if d >= n/d, then superior divisors are counted by A038548 and listed by A161908. This sequence consists of 1 and all numbers without a superior odd divisor. - Gus Wiseman, Feb 18 2021
Numbers k such that A006519(k) >= A000265(k), with equality only when k = 1. - Amiram Eldar, Jan 24 2023

			40 = 8 * 5, where 8 is highest power of 2 dividing 40 and 5 is the highest odd dividing 40. 8 is >= 5 (so 5^2 <= 40), so 40 is in the sequence.

G. C. Greubel, Table of n, a(n) for n = 1..1000
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.
Milan Janjic and Boris Petkovic, A Counting Function, arXiv 1301.4550 [math.CO], 2013.
Amelia Carolina Sparavigna, Discussion of the groupoid of Proth numbers (OEIS A080075), Politecnico di Torino, Italy (2019).

Cf. A000265, A006519, A080075, A112714.
The complement is A116883.
Positions of zeros (and 1) in A341675.
A051283 = numbers without a superior prime-power divisor (zeros of A341593).
A059172 = numbers without a superior squarefree divisor (zeros of A341592).
A063539 = numbers without a superior prime divisor (zeros of A341591).
A333805 counts strictly inferior odd divisors.
A341594 counts strictly superior odd divisors.
- Inferior: A033676, A038548, A063962, A066839, A069288, A161906, A217581.
- Superior: A033677, A063538, A070038, A072500, A161908, A341676.
- Strictly Inferior: A056924, A060775, A070039, A333806, A341596, A341674.
- Strictly Superior: A056924, A064052/A048098, A140271, A238535, A341642, A341643, A341673.
Cf. A000005, A000203, A001248, A006530, A020639, A026804, A027193, A340101, A340854 (zeros of A340832), A001008, A002805.
Subsequence of A082662, {1} U A363122.

f[n_] := Select[Divisors[n], OddQ[ # ] &][[ -1]]; Insert[Select[Range[2, 1500], 2^FactorInteger[ # ][[1]][[2]] > f[ # ] &], 1, 1] (* Stefan Steinerberger, Apr 10 2006 *)
q[n_] := 2^(2*IntegerExponent[n, 2]) >= n; Select[Range[1500], q] (* Amiram Eldar, Jan 24 2023 *)

isok(n) = vecmax(select(x->((x % 2)==1), divisors(n)))^2 <= n; \\ Michel Marcus, Sep 06 2016

isok(n) = 2^(valuation(n,2)*2) >= n \\ Jeppe Stig Nielsen, Feb 19 2019

from itertools import count, islice
def A116882_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:(n&-n)**2>=n,count(max(startvalue,1)))
A116882_list = list(islice(A116882_gen(),20)) # Chai Wah Wu, May 17 2023

a(n) = A080075(n-1)-1. - Klaus Brockhaus, Georgi Guninski and M. F. Hasler, Aug 16 2010
a(n) ~ n^2/2. - Thomas Ordowski, Oct 19 2014
Sum_{n>=1} 1/a(n) = 1 + (3/4) * Sum_{k>=1} H(2^k-1)/2^k = 2.3388865091..., where H(k) = A001008(k)/A002805(k) is the k-th harmonic number. - Amiram Eldar, Jan 24 2023

More terms from Stefan Steinerberger, Apr 10 2006

A080076 Proth primes: primes of the form k*2^m + 1 with odd k < 2^m, m >= 1.

Original entry on oeis.org

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857, 10369, 10753, 11393, 11777, 12161, 12289, 13313

Offset: 1

Eric W. Weisstein, Jan 24 2003

nonn

Named after the French farmer and self-taught mathematician François Proth (1852-1879). - Amiram Eldar, Jun 05 2021

T. D. Noe, Table of n, a(n) for n = 1..10000
Chris K. Caldwell's The Top Twenty, Proth.
Bertalan Borsos, Attila Kovács and Norbert Tihanyi, Tight upper and lower bounds for the reciprocal sum of Proth primes, The Ramanujan Journal (2022).
James Grime and Brady Haran, 78557 and Proth Primes, Numberphile video, 2017.
Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
Youngik Lee, Hyperbolic Primality Test and Catalan-Mersenne Number Conjecture, Brown Univ., Preprints.org (2024). See p. 6.
Max Lewis and Victor Scharaschkin, k-Lehmer and k-Carmichael Numbers, Integers, Vol. 16 (2016), #A80.
Rogério Paludo and Leonel Sousa, Number Theoretic Transform Architecture suitable to Lattice-based Fully-Homomorphic Encryption, 2021 IEEE 32nd Int'l Conf. Appl.-specific Sys., Architectures and Processors (ASAP) 163-170.
François Proth, Théorèmes sur les nombres premiers, Comptes rendus de l'Académie des Sciences de Paris, Vol. 87 (1878), p. 926.
Mario Raso, Integer Sequences in Cryptography: A New Generalized Family and its Application, Ph. D. Thesis, Sapienza University of Rome (Italy 2025). See p. 66.
Hermann Stamm-Wilbrandt, a080076.json, sorted array of all 122,742 Proth primes less than 2^40 (> 10^12).
Tsz-Wo Sze, Deterministic Primality Proving on Proth Numbers, arXiv:0812.2596 [math.NT], 2009.
Eric Weisstein's World of Mathematics, Proth Prime.
Wikipedia, Proth prime.

Cf. A080075.
Cf. A134876 (number of Proth primes), A214120, A239234.
Cf. A248972.

N:= 20000: # to get all terms <= N
S:= select(isprime, {seq(seq(k*2^m+1, k = 1 .. min(2^m, (N-1)/2^m), 2), m=1..ilog2(N-1))}):
sort(convert(S,list)); # Robert Israel, Feb 02 2016

r[p_, n_] := Reduce[p == (2*m + 1)*2^n + 1 && 2^n > 2*m + 1 && n > 0 && m >= 0, {a, m}, Integers]; r[p_] := Catch[ Do[ If[ r[p, n] =!= False, Throw[True]], {n, 1, Floor[Log[2, p]]}]]; A080076 = Reap[ Do[ p = Prime[k]; If[ r[p] === True, Sow[p]], {k, 1, 2000}]][[2, 1]] (* Jean-François Alcover, Apr 06 2012 *)
nn = 13; Union[Flatten[Table[Select[1 + 2^n Range[1, 2^Min[n, nn - n + 1], 2], # < 2^(nn + 1) && PrimeQ[#] &], {n, nn}]]] (* T. D. Noe, Apr 06 2012 *)

is_A080076(N)=isproth(N)&&isprime(N) \\ see A080075 for isproth(). - M. F. Hasler, Oct 18 2014
next_A080076(N)={until(isprime(N=next_A080075(N)),);N}
A080076_first(N)=vector(N,i,N=if(i>1,next_A080076(N),3)) \\ M. F. Hasler, Jul 07 2022, following a suggestion from Bill McEachen

Conjecture: a(n) ~ (n log n)^2 / 2. - Thomas Ordowski, Oct 19 2014

Sum_{n>=1} 1/a(n) is in the interval (0.7473924793, 0.7473924795) (Borsos et al., 2022). - Amiram Eldar, Jan 29 2022

A033181 Absolute Euler pseudoprimes: odd composite numbers n such that a^((n-1)/2) == +-1 (mod n) for every a coprime to n.

Original entry on oeis.org

1729, 2465, 15841, 41041, 46657, 75361, 162401, 172081, 399001, 449065, 488881, 530881, 656601, 670033, 838201, 997633, 1050985, 1615681, 1773289, 1857241, 2113921, 2433601, 2455921, 2704801, 3057601, 3224065, 3581761, 3664585, 3828001, 4463641, 4903921

Offset: 1

N. J. A. Sloane, Dec 11 1999

nonn

These numbers n have the property that, for each prime divisor p, p-1 divides (n-1)/2. E.g., 2465 = 5*17*29; 1232/4 = 308; 1232/16 = 77; 1232/28 = 44. - Karsten Meyer, Nov 08 2005
All these numbers are Carmichael numbers (A002997). - Daniel Lignon, Sep 12 2015
These are odd composite numbers n such that b^((n-1)/2) == 1 (mod n) for every base b that is a quadratic residue modulo n and coprime to n. There are no odd composite numbers n such that b^((n-1)/2) == -1 (mod n) for every base b that is a quadratic non-residue modulo n and coprime to n. Note: the absolute Euler-Jacobi pseudoprimes do not exist. Theorem: if an absolute Euler pseudoprime n is a Proth number, then b^((n-1)/2) == 1 for every b coprime to n; by Proth's theorem. Such numbers are 1729, 8355841, 40280065, 53282340865, ...; for example, 1729 = 27*2^6 + 1 with 27 < 2^6. However, it seems that all absolute Euler pseudoprimes n satisfy the stronger congruence b^((n-1)/2) == 1 (mod n) for every b coprime to n, as evidenced by the modified Korselt's criterion (see the first comment). It should be noted that these are odd numbers n such that Carmichael's lambda(n) divides (n-1)/2. Also, these are odd numbers n > 1 coprime to Sum_{k=1..n-1} k^{(n-1)/2}. - Amiram Eldar and Thomas Ordowski, Apr 29 2019
Carmichael numbers k such that (p-1)|(k-1)/2 for each prime p|k. These are odd composite numbers k with half (the maximal possible fraction) of the numbers 1 <= b < k coprime to k that are bases in which k is an Euler-Jacobi pseudoprime, i.e. A329726((k-1)/2)/phi(k) = 1/2. - Amiram Eldar, Nov 20 2019
By Karsten Meyer's and Amiram Eldar's comment, this sequence is numbers k > 1 such that 2*psi(k) | (k-1), where psi = A002322. This means that if k is a term in this sequence, then we actually have a^((k-1)/2) == 1 (mod k) for every a coprime to k. - Jianing Song, Sep 03 2024

Daniel Lignon and Dana Jacobsen, Table of n, a(n) for n = 1..10000 (first 124 terms from Daniel Lignon)
Lorenzo Di Biagio, Euler Pseudoprimes for Half of the Bases, Integers, Vol. 12, No. 6 (2012), pp. 1231-1237, arXiv preprint, arXiv:1109.3596 [math.NT] (2011).
Math Help Forum, how many absolute euler pseudoprimes less than a million, Sep 2009.
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.
Index entries for sequences related to pseudoprimes

Cf. A002997, A006970, A047713, A080075, A329726.

filter:=  proc(n)
  local q;
  if isprime(n) then return false fi;
  if 2 &^ (n-1) mod n <> 1 then return false fi;
  if not numtheory:-issqrfree(n) then return false fi;
  for q in numtheory:-factorset(n) do
    if (n-1)/2 mod (q-1) <> 0 then return false fi
  od:
  true;
end proc:
select(filter, [seq(i,i=3..10^7,2)]); # Robert Israel, Nov 24 2015

absEulerpspQ[n_Integer?PrimeQ]:=False;
absEulerpspQ[n_Integer?EvenQ]:=False;
absEulerpspQ[n_Integer?OddQ]:=Module[{a=2},
While[aDaniel Lignon, Sep 09 2015 *)
aQ[n_] := Module[{f = FactorInteger[n], p},p=f[[;;,1]]; Length[p] > 1 && Max[f[[;;,2]]]==1 && AllTrue[p, Divisible[(n-1)/2, #-1] &]];Select[Range[3, 2*10^5], aQ] (* Amiram Eldar, Nov 20 2019 *)

use ntheory ":all"; my $n; foroddcomposites { say if is_carmichael($) && vecall { (($n-1)>>1) % ($-1) == 0 } factor($n=$); } 1e6; # _Dana Jacobsen, Dec 27 2015

a(n) == 1 (mod 4). - Thomas Ordowski, May 02 2019

"Absolute Euler pseudoprimes" added to name by Daniel Lignon, Sep 09 2015

Definition edited by Thomas Ordowski, Apr 29 2019

A112714 Numbers of the form k*2^m-1 with k<2^m and k odd.

Original entry on oeis.org

1, 3, 7, 11, 15, 23, 31, 39, 47, 55, 63, 79, 95, 111, 127, 143, 159, 175, 191, 207, 223, 239, 255, 287, 319, 351, 383, 415, 447, 479, 511, 543, 575, 607, 639, 671, 703, 735, 767, 799, 831, 863, 895, 927, 959, 991, 1023, 1087, 1151, 1215, 1279, 1343, 1407

Offset: 1

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

			a(4)=7 because 7 = 1*2^3 - 1, with 1 < 2^3, and it is the fourth number of this form.

Robert Israel, Table of n, a(n) for n = 1..10000
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.
Eric Weisstein's World of Mathematics, Proth Numbers

Cf. A080075.

N:= 2000: # to get all terms <= N
sort(convert({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@Flatten@Table[k*2^m - 1, {m, 0, 10}, {k, 1, 2^m - 1, 2}], 53] (* Robert G. Wilson v, Jan 02 2006 *)

for(n=2,8,for(k=2^(n-2)+1,2^n,print1(k*2^n-1","))) \\ Note that the first two terms (1,3) are not computed

a(n) = A080075(n)-2. - Thomas Ordowski, Aug 15 2025

A369901 Proth numbers h*2^k+1, with odd h < 2^k, ordered first by k then by h.

Original entry on oeis.org

3, 5, 13, 9, 25, 41, 57, 17, 49, 81, 113, 145, 177, 209, 241, 33, 97, 161, 225, 289, 353, 417, 481, 545, 609, 673, 737, 801, 865, 929, 993, 65, 193, 321, 449, 577, 705, 833, 961, 1089, 1217, 1345, 1473, 1601, 1729, 1857, 1985, 2113, 2241, 2369, 2497, 2625, 2753, 2881

Offset: 1

Daniel Sturm, Feb 05 2024

			Displayed as an irregular triangle:
  3;
  5, 13;
  9, 25, 41, 57;
  17, 49, 81, 113, 145, 177, 209, 241;
  ...

Daniel Sturm, Table of n, a(n) for n = 1..1023
David A. Corneth, PARI program.
E. Proth, Théorèmes sur les nombres premiers, Comptes rendus hebdomadaires des séances de l'Académie des sciences, 1878, p. 926.
Wikipedia, Proth Primes.

Cf. A080075 (Proth numbers).

Cf. A000051 (1st column), A020515 (right diagonal).

PARI
```
\\ See PARI link
```

def A369901(n):
    b = n.bit_length() - 1
    c = n - 2**b
    return (2*c+1)*2**(b+1)+1

a(2^b+c) = (2c+1)*2^(b+1)+1 for 0 <= c < 2^b. [Corrected by Thomas Ordowski, Aug 11 2025]

a(n) = (2n+1-2^m)*2^m+1 = (2n+1)*2^m-4^m+1, where m = floor(log_2(2n+1)). - Thomas Ordowski, Aug 11 2025

More terms from David A. Corneth, Feb 05 2024

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

A242880 Numbers that are both Poulet and Proth.

Original entry on oeis.org

1729, 4033, 8321, 12801, 65281, 130561, 348161, 3225601, 8355841, 8384513, 16773121, 40280065, 104988673, 2147418113, 4294901761, 4294967297, 53282340865, 68719214593, 137439477761, 1099510579201, 1911029760001, 2199021158401, 8796097216513, 281474959933441, 9007199388958721, 576460753377165313, 2305843011361177601, 18446744073709551617

Offset: 1

Lear Young, May 25 2014

nonn

Intersection of A080075 and A001567.

a(1) = 1729 is known as the Hardy-Ramanujan number (see A001235). - Omar E. Pol, Jun 14 2014

Giovanni Resta, Poulet n and Proth n.

Cf. A080075 (Proth numbers), A001567 (Poulet numbers).

a(20)-a(28) from Max Alekseyev, May 28 2014

cp's OEIS Frontend

A157892 Values of k in A080075.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A157893 Values of m in A080075.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A130569 Numbers of the form k*2^m + 1 for k odd, m >=1, that are not Proth numbers (A080075) (2^m <= k).

Views

Author

Keywords

Examples

Programs

Maple

A116882 A number k is included if (highest odd divisor of k)^2 <= k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A080076 Proth primes: primes of the form k*2^m + 1 with odd k < 2^m, m >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A033181 Absolute Euler pseudoprimes: odd composite numbers n such that a^((n-1)/2) == +-1 (mod n) for every a coprime to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Perl

Formula

Extensions

A112714 Numbers of the form k*2^m-1 with k<2^m and k odd.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A369901 Proth numbers h*2^k+1, with odd h < 2^k, ordered first by k then by h.

Views

Author

Keywords