cp's OEIS Frontend

A051903 Maximum exponent in the prime factorization of n.

%I A051903 #124 Jul 08 2025 07:47:16
%S A051903 0,1,1,2,1,1,1,3,2,1,1,2,1,1,1,4,1,2,1,2,1,1,1,3,2,1,3,2,1,1,1,5,1,1,
%T A051903 1,2,1,1,1,3,1,1,1,2,2,1,1,4,2,2,1,2,1,3,1,3,1,1,1,2,1,1,2,6,1,1,1,2,
%U A051903 1,1,1,3,1,1,2,2,1,1,1,4,4,1,1,2,1,1,1,3,1,2,1,2,1,1,1,5,1,2,2,2,1,1,1,3,1
%N A051903 Maximum exponent in the prime factorization of n.
%C A051903 Smallest number of factors of all factorizations of n into squarefree numbers, see also A128651, A001055. - _Reinhard Zumkeller_, Mar 30 2007
%C A051903 Maximum number of invariant factors among abelian groups of order n. - _Álvar Ibeas_, Nov 01 2014
%C A051903 a(n) is the highest of the frequencies of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product(p_j-th prime, j=1..r) (concept used by _Alois P. Heinz_ in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(24) = 3; indeed, the partition having Heinz number 24 = 2*2*2*3 is [1,1,1,2], where the distinct parts 1 and 2 have frequencies 3 and 1, respectively. - _Emeric Deutsch_, Jun 04 2015
%C A051903 From _Thomas Ordowski_, Dec 02 2019: (Start)
%C A051903 a(n) is the smallest k such that b^(phi(n)+k) == b^k (mod n) for all b.
%C A051903 The Euler phi function can be replaced by the Carmichael lambda function.
%C A051903 Problems:
%C A051903 (*) Are there composite numbers n > 4 such that n == a(n) (mod phi(n))? By Lehmer's totient conjecture, there are no such squarefree numbers.
%C A051903 (**) Are there odd numbers n such that a(n) > 1 and n == a(n) (mod lambda(n))? These are odd numbers n such that a(n) > 1 and b^n == b^a(n) (mod n) for all b.
%C A051903 (***) Are there odd numbers n such that a(n) > 1 and n == a(n) (mod ord_{n}(2))? These are odd numbers n such that a(n) > 1 and 2^n == 2^a(n) (mod n).
%C A051903 Note: if (***) do not exist, then (**) do not exist. (End)
%C A051903 Niven (1969) proved that the asymptotic mean of this sequence is 1 + Sum_{j>=2} 1 - (1/zeta(j)) (A033150). - _Amiram Eldar_, Jul 10 2020
%H A051903 Daniel Forgues, <a href="/A051903/b051903.txt">Table of n, a(n) for n = 1..100000</a> (first 10000 terms from T. D. Noe)
%H A051903 Benjamin Merlin Bumpus and Zoltan A. Kocsis, <a href="https://arxiv.org/abs/2104.01841">Spined categories: generalizing tree-width beyond graphs</a>, arXiv:2104.01841 [math.CO], 2021.
%H A051903 Cao Hui-Zhong, <a href="http://www.math.bas.bg/infres/MathBalk/MB-05/MB-05-105-108.pdf">The Asymptotic Formulas Related to Exponents in Factoring Integers</a>, Math. Balkanica, Vol. 5 (1991), Fasc. 2.
%H A051903 Ivan Niven, <a href="https://doi.org/10.1090/S0002-9939-1969-0241373-5">Averages of Exponents in Factoring Integers</a>, Proc. Amer. Math. Soc., Vol. 22, No. 2 (1969), pp. 356-360.
%H A051903 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/NivensConstant.html">Niven's Constant</a>.
%H A051903 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A051903 a(n) = max_{k=1..A001221(n)} A124010(n,k). - _Reinhard Zumkeller_, Aug 27 2011
%F A051903 a(1) = 0; for n > 1, a(n) = max(A067029(n), a(A028234(n))). - _Antti Karttunen_, Aug 08 2016
%F A051903 Conjecture: a(n) = a(A003557(n)) + 1. This relation together with a(1) = 0 defines the sequence. - _Velin Yanev_, Sep 02 2017
%F A051903 Comment from _David J. Seal_, Sep 18 2017: (Start)
%F A051903 This conjecture seems very easily provable to me: if the factorization of n is p1^k1 * p2^k2 * ... * pm^km, then the factorization of the largest squarefree divisor of n is p1 * p2 * ... * pm. So the factorization of A003557(n) is p1^(k1-1) * p2^(k2-1) * ... * pm^(km-1) if exponents of zero are allowed, or with the product terms that have an exponent of zero removed if they're not (if that results in an empty product, consider it to be 1 as usual).
%F A051903 The formula then follows from the fact that provided all ki >= 1, Max(k1, k2, ..., km) = Max(k1-1, k2-1, ..., km-1) + 1, and Max(k1-1, k2-1, ..., km-1) is not altered by removing the ki-1 values that are 0, provided we treat the empty Max() as being 0. That proves the formula and the provisos about empty products and Max() correspond to a(1) = 0.
%F A051903 Also, for any n, applying the formula Max(k1, k2, ..., km) times to n = p1^k1 * p2^k2 * ... * pm^km reduces all the exponents to zero, i.e., to the case a(1) = 0, so that case and the formula generate the sequence. (End)
%F A051903 Sum_{k=1..n} (-1)^k * a(k) ~ c * n, where c = Sum_{k>=2} 1/((2^k-1)*zeta(k)) = 0.44541445377638761933... . - _Amiram Eldar_, Jul 28 2024
%F A051903 a(n) <= log(n)/log(2). - _Hal M. Switkay_, Jul 03 2025
%e A051903 For n = 72 = 2^3*3^2, a(72) = max(exponents) = max(3,2) = 3.
%p A051903 A051903 := proc(n)
%p A051903         a := 0 ;
%p A051903         for f in ifactors(n)[2] do
%p A051903                 a := max(a,op(2,f)) ;
%p A051903         end do:
%p A051903         a ;
%p A051903 end proc: # _R. J. Mathar_, Apr 03 2012
%p A051903 # second Maple program:
%p A051903 a:= n-> max(0, seq(i[2], i=ifactors(n)[2])):
%p A051903 seq(a(n), n=1..120);  # _Alois P. Heinz_, May 09 2020
%t A051903 Table[If[n == 1, 0, Max @@ Last /@ FactorInteger[n]], {n, 100}] (* _Ray Chandler_, Jan 24 2006 *)
%o A051903 (Haskell)
%o A051903 a051903 1 = 0
%o A051903 a051903 n = maximum $ a124010_row n -- _Reinhard Zumkeller_, May 27 2012
%o A051903 (PARI) a(n)=if(n>1,vecmax(factor(n)[,2]),0) \\ _Charles R Greathouse IV_, Oct 30 2012
%o A051903 (Python)
%o A051903 from sympy import factorint
%o A051903 def A051903(n):
%o A051903     return max(factorint(n).values()) if n > 1 else 0
%o A051903 # _Chai Wah Wu_, Jan 03 2015
%o A051903 (Scheme)
%o A051903 ;; With memoization-macro definec.
%o A051903 (definec (A051903 n) (if (= 1 n) 0 (max (A067029 n) (A051903 (A028234 n))))) ;; _Antti Karttunen_, Aug 08 2016
%Y A051903 Average value is A033150 = 1.7052....
%Y A051903 Cf. A002322, A005361, A008479, A028234, A051904, A052409, A067029, A091050, A129132, A327295, A328310, A329885.
%K A051903 nonn,easy
%O A051903 1,4
%A A051903 _Labos Elemer_, Dec 16 1999