A073917 -id:A073917 - cp's OEIS frontend

A073918 Smallest prime which is 1 more than a product of n distinct primes: a(n) is a prime and a(n) - 1 is a squarefree number with n prime factors.

2, 3, 7, 31, 211, 2311, 43891, 870871, 13123111, 300690391, 6915878971, 200560490131, 11406069164491, 386480064480511, 18826412648012971, 693386350578511591, 37508276737897976011, 3087649419126112110271, 183452981525059000664911, 11465419967969569966774411

Offset: 0

Amarnath Murthy, Aug 18 2002

nonn

Apparently the same as record values of A055734: least k such that phi(k) has n distinct prime factors, where phi is Euler's totient function. If the Mathematica program is used for large n, then "fact" should be reduced to, say, 1.1 in order to increase the search speed. - T. D. Noe, Dec 17 2003

			a(0) = 1 + 1 = 2 (empty product of zero primes).
a(1) = 1 + 2 = 3.
a(2) = 1 + 2*3 = 7.
a(3) = 1 + 2*3*5 = 31.
a(4) = 1 + 2*3*5*7 = 211.
a(5) = 1 + 2*3*5*7*11 = 1 + 11# = 2311.
a(6) = 1 + 2*3*5*7*11*19 = 43891, since 13# + 1 and 11#*17 + 1 = 17#/13 + 1 is not prime, and 17#/p + 1 is larger than a(6) for all p in {2, ..., 11}.
The index of the smallest prime which is not a factor of a(n)+1 is (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, ...) for n = 0, 1, 2, ... - _M. F. Hasler_, May 31 2018

Max Alekseyev, Table of n, a(n) for n = 0..100 (terms for n = 0..24 from M. F. Hasler)

Cf. A055734 (number of distinct prime factors of phi(n)).
Cf. A073917, A098026.
Cf. A000040 (primes), A002110 (primorial), A081545 (same with composite instead of primes).

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]; t

A073918(n, b=0 /*best*/, p=1 /*product*/, f=[]/*factors*/)={ if( #f= f[n+1] ) || !b = A073918( n-1, b, p*f[n], f), f[n]= nextprime( f[n]+1 ) ); b } \\ then, e.g.: apply(A073918, [0..30]). - M. F. Hasler Jun 16 2007

From M. F. Hasler, Jun 16 2007 (Start):
Conjecture: For any m > 0 there is K > 0 such that for all k > K, a(k)-1 is divisible by the first m primes.
Corollary: For any m > 1 there is K > 0 such that for all k > K, a(k) = 1 (mod m).
Conjecture 2: Let K(m) be the smallest possible K satisfying the above Conjecture. Then K(m) ~ m, i.e., a(k) ~ A002110(k), only very few of the last factors will be a bit larger. (End)
Remark: the last "~" above was not intended to mean asymptotic equivalence. It appears that lim inf a(n)/A002110(n) = 1, but the lim sup might well be larger. It would be interesting to know whether it has a finite value. - M. F. Hasler, May 31 2018

More terms from Vladeta Jovovic, Aug 20 2002

Edited by M. F. Hasler, May 31 2018

A214089 Least prime p such that the first n primes divide p^2-1.

Original entry on oeis.org

3, 5, 11, 29, 419, 1429, 1429, 315589, 1729001, 57762431, 1724478911, 6188402219, 349152569039, 1430083494841, 390499187164241, 1010518715554349, 18628320726623609, 522124211958421799, 522124211958421799, 5936798290039408015951, 311263131154464891496249

Offset: 1

Robin Garcia, Jul 02 2012

(a(n)^2 - 1) / A002110(n) is congruent to 0 (mod 4). (a(n)^2 - 1) / (4*A002110(n)) = A215085(n). [J. Stauduhar, Aug 03 2012]

a(n) == +1 or -1 (mod prime(i)) for every i=1,2,...,n. The system of congruences x == +1 or -1 (mod prime(i)), i=1,2,...,n, has 2^(n-1) solutions modulo A002110(n) so that a(n) represents the smallest prime in the corresponding residue classes, allowing efficient computation (see PARI program). - Max Alekseyev, Aug 22 2012

			a(5) = 419: 419^2-1 = 175560 = 2^3*3*5*7*11*19 contains the first 5 primes.
a(7) = 1429:  1428=2^2*3*7*17, 1430=2*5*11*13 contains the first 7 primes.
a(8) = 315589: 315589^2-1 = 2^3*3*5*7*11*13*17^2*19*151 contains the first 8 primes.

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

Cf. A073917, A103783.

A214089 := proc(n)
     local m,k,p;
   m:= 2*mul(ithprime(j),j=1..n);
   for k from 1 do
     p:= sqrt(m*k+1);
     if type(p,integer) and isprime(p) then return(p)
     end if
   end do
end proc;
# Robert Israel, Aug 19 2012

f[n_] := Block[{k = 1, p = Times @@ Prime@Range@n}, While[! IntegerQ@Sqrt[4 k*p + 1], k++]; Block[{j = k}, While[! PrimeQ[Sqrt[4 j*p + 1]], j++]; Sqrt[4 j*p + 1]]]; Array[f, 10] (* J. Stauduhar, Aug 18 2012 *)

A214089(n) = {
        local(a,k=4,p) ;
        a=prod(j=1,n,prime(j)) ;
        while(1,
                if( issquare(k*a+1, &p),
                        if(isprime(p),
                                return(p);
                        ) ;
                ) ;
                k+=4;
        ) ;
} ;

{ a(n) = local(B,q); B=prod(i=1,n,prime(i))^2; forvec(v=vector(n-1,i,[0,1]), q=chinese(concat(vector(n-1,i,Mod((-1)^v[i],prime(i+1))),[Mod(1,2)])); forstep(s=lift(q),B-1,q.mod,if(ispseudoprime(s),B=s;break)) ); B } /* Max Alekseyev, Aug 22 2012 */

from itertools import product
from sympy import sieve, prime, isprime
from sympy.ntheory.modular import crt
def A214089(n): return 3 if n == 1 else int(min(filter(isprime,(crt(tuple(sieve.primerange(prime(n)+1)), t)[0] for t in product((1,-1),repeat=n))))) # Chai Wah Wu, May 31 2022

a(15)-a(16) from Donovan Johnson, Jul 25 2012
a(17) from Charles R Greathouse IV, Aug 08 2012
a(18) from Charles R Greathouse IV, Aug 16 2012
a(19) from J. Stauduhar, Aug 18 2012
a(20)-a(32) from Max Alekseyev, Aug 22 2012

A103783 Primes of the form primorial P(k)*n-1 with minimal n, n>0, k>=2.

Original entry on oeis.org

5, 29, 419, 2309, 30029, 1021019, 19399379, 669278609, 38818159379, 601681470389, 14841476269619, 304250263527209, 235489703970060539, 1844669347765474229, 228124109340330313109, 24995884552004764307909

Offset: 1

Lei Zhou, Feb 15 2005

nonn

Weak conjecture: sequence is defined for all k>=2; strong conjecture: n<(prime(k))^2;

Smallest prime p such that the prime factorization of p+1 contains the first n+1 primes. - R. J. Mathar, Jul 03 2012

			P(2)*1-1=5 is prime, so a(2)=5;
P(9)*3-1=669278609 is prime, so a(9)=669278609;

Cf. A002110, A103515, A103782, A073917, A214089.

nmax = 2^2048; npd = 2; n = 2; npd = npd*Prime[n]; While[npd < nmax, tt = 1; cp = npd*tt - 1; While[(tt <= (Prime[n])^2) && (! (PrimeQ[cp])), tt = tt + 1; cp = npd*tt - 1]; Print[cp]; n = n + 1; npd = npd*Prime[n]]

A272981 Least prime k>1 such that the sum of divisors of powers k^e, 1 <= e <= n, are divisible by the number their divisors, d(k^e).

Original entry on oeis.org

3, 7, 7, 31, 31, 211, 211, 211, 211, 2311, 2311, 120121, 120121, 120121, 120121, 4084081, 4084081, 106696591, 106696591, 106696591, 106696591, 892371481, 892371481, 892371481, 892371481, 892371481, 892371481, 71166625531, 71166625531, 200560490131, 200560490131

Offset: 1

Paolo P. Lava, May 12 2016

nonn

For 1A272981(n) = A092967(n+1).

The different numbers are listed in A073917.

			sigma(3) / d(3) = 4 / 2 = 2 but sigma(3^2) / d(3^2) = 13 / 3;
sigma(7) / d(7) = 8 / 2 = 4, sigma(7^2) / d(7^2) = 57 / 3 = 19, sigma(7^3) / d(7^3) = 400 / 4 = 100 but sigma(7^4) / d(7^4) = 2801 / 5.

Paolo P. Lava, Table of n, a(n) for n = 1..100

Cf. A000005, A000203, A073917, A092967, A272980.

with(numtheory): P:= proc(q) local a,j,k,ok,p; global n; a:=2;
for k from 1 to q do for n from a to q do ok:=1;
for j from 1 to k do if not type(sigma(n^j)/tau(n^j),integer) then ok:=0; break; fi; od;
if ok=1 then a:=n; print(n); break; fi; od; od; end: P(10^9);

Table[SelectFirst[Range[2, 10^6], AllTrue[#^Range@ n, Divisible[DivisorSigma[1, #], DivisorSigma[0, #]] &] &], {n, 15}] (* Michael De Vlieger, May 12 2016, Version 10 *)

A359262 a(n) is the largest number m such that prime(n)^m is in A359260.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 1, 3, 1, 1, 5, 3, 1, 3, 1, 1, 1, 5, 3, 1, 3, 3, 1, 1, 3, 1, 3, 1, 3, 1, 3, 1, 1, 3, 1, 5, 3, 3, 1, 1, 1, 5, 1, 3, 1, 3, 9, 3, 1, 3, 1, 1, 5, 1, 1, 1, 1, 5, 3, 1, 3, 1, 3, 1, 3, 1, 5, 3, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 3, 1, 9, 1, 3, 3, 1, 1

Offset: 1

Amiram Eldar, Dec 23 2022

a(n) is the largest number m such that the arithmetic mean of {1, p, p^2, ..., p^k} is an integer for all k in 1..m.
Apparently, all the terms are of the form prime(k)-2 (A040976). Conjecture: The asymptotic density of the occurrences of prime(k)-2 is (1/s(k-1)-1/s(k)), where s(k) = A005867(k) = phi(prime(k)#), and prime(k)# is the k-th primorial number (A002110).
The sums of the first 10^k terms, for k = 1, 2, ..., are 15, 221, 2291, 23287, 233641, 2337007, 23379901, 233814475, 2338211029, 23382168187, ... . If the mentioned above conjecture is correct, then the asymptotic mean of this sequence is Sum_{k>=1} (prime(k)-2)*(1/s(k-1)-1/s(k)) = 2.33821872365981424748... .
Apparently, the indices of records after n = 1 occur at A000720(A073917(n)) (verified for the first 12 terms of A073917) with record values a(A000720(A073917(n))) = prime(n+1) - 2 (verified for the first 150 terms of A073917).

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000720, A002110, A040976, A073917, A005867, A359260, A359261.

Cf. A002476, A073102, A132230.

a[n_] := Module[{p = Prime[n], k = 1, r = s = 1}, While[Divisible[s, k], k++; r *= p; s += r]; k - 2]; Array[a, 100]

a(n) = {my(p = prime(n), k = 1, r = s = 1); while(!(s%k), k++; r *= p; s += r); k - 2; }

a(n) >= 1 for n >= 2.
a(n) >= 3 iff prime(n) == 1 (mod 6) (prime(n) is in A002476).
Conjectures:
a(n) >= 5 iff prime(n) == 1 (mod 30) (prime(n) is in A132230).
a(n) >= 9 iff prime(n) == 1 (mod 210) (prime(n) is in A073102).
a(n) >= prime(k) - 2 iff prime(n) == 1 (mod A002110(k-1)).

A076689 Smallest k such that k*prime(n)# + 1 is prime where prime(n)# is the n-th primorial number A002110(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 8, 11, 4, 11, 1, 4, 7, 6, 14, 3, 5, 2, 7, 3, 6, 20, 2, 9, 20, 2, 5, 7, 31, 2, 12, 13, 24, 7, 39, 21, 35, 24, 22, 3, 21, 8, 9, 13, 39, 21, 29, 10, 3, 62, 52, 21, 3, 36, 28, 15, 18, 33, 7, 46, 33, 20, 14, 22, 41, 7, 27, 39, 20, 4, 4, 5, 15, 27, 1, 44, 99, 9, 52, 2, 27, 12

Offset: 1

Jason Earls, Nov 10 2002

nonn

From Pierre CAMI, Sep 12 2017: (Start)
Conjectures:
lim_{N->infinity} (Sum_{n=1..N} a(n)) / (Sum_{n=1..N} n) = 1/2;
a(n)/n is always < 4.
This is certified for the first 3100 primes a(n)*prime(n)#+1.
(End)

Pierre CAMI, Table of n, a(n) for n = 1..3100
Pierre CAMI, PFGW Sript

Cf. A002110, A014545 (n for which k=1), A073917 (the primes).

With[{P = FoldList[Times, Prime@ Range@ 120]}, Table[k = 1; While[CompositeQ[k P[[n]] + 1], k++]; k, {n, Length@ P}]] (* Michael De Vlieger, Sep 18 2017 *)

a(n) = my(k=1, pr = prod(i=1, n, prime(i))); while (! isprime(k*pr+1), k++); k; \\ Michel Marcus, Oct 09 2017

A167857 Numbers whose divisors are represented by an integer polynomial.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 10, 11, 13, 17, 19, 22, 23, 25, 29, 31, 34, 37, 41, 43, 46, 47, 49, 53, 55, 58, 59, 61, 67, 71, 73, 79, 82, 83, 85, 89, 91, 94, 97, 101, 103, 106, 107, 109, 113, 115, 118, 121, 127, 131, 133, 137, 139, 142, 145, 149, 151, 157, 163, 166, 167, 169, 171

Offset: 1

T. D. Noe, Nov 13 2009

nonn

That is, these numbers n have the property that there is a polynomial f(x) with integer coefficients whose values at x=0..tau(n)-1 are the divisors of n, where tau(n) is the number of divisors of n.

Every prime has this property, as do 1 and 9, the squares of primes of the form 6k+1, and semiprimes p*q with p and q both primes of the form 3k-1 or 3k+1. Terms of the form p^2*q also appear. We can find terms of the form p^m for any m. For example, 2311^13 is the smallest 13th power that appears. For any m, it seems that p^m appears for p a prime of the form k*m#+1, where m# is the product of the primes up to m. Are there terms with three distinct prime divisors?

			The divisors of 55 are (1, 5, 11, 55). The polynomial 1+15x-17x^2+6x^3 takes these values at x=0..3.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A108164, A108166, A112774 (forms of semiprimes)
Cf. A002476 (primes of the form 6k+1)
Cf. A132230 (primes of the form 30k+1)
Cf. A073103 (primes of the form 210k+1)
Cf. A073917 (least prime of the form k*prime(n)#+1)

Select[Range[1000], And @@ IntegerQ /@ CoefficientList[Expand[InterpolatingPolynomial[Divisors[ # ], x+1]], x] &]

is(n)=my(d=divisors(n));denominator(content(polinterpolate([0..#d-1],d))) == 1 \\ Charles R Greathouse IV, Jan 29 2016

A191346 Primes = 1 mod 17#.

Original entry on oeis.org

4084081, 5105101, 8168161, 8678671, 9189181, 10720711, 12762751, 13273261, 13783771, 14804791, 18888871, 21441421, 21951931, 22972951, 25014991, 26546521, 28078051, 31651621, 36246211, 38288251, 40330291

Offset: 1

Zak Seidov, May 31 2011

Infinite by Dirichlet's theorem.

a(1)=A073917(7), 17#(=510510=A002110(7)).

Cf. A002110, A073917.

forstep(n=1,1e8,510510,if(isprime(n),print1(n", "))) \\ Charles R Greathouse IV, May 31 2011

a(n) ~ 92160 n log n. [Charles R Greathouse IV, May 31 2011]

cp's OEIS Frontend

A073918 Smallest prime which is 1 more than a product of n distinct primes: a(n) is a prime and a(n) - 1 is a squarefree number with n prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A214089 Least prime p such that the first n primes divide p^2-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Extensions

A103783 Primes of the form primorial P(k)*n-1 with minimal n, n>0, k>=2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A272981 Least prime k>1 such that the sum of divisors of powers k^e, 1 <= e <= n, are divisible by the number their divisors, d(k^e).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A359262 a(n) is the largest number m such that prime(n)^m is in A359260.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A076689 Smallest k such that k*prime(n)# + 1 is prime where prime(n)# is the n-th primorial number A002110(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A167857 Numbers whose divisors are represented by an integer polynomial.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica