A340799 a(n) is the smallest prime p such that p + 1 has 2n divisors.

2, 5, 11, 23, 47, 59, 191, 167, 179, 239, 5119, 359, 20479, 2111, 719, 839, 1114111, 1259, 786431, 3023, 2879, 15359, 348127231, 3359, 22031, 266239, 6299, 6719, 22280142847, 5039, 559419490303, 7559, 156671, 7798783, 25919, 10079, 1168231104511, 5505023

Offset: 1

Author

Jaroslav Krizek, Jan 21 2021

Keywords

• nonn
• look

Comments

The only prime p such that p+1 has an odd number of divisors is 3, because every number with an odd number of divisors is a square. - Robert Israel, Jan 12 2025

Examples

			a(4) = 23 because 23 is the smallest prime p such that p + 1 has 2*4 divisors; tau(24) = 8.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..255

Crossrefs

Cf. A000005 (tau), A003680, A080371.

Programs

Magma

Ax:=func; [Ax(n): n in[1..20]];

Maple

g:= proc(n,k) # lists of integers > k whose product is n
      option remember;
      local F,m;
      if n = 1 then return [[]]
      elif k >= n then return []
      fi;
      F:= select(`>`,numtheory:-divisors(n),k);
      [seq(op(map(t -> [m,op(t)], procname(n/m,m-1))), m=F)]
end proc:
children:= proc(t) local m,nt,S,i,qs,t3s,t1s;
    nt:= nops(t[3]);
    S:= select(i -> t[3][i] <> 2, [$1..nt]);
    if S = [] then m:= nt else m:= min(S) fi;
    qs:= [seq(nextprime(t[3][i]),i=1..m)];
    t3s:= [seq(subsop(i = qs[i], t[3]), i = 1..m)];
    t1s:= [seq(t[1]*(qs[i]/t[3][i])^t[2][i], i=1..m)];
    [seq([t1s[i],t[2],t3s[i]],i=1..m)]
end proc:
f:= proc(d) local pq,s,t,i; uses priqueue;
  initialize(pq);
  for t in g(2*d,1) do insert([-mul(2^(t[i]-1),i=1..nops(t)),t -~ 1, [2$nops(t)]],pq) od;
  do
     t:= extract(pq);
     if nops(convert(t[3],set)) = nops(t[3]) and isprime(-t[1]-1) then return -t[1]-1 fi;
  for s in children(t) do insert(s,pq) od
  od:
end proc:
map(f, [$1..40]); # Robert Israel, Jan 12 2025

Formula

A000005(a(n) + 1) = 2n.