A073918 -id:A073918 - cp's OEIS frontend

A305398 Index of the least prime not dividing p-1, where p = A073918(n) is the smallest prime such that p-1 has n distinct prime factors.

1, 2, 3, 4, 5, 6, 6, 7, 7, 9, 10, 12, 11, 12, 13, 15, 16, 15, 16, 18, 19, 20, 21, 22, 22, 23, 25, 27, 26, 29, 29, 27, 31, 33, 32, 34, 36, 36, 38, 39, 35, 38, 40, 43, 38, 44, 46, 46, 45, 48, 50, 49, 49, 51, 50, 54, 54, 57, 58, 56, 57, 58, 58, 63, 62, 64, 63, 67, 64, 68, 69, 69, 70, 69, 74, 76, 71, 73, 76, 78, 80, 79, 80, 81, 84, 84, 83, 87, 88, 86, 88

Offset: 0

M. F. Hasler, May 31 2018

nonn

For 0 <= n <= 5, A073918(n) = A002110(n) + 1 = prime(n)# + 1, therefore a(n) = n + 1. From n >= 6 on, some smaller primes are missing in the factorization of A073918(n) - 1, whence a(n) <= n.

This is related to the conjecture formulated in A073918, that for any m there is K(m) such that prime(m)# | A073918(k)-1 for all k >= K(m): This conjecture is equivalent to lim inf a(n) = oo.

			For 0 <= n <= 5, the smallest prime p = A073918(n) such that p-1 has n distinct prime factors is p = prime(n)# + 1, therefore a(n) = n + 1 is the index of the smallest prime not dividing p - 1.
For n = 6, the smallest prime p such that p - 1 has 6 distinct prime factors is prime(5)#*prime(8) + 1, therefore a(n) = 6.

Cf. A073918, A002110.

a(n)={(n=factor(A073918(n)-1)[,1])&& for(i=2,#n,n[i]>prime(i)&&return(i)); #n+1} \\ For illustration; it is more efficient to adapt code from A073918 to compute the sequence.

A305399 Index of the largest prime dividing p-1, where p = A073918(n) is the smallest prime such that p-1 has n distinct prime factors; a(0) = 0.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 8, 10, 9, 11, 11, 11, 14, 15, 17, 16, 18, 21, 21, 24, 23, 22, 23, 27, 30, 26, 29, 31, 29, 30, 35, 34, 39, 36, 39, 37, 39, 41, 39, 43, 42, 43, 46, 45, 45, 46, 51, 52, 49, 53, 56, 58, 58, 54, 58, 56, 59, 61, 60, 62, 63, 66, 66, 65, 65, 68, 68, 71, 70, 71, 73, 72, 73, 75, 75, 75, 78, 79, 82, 83, 89, 83, 85

Offset: 0

M. F. Hasler, May 31 2018

nonn

For 0 <= n <= 5, A073918(n) = A002110(n) + 1 = prime(n)# + 1, therefore a(n) = n. From n >= 6 on, some smaller primes are missing in the factorization of A073918(n) - 1, whence a(n) > n.

This is related to the question whether lim sup A073918(n)/A002110(n) has a finite value.

			For 0 <= n <= 5, the smallest prime p = A073918(n) such that p-1 has n distinct prime factors is p = prime(n)# + 1, therefore a(n) = n is the index of the largest prime dividing p - 1.
For n = 6, the smallest prime p such that p - 1 has 6 distinct prime factors is prime(5)#*prime(8) + 1, therefore a(n) = 8.

Cf. A073918, A002110.

a(n)=if(n,primepi(vecmax(factor(A073918(n)-1)[,1]))) \\ For illustration; it is more efficient to adapt code from A073918 to compute the sequence.

A305400 a(n) = round(1/(A073918(n)/prime(n)# - 1)), where A073918(n) = min { prime p | omega(p-1) = n } and p# = product of primes <= p.

Original entry on oeis.org

1, 2, 6, 30, 210, 2310, 2, 1, 3, 3, 14, 200560490130, 2, 4, 2, 8, 7, 2, 2, 2, 4, 9, 7, 3, 2, 5, 7, 4, 13, 27, 2, 3, 3, 10, 3, 8, 9, 4, 41, 7, 4, 5, 7, 32, 5, 32, 6, 5, 7, 11, 7, 4, 5, 13, 5, 21, 10, 19, 27, 8, 7, 3, 6, 51, 15, 10, 10, 15, 8, 21, 17, 29

Offset: 0

M. F. Hasler, May 31 2018

nonn

We conjecture that lim inf A073918(n)/A002110(n) = 1 but the value of the lim sup is unknown. Therefore we consider x defined as A073918(n)/A002110(n) = 1 + 1/x, and a(n) = round(x).

We have lim sup a(n) = oo <=> lim inf A073918(n)/A002110(n) = 1, and lim inf a(n) = m <=> (2m + 1)/(2m - 1) >= lim sup A073918(n)/A002110(n) >= (2m + 3)/(2m + 1), where the first inequality only holds for m >= 1.

			For 0 <= n <= 5,  A073918(n) = prime(n)# + 1, therefore a(n) = prime(n)#.
For n = 6, the smallest prime p such that p - 1 has 6 distinct prime factors is prime(5)#*prime(8) + 1, therefore a(n) = round(prime(6)/(prime(8) + 1/prime(5)# - prime(6))) = 2.

Cf. A073918, A002110, A014545, A305398, A305399.

apply( a(n)=1\/(A073918(n)/factorback(primes(n))-1), [0..99])

a(n) = round(A002110(n)/(A073918(n) - A002110(n))).

a(n) = A002110(n) <=> n in A014545 <=> primorial(n) + 1 is prime.

A081545 Smallest prime which is 1 more than the product of n distinct composite numbers.

Original entry on oeis.org

2, 5, 37, 193, 2161, 23041, 241921, 2903041, 55987201, 958003201, 17915904001, 250822656001, 5518098432001, 142216445952001, 2897001676800001, 90386452316160001, 1807729046323200001, 52563198423859200001

Offset: 0

Amarnath Murthy, Apr 01 2003

Let K(m) be the smallest possible K satisfying the Theorem. Conjecture: K(m) ~ m, i.e., a(k) ~ A002808(1)*...*A002808(k), only very few of the last factors will be insignificantly larger.
Let K(b,r) be the smallest possible K satisfying the Corollary, i.e., the index from which on all a(k)-1 are multiples of b^r. With the preceding conjecture, there are asymptotically at least (k+PrimePi(A002808(k)))/b multiples of b among the factors of a(k)-1, so this is an (asymptotic) lower bound on r.
Experimentally, a(k) = 1 + Product_{i>=1} prime(i)^e(i), with e(1)~k*3/2, e(2)~k*2/3, e(3)~k/4, e(4)~k/5, ... (Here ~ is not asymptotic equivalence.) Is there a simple formula? - M. F. Hasler, Jun 16 2007

			Writing c(n) for the n-th composite number A002808(n):
a(0) = (Product_{i=1..0} c(i))+1 = 1+1 = 2 (empty product).
a(1) = c(1)+1 = 4+1 = 5.
a(2) = c(1)*c(4)+1 = 4*9+1 = 37, since c(1)*c(k)+1 is not prime for k < 4.
a(3) = c(1)*c(2)*c(3)+1 = 4*6*8 + 1 = 193.
a(4) = c(1)*c(2)*c(4)*c(5)+1 = 2161, nothing better since c(6)*c(3) > c(5)*c(4).
a(5) = c(1)*c(2)*c(3)*c(5)*c(6)+1 = 23041, none better since c(7)*c(4) > c(5)*c(6).
a(6) = c(1)*c(2)*c(3)*c(4)*c(5)*c(7)+1 = 241921, best since c(1)*...*c(6)+1 is not prime.
a(7) = p(7)+1 = 2903041 with p(n) = Product_{i=1..n} c(i). - _M. F. Hasler_, Jun 16 2007

Jinyuan Wang, Table of n, a(n) for n = 0..300 (terms 0..99 from M. F. Hasler)

Cf. A002808 (composite numbers), A073918, A081546, A131100.

A081545(n, b=0 /*best*/, p=1 /*product*/, f=[]/*factors*/)={ if( #f= f[n+1] ) || !b = A081545( n-1, b, p*f[n], f), while( isprime( f[n]++ ),) /* next composite */ ); b } /* then vector(30,n,A081545(n-1)) gives the first 30 terms */ \\ M. F. Hasler, Jun 16 2007

Theorem: For any m > 0 there is a K > 0 such that for all k > K, a(k)-1 is divisible by the first m composite numbers.

Corollary: For any b > 1, r > 0 there is a K > 0 such that for all k > K, a(k) == 1 (mod b^r). Taking b=10 shows that all a(k) > a(8) end in 0..01 with an increasing number of zeros. - M. F. Hasler, Jun 16 2007

More terms from Michel ten Voorde Jun 13 2003

Terms beyond a(8) by M. F. Hasler Jun 16 2007

A098026 Smallest prime p such that p+1 is the product of exactly n distinct prime numbers.

Original entry on oeis.org

2, 5, 29, 389, 2309, 30029, 570569, 11741729, 300690389, 10407767369, 239378649509, 9426343036109, 304250263527209, 18740171637257069, 693386350578511589, 37508276737897976009, 2925030695773453637369, 141143645364710083725629, 8327475076517894939812169

Offset: 1

Lekraj Beedassy, Sep 10 2004

nonn

			a(4) = 389 because 389+1 = 2*3*5*13.

Max Alekseyev, Table of n, a(n) for n = 1..100

Cf. A073918 (least prime p such that p-1 has exactly n distinct prime factors).

Generate[pIndex_, i_] := Module[{p2, t}, p2=pIndex; While[p2[[i]]++; Do[p2[[j]]=p2[[i]]+j-i, {j, i+1, Length[p2]}]; t=Times@@Prime[p2]; tT. D. Noe, Dec 13 2004 *)

Corrected and extended by Ray Chandler, Sep 18 2004
Further corrected and extended by T. D. Noe, Dec 13 2004
a(14) corrected and terms a(18) onward added by Max Alekseyev, Mar 16 2023

A118883 Smallest prime p with bigomega(p+1)=n, where bigomega(m)=A001222(m) is the number of prime divisors of m (counted with multiplicity).

Original entry on oeis.org

2, 3, 7, 23, 31, 223, 127, 383, 1151, 3583, 5119, 6143, 8191, 129023, 73727, 245759, 131071, 917503, 524287, 5505023, 10616831, 14680063, 18874367, 109051903, 169869311, 654311423, 738197503, 2264924159, 2818572287, 3758096383, 2147483647, 24159191039

Offset: 1

Rick L. Shepherd, May 03 2006

nonn

Equivalently, smallest prime p such that p+1 is an n-almost prime. For smallest prime p such that p+1 is a squarefree n-almost prime, see A098026.

			a(4) = 23 because 23 is prime and 23+1 = 2*2*2*3 has 4 prime factors (24 is a 4-almost prime).

Robert G. Wilson v, Table of n, a(n) for n = 1..421

Cf. A073919, A098026, A073918.

(* copied directly from A073919 with only a sign change *) ptns[n_, 0] := If[n==0, {{}}, {}]; ptns[n_, k_] := Module[{r}, If[n v, Return[v]]; minp = Min@@ Select[l - 1, ProvablePrimeQ]; If[minp < v, v = minp]]] (* First do <Robert G. Wilson v *) Array[a, 32] (* Robert G. Wilson v, Jul 21 2011 *)

almost_primes(A, B, n) = A=max(A, 2^n); (f(m, p, n) = my(list=List()); if(n==1, forprime(q=max(p, ceil(A/m)), B\m, listput(list, m*q)), forprime(q=p, sqrtnint(B\m, n), list=concat(list, f(m*q, q, n-1)))); list); vecsort(Vec(f(1, 2, n)));
a(n) = my(x=2^n, y=2*x); while(1, my(v=almost_primes(x, y, n)); for(k=1, #v, if(isprime(v[k]-1), return(v[k]-1))); x=y+1; y=2*x); \\ Daniel Suteu, Jan 07 2025

a(26)-a(32) from Donovan Johnson, Feb 02 2011

A241196 Primes p at which phi(p-1)/(p-1) reaches a new minimum, where phi is Euler's totient function.

Original entry on oeis.org

2, 3, 7, 31, 211, 2311, 43891, 78541, 120121, 870871, 1381381, 2282281, 4084081, 13123111, 82192111, 106696591, 300690391, 562582021, 892371481, 6915878971, 71166625531, 200560490131

Offset: 1

T. D. Noe, Apr 17 2014

For these p, the numerator and denominator of phi(p-1)/(p-1) are listed in A241197 and A241198. This sequence appears to be related to A073918, the smallest prime which is 1 more than a product of n distinct primes.
By Dirichlet's theorem on primes in arithmetic progressions, for any n there is a prime p such that p-1 is divisible by the primorial A002110(n).  Then phi(p-1)/(p-1) <= Product_{i=1..n} (1 - 1/prime(i)).  Since Sum_{i >= 1} prime(i) diverges, that goes to 0 as n -> infinity.  Thus there are primes with phi(p-1)/(p-1) arbitrarily close to 0. - Robert Israel, Jan 18 2016
5*10^12 < a(23) <= 12234189897931. - Giovanni Resta, Apr 14 2016

R. K. Guy, Unsolved Problems in Number Theory, A2.

Tamiru Jarso, Tim Trudgian, Quadratic residues that are not primitive roots, arXiv:1710.04320 [math.NT], 2017.
Eric Weisstein's World of Mathematics, Euclid Number

Cf. A002110, A008330 (phi(prime(n)-1)), A073918, A241194, A241195.

m:= infinity:
p:= 1:
count:= 0:
while count < 10 do
  p:= nextprime(p);
  r:= numtheory:-phi(p-1)/(p-1);
  if r < m then
     count:= count+1;
     A[count]:= p;
     m:= r;
  fi
od:
seq(A[i],i=1..count); # Robert Israel, Jan 18 2016

tMin = {{2, 1}}; Do[p = Prime[n]; tn = EulerPhi[p - 1]/(p - 1); If[tn < tMin[[-1, -1]], AppendTo[tMin, {p, tn}]], {n, 10^7}]; Transpose[tMin][[1]]

a(20) from Dimitri Papadopoulos, Jan 11 2016

a(21)-a(22) from Giovanni Resta, Apr 14 2016

A055734 Number of distinct primes dividing phi(n).

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 3, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 3, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 3, 3, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 3, 1, 2, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 1, 2, 3, 3, 2, 2, 1, 3, 2, 2

Offset: 1

Labos Elemer, Jul 11 2000

nonn

Murty and Murty show that the normal order of a(n) is (log log n)^2/2, that is, sum_{1 <= k <= n} a(k) ~ n/2 * (log log n)^2. - Charles R Greathouse IV, Sep 13 2013. See also Erdos-Pomerance (1985) and Erdos-Granville-et-al. (1990). - N. J. A. Sloane, Sep 02 2017

Enrique Pérez Herrero, Table of n, a(n) for n = 1..5000
Paul Erdős and C. Pomerance, On the normal number of prime factors of phi(n), Rocky Mountain Math. J. 15 (1985), 343-352.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
M. Ram Murty and V. Kumar Murty, Prime divisors of Fourier coefficients of modular forms, Duke Math. J. 51:1 (1984), pp. 57-76.

Cf. A001221, A000010, A073918.

Table[PrimeNu[EulerPhi[n]], {n, 1, 50}] (* G. C. Greubel, May 08 2017 *)

a(n)=omega(eulerphi(n)) \\ Charles R Greathouse IV, Sep 13 2013

a(n) = A001221(A000010(n)).

A241197 Numerator of new minima of phi(p-1)/(p-1), where phi is Euler's totient function and p = prime(n).

Original entry on oeis.org

1, 1, 1, 4, 8, 16, 288, 256, 192, 768, 384, 3456, 3072, 6912, 6144, 55296, 1658880, 221184, 110592, 3317760, 442368, 13271040

Offset: 1

T. D. Noe, Apr 17 2014

The values of p are in A241196. The denominator is in A241198.

			In decimal, the minima are about 1, 0.5, 0.333333, 0.266667, 0.228571, 0.207792, 0.196856, 0.195569, 0.191808, 0.185194, 0.183469, 0.181713, 0.180525, 0.173812, 0.172676, 0.171024, 0.165507, 0.165127, 0.163588.

Cf. A008330 (phi(prime(n)-1)), A073918, A241194, A241195.

tMin = {{2, 1}}; Do[p = Prime[n]; tn = EulerPhi[p - 1]/(p - 1); If[tn < tMin[[-1, -1]], AppendTo[tMin, {p, tn}]], {n, 10^7}]; Numerator[Transpose[tMin][[2]]]

a(20)-a(22) from Giovanni Resta, Apr 14 2016

A241198 Denominator of new minima of phi(p-1)/(p-1), where phi is Euler's totient function and p = prime(n).

Original entry on oeis.org

1, 2, 3, 15, 35, 77, 1463, 1309, 1001, 4147, 2093, 19019, 17017, 39767, 35581, 323323, 10023013, 1339481, 676039, 20957209, 2800733, 86822723

Offset: 1

T. D. Noe, Apr 17 2014

The values of p are in A241196. The numerator is in A241197.

Cf. A008330 (phi(prime(n)-1)), A073918, A241194, A241195.

tMin = {{2, 1}}; Do[p = Prime[n]; tn = EulerPhi[p - 1]/(p - 1); If[tn < tMin[[-1, -1]], AppendTo[tMin, {p, tn}]], {n, 10^7}]; Denominator[Transpose[tMin][[2]]]

a(20)-a(22) from Giovanni Resta, Apr 14 2016

cp's OEIS Frontend

A305398 Index of the least prime not dividing p-1, where p = A073918(n) is the smallest prime such that p-1 has n distinct prime factors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A305399 Index of the largest prime dividing p-1, where p = A073918(n) is the smallest prime such that p-1 has n distinct prime factors; a(0) = 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A305400 a(n) = round(1/(A073918(n)/prime(n)# - 1)), where A073918(n) = min { prime p | omega(p-1) = n } and p# = product of primes <= p.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A081545 Smallest prime which is 1 more than the product of n distinct composite numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A098026 Smallest prime p such that p+1 is the product of exactly n distinct prime numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A118883 Smallest prime p with bigomega(p+1)=n, where bigomega(m)=A001222(m) is the number of prime divisors of m (counted with multiplicity).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A241196 Primes p at which phi(p-1)/(p-1) reaches a new minimum, where phi is Euler's totient function.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A055734 Number of distinct primes dividing phi(n).

Views

Author

Keywords

Comments