A058500 -id:A058500 - cp's OEIS frontend

A074781 Primes of the form p*2^k + 1 for any k and any prime p.

3, 5, 7, 11, 13, 17, 23, 29, 41, 47, 53, 59, 83, 89, 97, 107, 113, 137, 149, 167, 173, 179, 193, 227, 233, 257, 263, 269, 293, 317, 347, 353, 359, 383, 389, 449, 467, 479, 503, 509, 557, 563, 569, 587, 593, 641, 653, 719, 769, 773, 797, 809, 839, 857, 863, 887

Offset: 1

Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Sep 07 2002

nonn

From Bernard Schott, Dec 14 2020: (Start)
Equivalently, primes p such that the ratio (p-1)/gpf(p-1) = 2^k where gpf(m) is the greatest prime factor of m, A006530.
Paul Erdős asked if there are infinitely many primes p in this sequence (see R. K. Guy reference). (End)

			3 = 2*2^0+1 is a term and 2/2 = 1 = 2^0.
7 = 3*2^1+1 is a term and 6/3 = 2 = 2^1.
13 = 3*2^2+1 is a term and 12/3 = 4 = 2^2.
41 = 5*2^3+1 is a term and 40/5 = 8 = 2^3.
113 = 7*2^4+1 is a term and 112/7 = 16 = 2^4.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B46, p. 154.

T. D. Noe, Table of n, a(n) for n = 1..2000
Graeme L. Cohen, On a conjecture of Makowski and Schinzel, Colloquium Mathematicae, Vol. 74, No. 1 (1997), pp. 1-8.

Cf. A000079, A006093, A006530, A052126, A339464.
Cf. other ratios : A339463, A339465, A339466.
Subsequences: A039687, A051900, A058500 (this sequence without the Fermat primes), A090866, A147545,

alias(pf = NumberTheory:-PrimeFactors): gpf := n -> max(pf(n)):
is_a := n -> isprime(n) and pf((n-1)/gpf(n-1)) = {2}:
3, op(select(is_a, [$3..919])); # Peter Luschny, Dec 14 2020

Select[Range[3, 1000], PrimeQ[#] && !CompositeQ[(# - 1)/2^IntegerExponent[(# - 1), 2]] &] (* Amiram Eldar, Dec 28 2018 *)

A066669 Numbers m such that phi(m) = 2^k*prime for some k >= 0.

Original entry on oeis.org

7, 9, 11, 13, 14, 18, 21, 22, 23, 25, 26, 28, 29, 33, 35, 36, 39, 41, 42, 44, 45, 46, 47, 50, 52, 53, 55, 56, 58, 59, 65, 66, 69, 70, 72, 75, 78, 82, 83, 84, 87, 88, 89, 90, 92, 94, 97, 100, 104, 105, 106, 107, 110, 112, 113, 115, 116, 118, 119, 123, 130, 132, 137, 138

Offset: 1

Labos Elemer, Dec 18 2001

nonn

Sequence is infinite, since 2n is in the sequence if and only if n is in the sequence. What is its density? - Charles R Greathouse IV, Feb 21 2013

Products of powers of 2, distinct terms (at least one) of A074781, and possibly (if all the factors from A074781 are Fermat primes, A019434) an additional Fermat prime (i.e., it can be divisible by a square of one Fermat prime, A330828). - Amiram Eldar, Feb 11 2025

			7 is a term because phi(7) = 6 divided by 2 is 3, a prime.
21 is a term because phi(21) = 12 divided by 4 is 3, a prime.
15 is not a term because phi(15) = 8 divided by 8 is 1, not a prime.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000010, A066670, A066671, A066672, A066673, A065966.

Cf. A019434, A058500, A074781, A330828.

Select[Range@ 138, PrimeQ@ Last@ Most@ NestWhileList[#/2 &, EulerPhi@ #, IntegerQ@ # &] &] (* Michael De Vlieger, Mar 18 2017 *)

is(n)=n=eulerphi(n);isprime(n>>valuation(n,2)) \\ Charles R Greathouse IV, Feb 21 2013

A090865 Primes p such that (p-1)/2 is prime if p == 3 (mod 4) or (p-1)/4 is prime if p == 1 (mod 4).

Original entry on oeis.org

7, 11, 13, 23, 29, 47, 53, 59, 83, 107, 149, 167, 173, 179, 227, 263, 269, 293, 317, 347, 359, 383, 389, 467, 479, 503, 509, 557, 563, 587, 653, 719, 773, 797, 839, 863, 887, 983, 1019, 1109, 1187, 1229, 1283, 1307, 1319, 1367, 1439, 1487, 1493, 1523, 1619

Offset: 1

Benoit Cloitre, Feb 12 2004

nonn

G. C. Greubel, Table of n, a(n) for n = 1..10000

Subsequence of A058500.

Union of (A005385 \ {5}) and A090866.

Select[Prime[Range[256]], PrimeQ[(#-1)/(5-Mod[#, 4])]& ] (* Jean-François Alcover, Jul 16 2012 *)

forprime(p=1, 1619, if (((p%4==3) && isprime((p-1)/2)==1) || ((p%4==1) && isprime((p-1)/4)), print1(p, ", "))) \\ Jinyuan Wang, Feb 09 2019

A340281 a(n) is the smallest prime p such that the number of distinct values of the ratio (number of nonnegative m < p such that m^k == m (mod p))/(number of nonnegative m < p such that -m^k == m (mod p)) is equal to n for some nonnegative k.

Original entry on oeis.org

2, 3, 7, 19, 31, 163, 127, 1459, 211, 883, 811, 472393, 631, 8503057, 32077, 4051, 2311, 86093443, 4951, 6347497291777, 10531, 36451, 1299079, 251048476873, 8191, 388963, 5314411, 22051, 51031, 596046447753906250001, 28351, 411782264189299, 24571, 5904901

Offset: 1

Juri-Stepan Gerasimov, Jan 02 2021

nonn

a(n) is the least prime p such that there are n distinct terms in the p-th row of A334006.
Conjecture: a(n) is the smallest prime p such that the number of distinct values of the ratio T(p, k) = (number of nonnegative m < p such that m^k == m (mod p))/(number of nonnegative m < p such that -m^k == m (mod p)) is equal to n for some 0 <= k <= floor((p + 2)/3).
Proof: for k > 1, iff t is a k-th power residue mod p, the number of nonnegative m < p such that m^k == t (mod p) is gcd(k, p - 1). Thus, the ratio T(p, 1+x) = T(p, 1+gcd(x, p-1)) and T(p, 2*t) = T(p, (p+1)/2) = 1. For odd prime p and 0 <= k < p - 1, notice that if k is an odd number of the form 1 + gcd(x, p-1) and x != (p - 1)/2, then k <= floor((p + 2)/3). - Jinyuan Wang, Jan 23 2021
For n >= 2, a(n) is the least prime p such that p - 1 has n - 1 odd divisors. - Jinyuan Wang, Jan 23 2021

			A334006 triangle begins:
   1 | 1;
   2 | 1, 1;   : 1 distinct value
   3 | 1, 3, 1;   : 2 distinct values
   4 | 1, 2, 1, 3;
   5 | 1, 5, 1, 1, 1;   : 2 distinct values
   6 | 1, 3, 1, 3, 1, 3;
   7 | 1, 7, 1, 3, 1, 3, 1;   : 3 distinct values

Seth A. Troisi, Table of n, a(n) for n = 1..200

Cf. A001227, A019434, A058500, A074781, A334006.

T(n, k) = sum(m=0, n-1, Mod(m, n)^k == m)/sum(m=0, n-1, -Mod(m, n)^k == m); \\ A334006
a(n) = my(p=2); while (#Set(vector(p, k, T(p,k))) != n, p = nextprime(p+1)); p; \\ Michel Marcus, Jan 21 2021

lista(nn, show=50) = my(c, v=vector(show)); v[1]=2; forprime(p=3, nn, c=1+numdiv(p\2^valuation(p-1, 2)); if(c<=show && !v[c], v[c]=p)); v; \\ Jinyuan Wang, Jan 23 2021

More terms from Jinyuan Wang, Jan 23 2021

Typo in a(34) corrected by Seth A. Troisi, May 22 2022

A294074 Primes of the form p*2^k + 1, where p is an odd prime and k is odd.

Original entry on oeis.org

7, 11, 23, 41, 47, 59, 83, 89, 97, 107, 137, 167, 179, 227, 233, 263, 347, 353, 359, 383, 467, 479, 503, 563, 569, 587, 641, 719, 809, 839, 857, 863, 887, 929, 983, 1019, 1049, 1097, 1187, 1193, 1283, 1307, 1319, 1367, 1409, 1433, 1439, 1487, 1523, 1619, 1697

Offset: 1

Arkadiusz Wesolowski, Feb 07 2018

nonn

I conjecture that a number of the form p*2^k + 1 (with odd prime p and odd k) belongs to this sequence if and only if p*2^k + 1 divides (p + 2)^(p*2^k) - 1.

This conjecture has been verified for n up to 10^10.

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

Subsequence of A058500.

filter:= proc(n) local k; if not isprime(n) then return false fi; k:= padic:-ordp(n-1,2); k::odd and isprime((n-1)/2^k) end proc:
select(filter, [seq(n,n=3..2000,2)]); # Robert Israel, Mar 13 2018

lst = {}; Do[v = IntegerExponent[m - 1, 2]; If[OddQ[v], If[PrimeQ[(m - 1)/2^v] && PrimeQ[m], AppendTo[lst, m]]], {m, 3, 1697, 2}]; lst

isok(p) = isprime(p) && (pp=p-1) && (v=valuation(pp,2)) && (v%2) && isprime(pp/2^v); \\ Michel Marcus, Feb 09 2018

A276660 Primes of the form p*2^k - 1 where p is an odd prime and k >= 0.

Original entry on oeis.org

2, 5, 11, 13, 19, 23, 37, 43, 47, 61, 67, 73, 79, 103, 151, 157, 163, 191, 193, 211, 223, 271, 277, 283, 313, 331, 367, 383, 397, 421, 457, 463, 487, 523, 541, 547, 607, 613, 631, 661, 673, 691, 733, 751, 757, 787, 823, 877, 907, 991, 997, 1051, 1087, 1093, 1123

Offset: 1

Juri-Stepan Gerasimov, Sep 11 2016

nonn

			2 is in this sequence because 3*2^0 - 1 = 2 is prime.
5 is in this sequence because 3*2^1 - 1 = 5 is prime.
11 is in this sequence because 3*2^2 - 1 = 11 is prime.

Essentially the same as A192869 and A206581.

Cf. A038550, A058500.

is(n)=isprime((n+1)>>valuation(n+1,2)) && isprime(n) \\ Charles R Greathouse IV, Sep 11 2016

a(n) >> n (log n)^2. - Charles R Greathouse IV, Sep 11 2016

cp's OEIS Frontend

A074781 Primes of the form p*2^k + 1 for any k and any prime p.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A066669 Numbers m such that phi(m) = 2^k*prime for some k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A090865 Primes p such that (p-1)/2 is prime if p == 3 (mod 4) or (p-1)/4 is prime if p == 1 (mod 4).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A340281 a(n) is the smallest prime p such that the number of distinct values of the ratio (number of nonnegative m < p such that m^k == m (mod p))/(number of nonnegative m < p such that -m^k == m (mod p)) is equal to n for some nonnegative k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Extensions

A294074 Primes of the form p*2^k + 1, where p is an odd prime and k is odd.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A276660 Primes of the form p*2^k - 1 where p is an odd prime and k >= 0.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula