A366857 a(n) is the least k such that n*k-1 has exactly n prime factors, counted with multiplicity.

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

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

Cf. A001222, A053669.

Sequence in context: A249012 A249908 A195418 * A065974 A096822 A195383

Adjacent sequences: A366854 A366855 A366856 * A366858 A366859 A366860

Keyword

nonn,look

Author

Robert Israel, Oct 30 2023

Extensions

More terms from David A. Corneth, Oct 30 2023

Status

approved