|
%I #36 Jun 02 2021 17:28:38
%S 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 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 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 Number of distinct prime factors of 2^n-1.
%H 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 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 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 a(n) = Sum_{d|n} A086251(d), Mobius transform of A086251.
%F 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 a(n) = A001221(2^n-1). - _R. J. Mathar_, Nov 10 2017
%e a(6) = 2 because 63 = 3*3*7 has 2 distinct prime factors.
%p A046800 := proc(n)
%p if n <= 1 then
%p 0;
%p else
%p numtheory[factorset](2^n-1) ;
%p nops(%) ;
%p end if;
%p end proc:
%p seq(A046800(n),n=0..100) ; # _R. J. Mathar_, Nov 10 2017
%t Table[Length[ FactorInteger [ 2^n -1 ] ], {n, 0, 100}]
%t Join[{0},PrimeNu/@(2^Range[110]-1)] (* _Harvey P. Dale_, Mar 09 2015 *)
%o (PARI) a(n)=omega(2^n-1) \\ _Charles R Greathouse IV_, Nov 17 2014
%Y Length of row n of A060443.
%Y Cf. A000225, A046051 (number of prime factors, with repetition, of 2^n-1), A086251.
%K nonn
%O 0,5
%A _Labos Elemer_
%E Edited by _T. D. Noe_, Jul 14 2003
|
