A138618 -id:A138618 - 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

A140256 Triangle read by columns: Column k is A014963 aerated with groups of (k-1) zeros.

Original entry on oeis.org

1, 2, 1, 3, 0, 1, 2, 2, 0, 1, 5, 0, 0, 0, 1, 1, 3, 2, 0, 0, 1, 7, 0, 0, 0, 0, 0, 1, 2, 2, 0, 2, 0, 0, 0, 1, 3, 0, 3, 0, 0, 0, 0, 0, 1, 1, 5, 0, 0, 2, 0, 0, 0, 0, 1, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 0, 2, 0, 0, 0, 0, 0, 1, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 7, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Gary W. Adamson and Mats Granvik, May 16 2008, Jun 11 2008

If the row number n is prime, the row consists of T(n,1)=n followed by n-2 zeros and followed by T(n,n)=1.
Similar to A138618.
Row products of nonzero terms in row n, equals n. - Mats Granvik, May 22 2016

			First few rows of the triangle are:
   1;
   2, 1;
   3, 0, 1;
   2, 2, 0, 1;
   5, 0, 0, 0, 1;
   1, 3, 2, 0, 0, 1;
   7, 0, 0, 0, 0, 0, 1;
   2, 2, 0, 2, 0, 0, 0, 1;
   3, 0, 3, 0, 0, 0, 0, 0, 1;
   1, 5, 0, 0, 2, 0, 0, 0, 0, 1;
  11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
   1, 1, 2, 3, 0, 2, 0, 0, 0, 0, 0, 1;
  ...
Column 2 = (1, 0, 2, 0, 3, 0, 2, 0, 5, 0, 1, 0, 7, ...).

T. Tao, Simons Lecture I: Structure and randomness in Fourier analysis and number theory.
Wikipedia, Fundamental theorem of arithmetic.

Cf. A140255 (row sums), A014963.

Row products without the zero terms produce A000027. [Mats Granvik, Oct 08 2009]

=if(row()>=column();if(mod(row();column())=0;lookup(roundup(row()/column();0);A000027;A014963);0);"")

t[n_, k_] /; Divisible[n, k] := Exp[ MangoldtLambda[n/k] ]; t[, ] = 0; Table[t[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 28 2013 *)
(* recurrence *)
Clear[t, s, n, k, z, nn];z = 1;nn = 14;t[n_, k_] := t[n, k] = If[k == 1, Zeta[s]*(1 - 1/n^(s - 1)) -Sum[t[n, i]/i^(s - 1), {i, 2, n}], If[Mod[n, k] == 0, t[n/k, 1], 0], 0]; A = Table[Table[Limit[t[n, k], s -> z], {k, 1, n}], {n, 1, nn}]; Flatten[Exp[A]*Table[Table[If[Mod[n, k] == 0, 1, 0], {k, 1, n}], {n, 1, nn}]] (* Mats Granvik, Apr 09 2016, May 22 2016 *)

T(n,k) = A014963(n/k) = A014963(A126988(n,k)) if k|n, T(n,k)=0 otherwise. 1 <= k <= n.
From Mats Granvik, Apr 10 2016, May 22 2016: (Start)
Limit as s -> 1 of the recurrence: Ts(n, k) = if k = 1 then zeta(s)*(1 - 1/n^(s - 1)) -Sum_{i=2..n} Ts(n, i)/(i)^(s - 1) else if n mod k = 0 then Ts(n/k, 1) else 0 else 0.
For n not equal to k: Limit as s -> 1 of the recurrence: Ts(n, k) = if k = 1 then zeta(s) -Sum_{i=2..n} Ts(n, i)/i^(s - 1) else if n mod k = 0 then Ts(n/k, 1) else 0 else 0.
Limit as s -> 1 of the recurrence: Ts(n, k) = if k = 1 then log(n) -Sum_{i=2..n} Ts(n, i)/i^(s - 1) else if n mod k = 0 then Ts(n/k, 1) else 0 else 0. (End)
[The above sentences need a lot of work!  Parentheses might help. - N. J. A. Sloane, Mar 14 2017]

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