login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #40 Oct 31 2023 15:29:49

%S 3,5,3,34,53,3646,103,1367,57,5905,419,28483073,5317,2087804,12015,

%T 11658487,28913,551011827257,379419,987922247,249661,3328294201,

%U 1914791,9437402089436849,38755369,271566862001,4971027,7897940252308,351453749,1824613261627468511874644,233798623

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

%C 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.

%H Robert Israel, <a href="/A366857/b366857.txt">Table of n, a(n) for n = 1..1049</a>

%F A001222(a(n)*n-1) = n.

%F a(n) >= (A053669(n)^n + 1) / n. - _David A. Corneth_, Oct 30 2023

%e a(4) = 34 because 4*34-1 = 135 = 3^3 * 5 has 4 prime factors, counted with multiplicity, and no smaller k works.

%p g:= proc(t,n) # first prime p == t mod n;

%p local p;

%p for p from t by n do if isprime(p) then return p fi od

%p end proc:

%p f:= proc(n) local m,t,p,P, T, Q, i, L, Lp,v,S; uses priqueue;

%p T:= select(i -> igcd(i, n)=1, [$1..n-1]);

%p P:= sort(map(g, T, n));

%p m:= nops(T);

%p initialize(Q); S:= {};

%p insert([-P[1]^n, [1$n]], Q);

%p do

%p t:= extract(Q);

%p if t[1] mod n = 1 then return (1-t[1])/n fi;

%p L:= t[2];

%p for i from 1 to n-1 do if L[i] < L[i+1] then

%p v:= t[1]*P[L[i]+1]/P[L[i]]; if member(v,S) then next fi;

%p S:= S union {v};

%p Lp:= subsop(i=L[i]+1, L); insert([v, Lp], Q)

%p fi od;

%p if L[n] < m then

%p v:= t[1]*P[L[n]+1]/P[L[n]];

%p if member(v,S) then next fi;

%p S:= S union {v};

%p Lp:= subsop(n=L[n]+1, L); insert([v, Lp], Q)

%p fi;

%p od;

%p end proc:

%p f(1):= 3:

%p map(f, [$1..40]);

%Y Cf. A001222, A053669.

%K nonn,look

%O 1,1

%A _Robert Israel_, Oct 30 2023

%E More terms from _David A. Corneth_, Oct 30 2023