A275969 Least k such that phi(k) has exactly n prime factors (counted with multiplicity).

3, 5, 13, 17, 51, 85, 193, 257, 769, 1285, 3281, 4369, 12289, 21845, 49601, 65537, 196611, 327685, 786433, 1114129, 3158273, 5570645, 12648641, 16843009, 50397953, 84215045, 202113281, 286331153, 805384193, 1431655765, 3221225473, 8168859365, 12952273921

Offset: 1

Author

Altug Alkan, Aug 15 2016

Keywords

• nonn

Comments

Least k such that A001222(A000010(k)) = n.

If 2^2^n + 1 is a Fermat prime (A019434), then a(2^n) = 2^2^n + 1. - Michael De Vlieger, Aug 15 2016

Examples

			a(2) = 5 because phi(5) = 4 has 2 prime factors (counted with multiplicity).
		

Crossrefs

Cf. A000010, A001222, A019434, A073918.

Programs

Mathematica

Table[k = 1; While[PrimeOmega@ EulerPhi@ k != n, k++]; k, {n, 16}] (* Michael De Vlieger, Aug 15 2016 *)

PARI

a(n) = {my(k = 1); while(bigomega(eulerphi(k)) != n, k++); k; }

Perl

use ntheory ":all"; sub a275969 { my($k,$n)=(1,shift); $k++ while scalar(factor(euler_phi($k))) != $n; $k; } # Dana Jacobsen, Aug 16 2016

Perl

use v5.16; use ntheory ":all";
my($s,$chunk,$lp,@done) = (1,2e6,0);
while (1) {
  my @npf = map { scalar(factor($_)) } euler_phi($s, $s+$chunk-1);
  if (vecany { $_>$lp } @npf) {
    while (my($idx,$val) = each @npf) {
      $done[$val] //= $s+$idx  if $val > $lp;
    }
    while ($done[$lp+1]) { $lp++; say "$lp $done[$lp]"; }
  }
  $s += $chunk;
} # Dana Jacobsen, Aug 16 2016

Extensions

a(26)-a(33) from Dana Jacobsen, Aug 16 2016