cp's OEIS Frontend

A059975 For n > 1, a(n) is the least number of prime factors (counted with multiplicity) of any integer with n divisors; fully additive with a(p) = p-1.

%I A059975 #76 Jun 10 2024 17:45:20
%S A059975 0,1,2,2,4,3,6,3,4,5,10,4,12,7,6,4,16,5,18,6,8,11,22,5,8,13,6,8,28,7,
%T A059975 30,5,12,17,10,6,36,19,14,7,40,9,42,12,8,23,46,6,12,9,18,14,52,7,14,9,
%U A059975 20,29,58,8,60,31,10,6,16,13,66,18,24,11,70,7,72,37,10,20,16,15,78,8,8,41
%N A059975 For n > 1, a(n) is the least number of prime factors (counted with multiplicity) of any integer with n divisors; fully additive with a(p) = p-1.
%C A059975 n*a(n) is the number of complex multiplications needed for the fast Fourier transform of n numbers, writing n = r1 * r2 where r1 is a prime.
%C A059975 This sequence with offset 1 and a(1) = 0 is completely additive with a(p^e) = e*(p-1) for prime p and e >= 0. - _Werner Schulte_, Feb 23 2019
%D A059975 Herbert S. Wilf, Algorithms and complexity, Internet Edition, Summer, 1994, p. 56.
%H A059975 Antti Karttunen, <a href="/A059975/b059975.txt">Table of n, a(n) for n = 1..16384</a> (terms 2..1000 from Vincenzo Librandi, terms 1001..10000 from Amiram Eldar)
%H A059975 K. V. Lever, <a href="http://www.jstor.org/stable/2031410">Problem 89-11: The complexity of the standard form of an integer</a>, SIAM Rev. 31 (3) (1989) 493-498.
%H A059975 Herbert S. Wilf, <a href="https://www.math.upenn.edu/~wilf/AlgComp3.html">Algorithms and complexity</a>, Internet Edition, 1994, p. 56.
%F A059975 a(n) = Sum ( e_i * (p_i - 1) ) where n = Product ( p_i^e_i ) is the canonical factorization of n.
%F A059975 a(n) = min(A001222(x) : A000005(x)=n).
%F A059975 a(n) = row sums of A138618 - row products of A138618. - _Mats Granvik_, May 23 2013
%F A059975 a(n) = A001414(n) - A001222(n). - _David James Sycamore_, Jul 17 2019
%F A059975 a(n) = n - A341865(n). - _Antti Karttunen_, Jun 05 2024
%e A059975 a(18) = 5 since 18 = 2*3^2, a(18) = 1*(2-1) + 2*(3-1) = 5.
%p A059975 A059975 := proc(n)
%p A059975         local a,pf,p,e ;
%p A059975         a := 0 ;
%p A059975         for pf in ifactors(n)[2] do
%p A059975                 p := op(1,pf) ;
%p A059975                 e := op(2,pf) ;
%p A059975                 a := a+e*(p-1) ;
%p A059975         end do:
%p A059975         a ;
%p A059975 end proc: # _R. J. Mathar_, Oct 17 2011
%t A059975 Table[Total[(First /@ FactorInteger[n] - 1) Last /@ FactorInteger[n]], {n, 1, 100}] (* _Danny Marmer_, Nov 13 2014 *)
%t A059975 f[p_, e_] := e*(p - 1); a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Mar 27 2023 *)
%o A059975 (PARI) a(n) = {my(f = factor(n)); sum(i = 1, #f~, f[i, 2]*(f[i, 1] - 1));} \\ _Amiram Eldar_, Mar 27 2023
%Y A059975 Essentially same as A087656 apart from offset.
%Y A059975 Cf. A000005, A138618, A309155, A309239, A327250, A341865, A373368 [= gcd(n, a(n))], A373369 [= gcd(A001414(n), a(n))].
%Y A059975 Cf. A003159 (positions of even terms), A096268 (with offset 1, parity of terms), A373385 (positions of multiples of 3).
%Y A059975 Leftmost column of irregular table A355029.
%Y A059975 Other completely additive sequences with primes p mapped to a function of p include: A001222 (with a(p)=1), A001414 (with a(p)=p), A276085 (with a(p)=p#/p), A341885 (with a(p)=p*(p+1)/2), A373149 (with a(p)=prevprime(p)), A373158 (with a(p)=p#).
%K A059975 nonn
%O A059975 1,3
%A A059975 Yong Kong (ykong(AT)curagen.com), Mar 05 2001
%E A059975 Definition revised by _Hugo van der Sanden_, May 21 2010
%E A059975 Term a(1)=0 prepended and _Werner Schulte_'s comment adopted as an alternative definition - _Antti Karttunen_, Jun 05 2024