cp's OEIS Frontend

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

%I A275969 #30 Aug 18 2016 19:44:30
%S A275969 3,5,13,17,51,85,193,257,769,1285,3281,4369,12289,21845,49601,65537,
%T A275969 196611,327685,786433,1114129,3158273,5570645,12648641,16843009,
%U A275969 50397953,84215045,202113281,286331153,805384193,1431655765,3221225473,8168859365,12952273921
%N A275969 Least k such that phi(k) has exactly n prime factors (counted with multiplicity).
%C A275969 Least k such that A001222(A000010(k)) = n.
%C A275969 If 2^2^n + 1 is a Fermat prime (A019434), then a(2^n) = 2^2^n + 1. - _Michael De Vlieger_, Aug 15 2016
%e A275969 a(2) = 5 because phi(5) = 4 has 2 prime factors (counted with multiplicity).
%t A275969 Table[k = 1; While[PrimeOmega@ EulerPhi@ k != n, k++]; k, {n, 16}] (* _Michael De Vlieger_, Aug 15 2016 *)
%o A275969 (PARI) a(n) = {my(k = 1); while(bigomega(eulerphi(k)) != n, k++); k; }
%o A275969 (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
%o A275969 (Perl) use v5.16; use ntheory ":all";
%o A275969 my($s,$chunk,$lp,@done) = (1,2e6,0);
%o A275969 while (1) {
%o A275969   my @npf = map { scalar(factor($_)) } euler_phi($s, $s+$chunk-1);
%o A275969   if (vecany { $_>$lp } @npf) {
%o A275969     while (my($idx,$val) = each @npf) {
%o A275969       $done[$val] //= $s+$idx  if $val > $lp;
%o A275969     }
%o A275969     while ($done[$lp+1]) { $lp++; say "$lp $done[$lp]"; }
%o A275969   }
%o A275969   $s += $chunk;
%o A275969 } # _Dana Jacobsen_, Aug 16 2016
%Y A275969 Cf. A000010, A001222, A019434, A073918.
%K A275969 nonn
%O A275969 1,1
%A A275969 _Altug Alkan_, Aug 15 2016
%E A275969 a(26)-a(33) from _Dana Jacobsen_, Aug 16 2016