cp's OEIS Frontend

A046800 Number of distinct prime factors of 2^n-1.

%I A046800 #36 Jun 02 2021 17:28:38
%S A046800 0,0,1,1,2,1,2,1,3,2,3,2,4,1,3,3,4,1,4,1,5,3,4,2,6,3,3,3,6,3,6,1,5,4,
%T A046800 3,4,8,2,3,4,7,2,6,3,7,6,4,3,9,2,7,5,7,3,6,6,8,4,6,2,11,1,3,6,7,3,8,2,
%U A046800 7,4,9,3,12,3,5,7,7,4,7,3,9,6,5,2,12,3,5,6,10,1,11,5,9,3,6,5,12,2,5,8,12,2
%N A046800 Number of distinct prime factors of 2^n-1.
%H A046800 Amiram Eldar, <a href="/A046800/b046800.txt">Table of n, a(n) for n = 0..1206</a> (terms 1..500 from T. D. Noe)
%H A046800 J. Brillhart et al., <a href="http://dx.doi.org/10.1090/conm/022">Factorizations of b^n +- 1</a>. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
%H A046800 Abílio Lemos and Ady Cambraia Junior, <a href="https://arxiv.org/abs/1606.08690">On the number of prime factors of Mersenne numbers</a> (2016)
%F A046800 a(n) = Sum_{d|n} A086251(d), Mobius transform of A086251.
%F A046800 a(n) < 0.7 * n; the constant 0.7 cannot be improved below log 2 using only the size of 2^n-1. - _Charles R Greathouse IV_, Apr 12 2012
%F A046800 a(n) = A001221(2^n-1). - _R. J. Mathar_, Nov 10 2017
%e A046800 a(6) = 2 because 63 = 3*3*7 has 2 distinct prime factors.
%p A046800 A046800 := proc(n)
%p A046800     if n <= 1 then
%p A046800         0;
%p A046800     else
%p A046800         numtheory[factorset](2^n-1) ;
%p A046800         nops(%) ;
%p A046800     end if;
%p A046800 end proc:
%p A046800 seq(A046800(n),n=0..100) ; # _R. J. Mathar_, Nov 10 2017
%t A046800 Table[Length[ FactorInteger [ 2^n -1 ] ], {n, 0, 100}]
%t A046800 Join[{0},PrimeNu/@(2^Range[110]-1)] (* _Harvey P. Dale_, Mar 09 2015 *)
%o A046800 (PARI) a(n)=omega(2^n-1) \\ _Charles R Greathouse IV_, Nov 17 2014
%Y A046800 Length of row n of A060443.
%Y A046800 Cf. A000225, A046051 (number of prime factors, with repetition, of 2^n-1), A086251.
%K A046800 nonn
%O A046800 0,5
%A A046800 _Labos Elemer_
%E A046800 Edited by _T. D. Noe_, Jul 14 2003