login
A275969
Least k such that phi(k) has exactly n prime factors (counted with multiplicity).
2
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,1
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
EXAMPLE
a(2) = 5 because phi(5) = 4 has 2 prime factors (counted with multiplicity).
MATHEMATICA
Table[k = 1; While[PrimeOmega@ EulerPhi@ k != n, k++]; k, {n, 16}] (* Michael De Vlieger, Aug 15 2016 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Altug Alkan, Aug 15 2016
EXTENSIONS
a(26)-a(33) from Dana Jacobsen, Aug 16 2016
STATUS
approved