Displaying 21-30 of 82 results found.
Primes in the Jacobsthal sequence ( A001045).
+10
8
3, 5, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, 201487636602438195784363, 845100400152152934331135470251, 56713727820156410577229101238628035243
COMMENTS
All terms, except a(2) = 5, are of the form (2^p + 1)/3 - the Wagstaff primes A000979 = {3, 11, 43, 683, 2731, 43691, 174763, ...}.
Indices of prime Jacobsthal numbers are listed in A107036 = {3, 4, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, ...}.
Smallest prime q such that (q^p+1)/(q+1) is prime, where p = prime(n); or 0 if no such prime q exists.
+10
8
0, 2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 19, 61, 2, 7, 839, 89, 2, 5, 409, 571, 2, 809, 227, 317, 2, 5, 79, 23, 4073, 2, 281, 89, 739, 1427, 727, 19, 19, 2, 281, 11, 2143, 2, 1013, 4259, 2, 661, 1879, 401, 5, 4099, 1579, 137, 43, 487, 307, 547, 1709, 43, 3, 463, 2161, 353, 443, 2
COMMENTS
a(1) = 0 because such a prime does not exist, Mod[n^2+1,n+1] = 2 for n>1.
Corresponding primes (q^p+1)/(q+1), where prime q = a(n) and p = Prime[n], are listed in A123628[n] = {1,3,11,43,683,2731,43691,174763,2796203,402488219476647465854701,715827883,...}.
a(n) = 2 for n = PrimePi[ A000978[k]] = {2,3,4,5,6,7,8,9,11,14,18,22,26,31,39,43,46,65,69,126,267,380,495,762,1285,1304 ,1364,1479,1697,4469,8135,9193,11065,11902,12923,13103,23396,23642,31850,...}.
Corresponding primes of the form (2^p + 1)/3 are the Wagstaff primes that are listed in A000979[n] = {3,11,43,683,2731,43691,174763,2796203,715827883,...}.
FORMULA
A123628(n) = (a(n)^prime(n) + 1) / (a(n) + 1).
MAPLE
f:= proc(n) local p, q;
p:= ithprime(n);
q:= 1;
do
q:= nextprime(q);
if isprime((q^p+1)/(q+1)) then return q fi
od
end proc:
f(1):= 0:
MATHEMATICA
a(1) = 0, for n>1 Do[p=Prime[k]; n=1; q=Prime[n]; cp=(q^p+1)/(q+1); While[ !PrimeQ[cp], n=n+1; q=Prime[n]; cp=(q^p+1)/(q+1)]; Print[q], {k, 2, 61}]
Do[p=Prime[k]; n=1; q=Prime[n]; cp=(q^p+1)/(q+1); While[ !PrimeQ[cp], n=n+1; q=Prime[n]; cp=(q^p+1)/(q+1)]; Print[{k, q}], {k, 1, 134}]
spq[n_]:=Module[{p=Prime[n], q=2}, While[!PrimeQ[(q^p+1)/(q+1)], q=NextPrime[ q]]; q]; Join[{0}, Array[spq, 70, 2]] (* Harvey P. Dale, Mar 23 2019 *)
11, 1011, 101011, 1010101011, 101010101011, 1010101010101011, 101010101010101011, 1010101010101010101011, 101010101010101010101010101011, 101010101010101010101010101010101010101011
MATHEMATICA
b[n_] := FromDigits[IntegerDigits[n, 2]]; b /@ Select[Table[(2^p + 1)/3, {p, Prime[Range[15]]}], PrimeQ] (* Amiram Eldar, Jul 23 2023 *)
PROG
(Python)
from gmpy2 import divexact
from sympy import prime, isprime
A127962 = [int(bin(p)[2:]) for p in (divexact(2**prime(n)+1, 3) for n in range(2, 10**2)) if isprime(p)] # Chai Wah Wu, Sep 04 2014
CROSSREFS
Cf. A000978, A000979, A007088, A124400, A126614, A127936, A127955, A127956, A127957, A127958, A127961.
Numbers k such that (38^k + 1)/39 is prime.
+10
8
5, 167, 1063, 1597, 2749, 3373, 13691, 83891, 131591
COMMENTS
All terms are primes. a(9) > 10^5.
LINKS
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
Eric Weisstein's World of Mathematics, Repunit.
MATHEMATICA
Do[ p=Prime[n]; If[ PrimeQ[ (38^p + 1)/39 ], Print[p] ], {n, 1, 9592} ]
CROSSREFS
Cf. A000978 = numbers n such that (2^n + 1)/3 is prime. Cf. A007658, A057171, A057172, A057173, A057175, A001562, A057177, A057178, A057179, A057180, A057181, A057182, A057183, A057184, A057185, A057186, A057187, A057188, A057189, A057190, A057191, A071380, A071381, A071382, A084741, A084742, A065507, A126659, A126856, A185240, A229145.
EXTENSIONS
a(9)=131591 corresponds to a probable prime discovered by Paul Bourdelais, Jul 03 2018
Numbers k such that (2^k + 9^k)/11 is prime.
+10
7
3, 7, 127, 283, 883, 1523, 4001
COMMENTS
All terms are primes. Note that first 3 terms {3, 7, 127} are primes of the form 2^q - 1, where q = {2, 3, 7} is prime too. Corresponding primes of the form (2^k + 9^k)/11 are {67, 434827, ...}.
MATHEMATICA
Do[p=Prime[n]; f=(2^p+9^p)/11; If[PrimeQ[f], Print[{p, f}]], {n, 1, 100}]
CROSSREFS
Cf. A000978 = numbers n such that (2^n + 1)/3 is prime.
Cf. A057469 = numbers n such that (2^n + 3^n)/5 is prime.
Cf. A082387 = numbers n such that (2^n + 5^n)/7 is prime.
Numbers k such that 2^k + 1 is the product of two distinct primes.
+10
6
5, 6, 7, 11, 12, 13, 17, 19, 20, 23, 28, 31, 32, 40, 43, 61, 64, 79, 92, 101, 104, 127, 128, 148, 167, 191, 199, 256, 313, 347, 356, 596, 692, 701, 1004, 1228, 1268, 1709, 2617, 3539, 3824, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239
COMMENTS
Original name: "2^n + 1 is squarefree and has exactly 2 prime factors."
As 3 divides 2^a(n) + 1 for any odd term a(n), all odd terms are prime and exactly the Wagstaff primes ( A000978), at the exclusion of 3 (which gives 2^3 + 1 = 3^2 not squarefree).
For the even terms, let a(n) = d * 2^j with d odd integer and j > 0. If d > 1, as (2^2^j)^q + 1 divides 2^a(n) + 1 for any odd prime q dividing d, then d must be prime.
So the even terms are all given by the following two class:
a) (d = 1) a(n) = 2^j such that Fj is a semiprime Fermat number. Up to now, only j = 5, 6, 7, 8 are known to give a Fermat semiprime, giving the even terms 32, 64, 128 and 256. We are also assured that 2^j is not a term for j = 9..19 because Fj is not a semiprime for those value of j (see Wagstaf's link). F20 is the first composite Fermat number which could give another even term (it would be 2^20 = 1048576). However, it seems highly unlikely that other Fermat semiprimes could exist.
b) (d = p odd prime) a(n) = p * 2^j with j such that Fj is a Fermat prime and p a prime verifying ((Fj - 1)^p + 1)/Fj is a prime.
Exemplifying that, we have:
for j = 1 this gives only the even term a(2) = 2 * 3 = 6 (see Jack Brennen's result in ref),
for j = 2 we have all the terms of type 2^2 * A057182.
for j = 3 the even terms are of type 2^3 * A127317.
For j = 4 at least up to 200000, there is only the term a(41) = 2^4 * 239 = 3824 (see comment in A127317).
All terms after a(50) refer to probabilistic primality tests for 2^a(n) + 1 (see Caldwell's link for the list of the largest certified Wagstaff primes).
After a(56), from the above, the primes 267017, 269987, 374321, 986191, 4031399 and the even value 4101572 are also terms, but still remains the (remote) possibility of some gaps in between. In addition, 13347311 and 13372531 are also terms, but possibly much further in the numbering (see comments in A000978).
(End)
LINKS
AMS Books Online, Factorizations of b^n = +-1, b=2,3,5,6,7,10,11,12 Up to High Powers, Third Edition.
EXAMPLE
11 is a member because 1 + 2^11 = 2049 = 3 * 683.
9 is not a term because 1 + 2^9 = 513 = 3^3 * 19
MATHEMATICA
Do[ If[ Length[ Divisors[1 + 2^n]] == 4, Print[n]], {n, 1, 200}]
(* Second program: *)
PROG
(Sage) [n for n in xsrange(3, 200) if sigma(2^n+1, 0)==4]
# Second program (faster):
(Sage) v=[]; N=2000
for n in xsrange(4, N):
j=valuation(n, 2)
if j<5:
Fj=2^2^j+1; p=ZZ(n/2^j); q=ZZ((2^n+1)/Fj)
if p.is_prime() and q.is_prime(proof=false): v.append(n)
elif j<9 and n.is_power_of(2): v.append(n)
Numbers n such that (40^n + 1)/41 is prime.
+10
6
53, 67, 1217, 5867, 6143, 11681, 29959
COMMENTS
All terms are primes.
a(8) > 10^5.
LINKS
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
Eric Weisstein's World of Mathematics, Repunit.
MATHEMATICA
Do[ p=Prime[n]; If[ PrimeQ[ (40^p + 1)/41 ], Print[p] ], {n, 1, 9592} ]
CROSSREFS
Cf. A000978 = numbers n such that (2^n + 1)/3 is prime. Cf. A007658, A057171, A057172, A057173, A057175, A001562, A057177, A057178, A057179, A057180, A057181, A057182, A057183, A057184, A057185, A057186, A057187, A057188, A057189, A057190, A057191, A071380, A071381, A071382, A084741, A084742, A065507, A126659, A126856, A185240, A229145, A229524.
Numbers n such that (39^n + 1)/40 is prime.
+10
6
COMMENTS
All terms are primes.
a(5) > 10^5.
LINKS
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
Eric Weisstein's World of Mathematics, Repunit.
MATHEMATICA
Do[ p=Prime[n]; If[ PrimeQ[ (39^p + 1)/40 ], Print[p] ], {n, 1, 9592} ]
CROSSREFS
Cf. A000978 (numbers n such that (2^n + 1)/3 is prime).
Cf. A007658, A057171, A057172, A057173, A057175, A001562, A057177, A057178, A057179, A057180, A057181, A057182, A057183, A057184, A057185, A057186, A057187, A057188, A057189, A057190, A057191, A071380, A071381, A071382, A084741, A084742, A065507, A126659, A126856, A185240, A229145, A229524.
Numbers k such that 2^k + 1 has just two distinct prime factors.
+10
5
5, 6, 7, 9, 10, 11, 12, 13, 17, 19, 20, 23, 28, 31, 32, 40, 43, 61, 64, 79, 92, 101, 104, 127, 128, 148, 167, 191, 199, 256, 313, 347, 356, 596, 692, 701, 1004, 1228, 1268, 1709, 2617, 3539, 3824, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369
COMMENTS
All terms after a(52) refer to probabilistic primality tests for 2^a(n) + 1 (see Caldwell's link for the list of the largest certified Wagstaff primes). After a(58), 267017, 269987, 374321, 986191, 4031399 and 4101572 are also terms, but there still remains the remote possibility of some gaps in between. In addition, 13347311 and 13372531 are also terms, but possibly much farther in the numbering (see comments in A000978).
For the relation with Fermat numbers and for the primality of odd terms, see comments in A073936. The terms 9 and 10 give a value of 2^n + 1 which is not squarefree, so they are not in A073936. For the rest, the actually known terms of the two sequences coincide. In order to verify if any other term could be found hereafter that is not in A073936, all we have to do is to examine the terms for which 2^n + 1 is not squarefree. Considering that 3 divides 2^a(n) + 1 for any odd term a(n) and using Zsigmondy's and Mihăilescu-Catalan's theorems (see links), one can verify that any nonsquarefree term greater than 9 has to be of the form a(n) = 2^j * Fj, where Fj is the Fermat prime 2^2^j + 1. So basically we have to see if ((Fj-1)^Fj + 1)/(Fj)^2 is a prime or the power of a prime for any Fermat prime Fj. The case j = 1 gives the term a(n) = 10 because (4^5 + 1)/5^2 = 41 is a prime, while for j = 2, (16^17 + 1)/17^2 = 354689 * 2879347902817 is composite. Similarly (256^257 + 1)/257^2 is neither a prime nor the power of a prime, so there is no contribution from the cases j = 2, 3 (see also comments in A127317).
For j = 4 and for any possible other Fermat prime which could be found later, the question is still open, in the sense that it is not actually known if n = 16 * F4 = 1048592 is a term or not. That seems very unlikely, but in order to decide that question for j = 4, one would have to check if (2^1048592 + 1)/65537^2 is a prime or the power of a prime. As this number has 315649 digits, I wonder if it is possible to handle it with the existing primality tests.
(End)
EXAMPLE
3 and 4 are not terms because 2^3 + 1 and 2^4 + 1 have only a single prime factor (counted without multiplicity).
6 and 10 are terms because 2^6 + 1 = 5 * 13 and 2^10 + 1 = 5^2 * 41 have two distinct prime factors.
MATHEMATICA
f[n_] := First[ Transpose[ FactorInteger[2^n + 1]]]; Select[ Range[100], Length[f[ # ]] == 2 & ]
Select[Range[1300], PrimeNu[2^#+1]==2&] (* Harvey P. Dale, Nov 28 2014 *)
PROG
(PARI) isok(k) = #factor(2^k+1)~ == 2; \\ Michel Marcus, Nov 14 2017
Smallest prime of the form (q^p+1)/(q+1), where p = prime(n) and q is also prime (q = A123627(n)); or 1 if such a prime does not exist.
+10
5
1, 3, 11, 43, 683, 2731, 43691, 174763, 2796203, 402488219476647465854701, 715827883, 10300379826060720504760427912621791994517454717, 254760179343040585394724919772965278539769280548173566545431025735121201
COMMENTS
a(1) = 1 because such a prime does not exist; (n^2+1) mod (n+1) = 2 for n > 1. a(n) = ( A103795(n)^prime(n)+1)/( A103795(n)+1) when A103795(n) is prime. Corresponding smallest primes q such that (q^p+1)/(q+1) is prime, where p = prime(n), are listed in A123627(n) = {0, 2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 19, 61, 2, 7, 839, 1459, 2, 5, 409, 571, 2, ...}. All Wagstaff primes or primes of form (2^p + 1)/3 belong to a(n). Wagstaff primes are listed in A000979(n) = {3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, ...}. Corresponding indices n such that a(n) = (2^prime(n) + 1)/3 are PrimePi( A000978(n)) = {2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 18, 22, 26, 31, 39, 43, 46, 65, 69, 126, 267, 380, 495, 762, 1285, 1304, 1364, 1479, 1697, 4469, 8135, 9193, 11065, 11902, 12923, 13103, 23396, 23642, 31850, ...}. All primes with prime indices in the Jacobsthal sequence A001045(n) belong to a(n).
Search completed in 0.055 seconds
|