A074781 -id:A074781 - cp's OEIS frontend

A039687 Primes of the form 3*2^k + 1.

7, 13, 97, 193, 769, 12289, 786433, 3221225473, 206158430209, 6597069766657, 221360928884514619393, 2353913150770005286438421033702874906038383291674012942337

Offset: 1

Felice Russo

nonn

Primes of the form 6m+1 (A002476) of A074781. - Bernard Schott, Dec 14 2020

S. W. Golomb, Properties of the sequence 3*2^n+1, Math. Comp., 30 (1976), 657-663.
S. W. Golomb, Properties of the sequence 3*2^n+1, Math. Comp., 30 (1976), 657-663. [Annotated scanned copy]
Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.

For more terms see A002253. These are the primes in A004119 (or A181565).
Cf. A002476, A074781.
Subsequence of A081091.

Select[Table[6 2^n+1,{n,0,250}],PrimeQ] (* Harvey P. Dale, Dec 17 2010 *)

A039687(n)=3<<A002253(n)+1 \\ M. F. Hasler, Mar 03 2023

a(n) = 3*2^A002253(n) + 1. - M. F. Hasler, Mar 03 2023

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

Original entry on oeis.org

7, 11, 13, 23, 29, 41, 47, 53, 59, 83, 89, 97, 107, 113, 137, 149, 167, 173, 179, 193, 227, 233, 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, 929, 977

Offset: 1

Labos Elemer, Dec 20 2000

nonn

			719 is a term because 719 = 2*359 + 1 and 359 is prime.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..2000 from T. D. Noe)

Cf. A057023, A006093.

Cf. A074781 (this sequence and the Fermat primes), A147545.

mx = 1000; Select[ Sort@ Flatten@ Table[Prime[p] 2^k + 1, {p, 2, PrimePi[ mx/2]}, {k, Log2[ mx/Prime[ p]]}], PrimeQ] (* or *)
fQ[n_] := Block[{m = n -1}, PrimeQ[m/2^IntegerExponent[m, 2]]]; Select[
Prime@ Range@ PrimePi@ mx, fQ] (* Robert G. Wilson v, Feb 09 2018 *)

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

Revised definition from T. D. Noe, Nov 03 2008

A147545 Primes of the form p*2^k+1 with k>0 and p=1 or p in this sequence.

Original entry on oeis.org

3, 5, 7, 11, 13, 17, 23, 29, 41, 47, 53, 59, 83, 89, 97, 107, 113, 137, 167, 179, 193, 227, 233, 257, 353, 359, 389, 449, 467, 641, 719, 769, 773, 857, 929, 1097, 1283, 1409, 1433, 1439, 1553, 1697, 1889, 2657, 2819, 2879, 3089, 3329, 3593, 3617, 3779, 5639

Offset: 1

T. D. Noe, Nov 07 2008

nonn

This sequence starts like A074781 but grows much faster. Observe that there can be large differences between consecutive terms. Can it be shown that there is always such a prime between consecutive powers of 2? Or that this sequence is infinite? By theorem 1 of the Noe paper, this sequence is a subsequence of A135832, primes in Section I of the phi iteration.
From Antti Karttunen, Apr 19 2020: (Start)
Sequence can be considered as a generalization of Fermat primes, A019434, which is a subsequence of this sequence.
All terms with binary weight k (A000120, at least 2 for these terms) can be found as a subset of primes found on the row k-1 of array A334100. E.g. primes with weight 2 are Fermat primes (A019434), those with weight 3 are A334092 (which doesn't contain any other primes), those with weight 4 are in A334093 (among also other kind of primes), those with weights 5, 6, 7 are included as (proper) subsets in A334094, A334095 and A334096 respectively. (End)

T. D. Noe, Table of n, a(n) for n=1..2000
T. D. Noe, Primes in classes of the iterated totient function, J. Integer Sequences, 11 (2008), Article 08.1.2.

Cf. A000265, A329697, A334100.
Subsequence of A074781, and of A135832.
Subsequences: A019434, A334092 (including A039687, A050526, A300407).

nn=2^13; t={1}; i=1; While[q=t[[i]]; k=1; While[p=1+q*2^k; p

A000265(n) = (n>>valuation(n,2));
isA147454(n) = ((n>2)&&isprime(n)&&((1==(n=A000265(n-1)))||isA147454(n))); \\ Antti Karttunen, Apr 19 2020

A329697(a(n)) = A000120(a(n)) - 1. - Antti Karttunen, Apr 19 2020

A339466 Primes p such that gpf((p - 1)/gpf(p - 1)) > 3, where gpf(m) is the greatest prime factor of m, A006530.

Original entry on oeis.org

71, 101, 131, 151, 191, 197, 211, 239, 251, 281, 311, 331, 401, 419, 421, 431, 443, 461, 463, 491, 521, 547, 571, 599, 601, 617, 631, 647, 659, 661, 677, 683, 691, 701, 727, 743, 751, 761, 821, 827, 859, 881, 883, 911, 941, 947, 953, 967, 971, 991, 1013, 1021

Offset: 1

Bernard Schott, Dec 10 2020

nonn

Paul Erdős asked if there are infinitely many primes p such that (p-1)/gpf(p-1) = 2^k or = 2^q * 3^r (see Richard K. Guy reference). This sequence lists the primes p that do not satisfy these two previous relations.

Replacing in the definition gpf by lpf (A020639) leads to A122259. In fact this sequence is a subsequence of A122259. - Peter Luschny, Dec 13 2020

			71 is prime, 70/7 = 10 = 2*5 hence 71 is a term.
101 is prime, 100/5 = 20 = 2^2*5 hence 101 is a term.
151 is prime, 150/5 = 30 = 2*3*5 hence 151 is a term.
The first few quotients obtained are: 10, 20, 10, 30, 10, 28, 30, 14, 50, 40, ...

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

Robert Israel, Table of n, a(n) for n = 1..10000
P. Erdős and C. Pomerance, On the largest prime factors of n and n+1, Aequationes Math. 17 (1978), p. 311-321. [alternate link]

Cf. A006093, A006530, A052126, A339464.
Cf. A074781 (ratio=2^k), A339465 (ratio=2^q*3^r), A339463 (ratio=2^q*5^r).
Cf. A122259.

s:=func; [p:p in PrimesInInterval(3,1100)|( not 3 in PrimeDivisors(a) and #PrimeDivisors(a) ge 2) or ( 3 in PrimeDivisors(a) and #PrimeDivisors(a) ge 3) where a is (p-1) div s(p-1)]; // Marius A. Burtea, Dec 10 2020

alias(pf = NumberTheory:-PrimeFactors): gpf := n -> max(pf(n)):
is_a := n -> isprime(n) and gpf((n-1)/gpf(n-1)) > 3:
select(is_a, [$5..1021]); # Peter Luschny, Dec 13 2020

q[n_] := Module[{f = FactorInteger[n - 1]}, (Length[f] == 1 && f[[1, 1]] == 2) || (Length[f] == 2 && f[[1, 1]] == 2 && f[[2, 2]] == 1) || (Length[f] == 2 && f[[2, 1]] == 3 && f[[2, 2]] > 1) || (Length[f] == 3 && f[[2, 1]] == 3 && f[[3, 2]] == 1)]; Select[Range[3, 1000], PrimeQ[#] && ! q[#] &] (* Amiram Eldar, Dec 10 2020 *)

is(n) = {if(!isprime(n) || n==2, return(0)); my(pm1 = n-1, f = factor(pm1)[,1]); (pm1 /= (f[#f]*1<1} \\ David A. Corneth, Dec 13 2020

More terms from Amiram Eldar, Dec 11 2020

A051900 Minimal 2^n safe-primes: a(n) = 2^n*A051886(n) + 1 (a prime number).

Original entry on oeis.org

3, 5, 13, 17, 113, 97, 193, 257, 769, 11777, 13313, 59393, 12289, 40961, 114689, 65537, 2424833, 6946817, 786433, 5767169, 7340033, 23068673, 155189249, 595591169, 1224736769, 167772161, 469762049, 2281701377, 3489660929, 12348030977, 3221225473

Offset: 0

Labos Elemer, Dec 16 1999

nonn

Equivalently, a(n) is the smallest prime p such that (p-1)/gpf(p-1) = 2^n where gpf(m) is the greatest prime factor of m, A006530. Subsequence of A074781, primes p such that the ratio (p-1)/gpf(p-1) = 2^k. - Bernard Schott, Dec 14 2020

			1 + 2^11*A051886(11) = 2048*29 + 1 = 59393 = a(11) is the smallest q prime so that (q-1)/2048 is also a (minimal, generalized Germain-) prime. The 101st term is 2385718429629527733616795432517633 = 1 + (2^101)*941.

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

Amiram Eldar, Table of n, a(n) for n = 0..1000

Cf. A005385, A006530, A051886, A074781.

alias(pf = NumberTheory:-PrimeFactors): gpf := n -> max(pf(n)):
a := proc(n) local p, q; q := 2^n; p := 2;
   while (p-1) <> gpf(p-1)*q
   do p := nextprime(p) od;
p end: seq(a(n), n=0..14); # Peter Luschny, Dec 14 2020

f[n_] := Block[{e = IntegerExponent[n - 1, 2]}, g = (n - 1)/2^e; If[g == 1, e - 1, If[ PrimeQ[g], e, -1]]]; t = Table[0, {50}]; p = 3; While[p < 13000000000, a = f@ p; If[t[[a + 1]] == 0, t[[a + 1]] = p; Print[{a, p}]]; p = NextPrime@ p]; t  (* Robert G. Wilson v, Jun 17 2012 *)
f[n_] := Block[{k = 1}, While[ !PrimeQ[2^n*Prime[k] + 1], k++]; 2^n*Prime[k] + 1]; Array[f, 32, 0] (* Robert G. Wilson v, Jun 17 2012 *)

Name clarified by Joerg Arndt, Jun 18 2012

Offset changed to 0 and a(0) prepended by Amiram Eldar, Feb 28 2025

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

A339464 a(n) = (prime(n)-1) / gpf(prime(n)-1) where gpf(m) is the greatest prime factor of m, A006530.

Original entry on oeis.org

1, 2, 2, 2, 4, 8, 6, 2, 4, 6, 12, 8, 6, 2, 4, 2, 12, 6, 10, 24, 6, 2, 8, 32, 20, 6, 2, 36, 16, 18, 10, 8, 6, 4, 30, 12, 54, 2, 4, 2, 36, 10, 64, 28, 18, 30, 6, 2, 12, 8, 14, 48, 50, 128, 2, 4, 54, 12, 40, 6, 4, 18, 10, 24, 4, 30, 48, 2, 12, 32, 2, 6, 12, 54, 2

Offset: 2

Bernard Schott, Dec 06 2020

nonn

Paul Erdős asked if there are infinitely many primes p such that (p-1)/A006530(p-1) = 2^k or = 2^q*3^r (see Richard K. Guy reference).
A074781 is the sequence of primes p such that (p-1)/A006530(p-1) = 2^k.
A339465 is the sequence of primes p such that (p-1)/A006530(p-1) = 2^q*3^r with q, r >=1.
It is not known if these two sequences are infinite.

			Prime(6) = 13 and a(6) = 12/3 = 4 = 2^2.
Prime(11) = 31 and a(11) = 30/5 = 6 = 2*3.
Prime(20) = 71 and a(20) = 70/7 =10 = 2*5.
Prime(36) = 151 and a(36) = 150/5 = 30 = 2*3*5.

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

MacTutor History of Mathematics, Paul Erdős.

Cf. A006093 (prime(n)-1), A006530, A052126, A074781 (ratio = 2^k), A339465 (ratio = 2^q*3^r), A339466 (ratio <> 2^k and <> 2^q*3^r).

f[n_] := n/FactorInteger[n][[-1, 1]]; f /@ (Select[Range[3, 400], PrimeQ] - 1) (* Amiram Eldar, Dec 07 2020 *)

gpf(n) = vecmax(factor(n)[, 1]); \\ A006530
a(n) = my(x=prime(n)-1); x/gpf(x); \\ Michel Marcus, Dec 07 2020

a(n) = A006093(n)/A006530(A006093(n)).

a(n) = A052126(A006093(n)). - Michel Marcus, Dec 07 2020

A339465 Primes p such that (p-1)/gpf(p-1) = 2^q * 3^r with q, r >= 1, where gpf(m) is the greatest prime factor of m, A006530.

Original entry on oeis.org

19, 31, 37, 43, 61, 67, 73, 79, 103, 109, 127, 139, 157, 163, 181, 199, 223, 229, 241, 271, 277, 283, 307, 313, 337, 349, 367, 373, 379, 397, 409, 433, 439, 457, 487, 499, 523, 541, 577, 607, 613, 619, 643, 673, 709, 733, 739, 757, 787, 811, 823, 829, 853, 877, 907, 919

Offset: 1

Bernard Schott, Dec 09 2020

nonn

Paul Erdős asked if there are infinitely many primes p such that (p-1)/A006530(p-1) = 2^k or = 2^q*3^r (see Richard K. Guy reference).
It is not known if this sequence is infinite.
Proposition: if prime p is a term, then p is of the form 6*m+1 (A002476).

			31 is prime, 30/5 = 6 = 2*3 hence 31 is a term.
37 is prime, 36/3 = 12 = 2^2*3 hence 37 is a term.
127 is prime, 126/7 = 18 = 2*3^2 hence 127 is a term.

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

P. Erdős and C. Pomerance, On the largest prime factors of n and n+1, Aequationes Math. 17 (1978), pp. 311-321.

Cf. A006093, A006530, A033845, A052126, A339464.
Cf. A074781 (ratio=2^k), A339466 (ratio <> 2^k and <> 2^q*3^r).
Subsequence of A002476.

s:=func; [p:p in PrimesInInterval(3,1000)|PrimeDivisors(a) eq [2,3] where a is (p-1) div s(p-1)]; // Marius A. Burtea, Dec 09 2020

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

q[n_] := PrimeQ[n] && Module[{f = FactorInteger[n - 1]}, (Length[f] == 2 && f[[2, 1]] == 3 && f[[2, 2]] > 1) || (Length[f] == 3 && f[[2, 1]] == 3 && f[[3, 2]] == 1)]; Select[Range[1000], q] (* Amiram Eldar, Dec 09 2020 *)

More terms from Marius A. Burtea, Dec 09 2020

A339463 Primes p such that (p-1)/gpf(p-1) = 2^q * 5^r with q, r >= 1, where gpf(m) is the greatest prime factor of m, A006530.

Original entry on oeis.org

71, 101, 131, 191, 251, 281, 311, 401, 431, 461, 521, 701, 761, 821, 881, 941, 971, 1031, 1061, 1091, 1151, 1181, 1301, 1361, 1451, 1481, 1511, 1571, 1601, 1721, 1811, 1901, 1931, 2081, 2111, 2141, 2351, 2411, 2441, 2621, 2711, 2741, 2801, 3041, 3251, 3371

Offset: 1

Bernard Schott, Dec 13 2020

nonn

These primes that are all congruent to 11 (mod 30) form a subsequence of A132232. The first terms of A132232 that are not terms here are 11, 41, 491, ... (see examples)

			41 is prime, 40/5 = 8 = 2^3, hence 41 is not a term.
101 is prime, 100/5 = 20 = 2^2 * 5, hence 101 is a term.
491 is prime, 490/7 = 70 = 2 * 5 * 7, hence 491 is not a term.
521 is prime, 520/13 = 40 = 2^3 * 5, hence 521 is a term.

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

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

Cf. A006093 (prime(n)-1), A006530, A052126, A339464.
Cf. A074781 (ratio=2^k), A339465 (ratio=2^q*3^r).
Subsequence of A132232 and of A339466.

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

q[n_] := Divisible[n, 10] && ((PrimeQ[(r = n/2^IntegerExponent[n, 2]/5^(e = IntegerExponent[n, 5]))] && r > 5) || (r == 1 && e > 1)); Select[Range[3500], PrimeQ[#] && q[# - 1] &] (* Amiram Eldar, Dec 13 2020 *)

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

cp's OEIS Frontend

A039687 Primes of the form 3*2^k + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A147545 Primes of the form p*2^k+1 with k>0 and p=1 or p in this sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A339466 Primes p such that gpf((p - 1)/gpf(p - 1)) > 3, where gpf(m) is the greatest prime factor of m, A006530.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Extensions

A051900 Minimal 2^n safe-primes: a(n) = 2^n*A051886(n) + 1 (a prime number).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A339464 a(n) = (prime(n)-1) / gpf(prime(n)-1) where gpf(m) is the greatest prime factor of m, A006530.

Views

Author

Keywords

Comments

Examples

References