login
Number of distinct prime factors of 2^n-1.
36

%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