login
A366857
a(n) is the least k such that n*k-1 has exactly n prime factors, counted with multiplicity.
1
3, 5, 3, 34, 53, 3646, 103, 1367, 57, 5905, 419, 28483073, 5317, 2087804, 12015, 11658487, 28913, 551011827257, 379419, 987922247, 249661, 3328294201, 1914791, 9437402089436849, 38755369, 271566862001, 4971027, 7897940252308, 351453749, 1824613261627468511874644, 233798623
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
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
Sequence in context: A249012 A249908 A195418 * A065974 A096822 A195383
KEYWORD
nonn,look
AUTHOR
Robert Israel, Oct 30 2023
EXTENSIONS
More terms from David A. Corneth, Oct 30 2023
STATUS
approved