OFFSET
1,1
COMMENTS
If q is a prime that doesn't divide n, Dirichlet's theorem on primes in arithmetic progressions implies there are infinitely many k such that (k*n - 1)/q^(n-1) is a prime.
LINKS
Robert Israel, Table of n, a(n) for n = 1..1049
FORMULA
A001222(a(n)*n-1) = n.
a(n) >= (A053669(n)^n + 1) / n. - David A. Corneth, Oct 30 2023
EXAMPLE
a(4) = 34 because 4*34-1 = 135 = 3^3 * 5 has 4 prime factors, counted with multiplicity, and no smaller k works.
MAPLE
g:= proc(t, n) # first prime p == t mod n;
local p;
for p from t by n do if isprime(p) then return p fi od
end proc:
f:= proc(n) local m, t, p, P, T, Q, i, L, Lp, v, S; uses priqueue;
T:= select(i -> igcd(i, n)=1, [$1..n-1]);
P:= sort(map(g, T, n));
m:= nops(T);
initialize(Q); S:= {};
insert([-P[1]^n, [1$n]], Q);
do
t:= extract(Q);
if t[1] mod n = 1 then return (1-t[1])/n fi;
L:= t[2];
for i from 1 to n-1 do if L[i] < L[i+1] then
v:= t[1]*P[L[i]+1]/P[L[i]]; if member(v, S) then next fi;
S:= S union {v};
Lp:= subsop(i=L[i]+1, L); insert([v, Lp], Q)
fi od;
if L[n] < m then
v:= t[1]*P[L[n]+1]/P[L[n]];
if member(v, S) then next fi;
S:= S union {v};
Lp:= subsop(n=L[n]+1, L); insert([v, Lp], Q)
fi;
od;
end proc:
f(1):= 3:
map(f, [$1..40]);
CROSSREFS
KEYWORD
nonn,look
AUTHOR
Robert Israel, Oct 30 2023
EXTENSIONS
More terms from David A. Corneth, Oct 30 2023
STATUS
approved