A341865 -id:A341865 - 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.

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, 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, 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

Offset: 1

Yong Kong (ykong(AT)curagen.com), Mar 05 2001

nonn

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.

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

			a(18) = 5 since 18 = 2*3^2, a(18) = 1*(2-1) + 2*(3-1) = 5.

Herbert S. Wilf, Algorithms and complexity, Internet Edition, Summer, 1994, p. 56.

Antti Karttunen, Table of n, a(n) for n = 1..16384 (terms 2..1000 from Vincenzo Librandi, terms 1001..10000 from Amiram Eldar)
K. V. Lever, Problem 89-11: The complexity of the standard form of an integer, SIAM Rev. 31 (3) (1989) 493-498.
Herbert S. Wilf, Algorithms and complexity, Internet Edition, 1994, p. 56.

Essentially same as A087656 apart from offset.
Cf. A000005, A138618, A309155, A309239, A327250, A341865, A373368 [= gcd(n, a(n))], A373369 [= gcd(A001414(n), a(n))].
Cf. A003159 (positions of even terms), A096268 (with offset 1, parity of terms), A373385 (positions of multiples of 3).
Leftmost column of irregular table A355029.
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#).

A059975 := proc(n)
        local a,pf,p,e ;
        a := 0 ;
        for pf in ifactors(n)[2] do
                p := op(1,pf) ;
                e := op(2,pf) ;
                a := a+e*(p-1) ;
        end do:
        a ;
end proc: # R. J. Mathar, Oct 17 2011

Table[Total[(First /@ FactorInteger[n] - 1) Last /@ FactorInteger[n]], {n, 1, 100}] (* Danny Marmer, Nov 13 2014 *)
f[p_, e_] := e*(p - 1); a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Mar 27 2023 *)

a(n) = {my(f = factor(n)); sum(i = 1, #f~, f[i, 2]*(f[i, 1] - 1));} \\ Amiram Eldar, Mar 27 2023

a(n) = Sum ( e_i * (p_i - 1) ) where n = Product ( p_i^e_i ) is the canonical factorization of n.
a(n) = min(A001222(x) : A000005(x)=n).
a(n) = row sums of A138618 - row products of A138618. - Mats Granvik, May 23 2013
a(n) = A001414(n) - A001222(n). - David James Sycamore, Jul 17 2019
a(n) = n - A341865(n). - Antti Karttunen, Jun 05 2024

Definition revised by Hugo van der Sanden, May 21 2010

Term a(1)=0 prepended and Werner Schulte's comment adopted as an alternative definition - Antti Karttunen, Jun 05 2024

A341866 The cardinality of the smallest (nontrivial, except for prime n) multiset of positive integers whose product and sum equal n.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 5, 5, 1, 6, 1, 7, 9, 8, 1, 9, 1, 10, 13, 11, 1, 12, 17, 13, 17, 14, 1, 15, 1, 16, 21, 17, 25, 18, 1, 19, 25, 20, 1, 21, 1, 22, 29, 23, 1, 24, 37, 25, 33, 26, 1, 27, 41, 28, 37, 29, 1, 30, 1, 31, 41, 32

Offset: 1

Nathaniel Gregg, Feb 22 2021

nonn

The smallest set is obtained by taking the largest such multiset (A341865(n)) and replacing the largest proper subset that is also a product-sum multiset with its product. A singleton would always be the smallest product-sum multiset, so those are excluded except for prime n where no nontrivial multisets exist.

			For n = 12, the set of size a(n) = 6 is {1,1,1,1,2,6}.

Cf. A104173, A033178, A033179, A341865.

Equals A330492 + 1. - Hugo Pfoertner, Feb 23 2021

a(n) = if (n==1, 1, my(p=vecmin(factor(n)[,1])); (n/p-1)*(p-1) + 1); \\ Michel Marcus, Feb 26 2021

a(n) = (n/p - 1)*(p-1) + 1, where p is the smallest factor of n.

a(n) = A341865(n) - A341865(n/p) + 1, where p is the smallest prime factor of n.

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions