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

A289142 Numbers whose sum of prime factors (taken with multiplicity) is divisible by 3.

Original entry on oeis.org

1, 3, 8, 9, 14, 20, 24, 26, 27, 35, 38, 42, 44, 50, 60, 62, 64, 65, 68, 72, 74, 77, 78, 81, 86, 92, 95, 105, 110, 112, 114, 116, 119, 122, 125, 126, 132, 134, 143, 146, 150, 155, 158, 160, 161, 164, 170, 180, 185, 186, 188, 192, 194, 195, 196, 203, 204

Offset: 1

David James Sycamore, Jun 26 2017

nonn

U{S(n); 3|n}, where S(n)= {x; sopfr(x)=n}; numbers placed in ascending order.
A multiplicative semigroup: if m and n are in the sequence, then so is m*n. - Robert Israel, Jul 03 2017
From Antti Karttunen, Jun 11 2024, with minor edits Jun 30 2024: (Start)
Numbers such that the multiplicities of prime factors of the forms 3m+1 (A002476) and 3m-1 (A003627) are equal modulo 3.
For n that is not a multiple of 3, sopfr(n) [= A001414(n)] is a multiple of 3 if and only if the arithmetic derivative of n [= A003415(n)] is a multiple of 3. See A373475 for a proof.
This sequence (as a multiplicative semigroup) is generated by the union of A369659 with {3}.
(End)

			sopfr(42) = 2 + 3 + 7 = 12 = 4*3, sopfr(95) = 5 + 19 = 24 = 8 * 3, sopfr(180) = 2 + 2 + 3 + 3 + 5 = 15 = 5 * 3.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A002476, A003627, A036349, A036350, A046363, A373371 (characteristic function).
Positions of multiples of 3 in A001414 (sopfr) and in A118503.
Subsequences that are formed by intersecting this sequence with other multiplicative semigroups: A102217, A369659, A373373, A373473, A373475, A373478, A373597.
Cf. also A373385, A373602, A374052.

select(n -> add(t[1]*t[2],t=ifactors(n)[2]) mod 3 = 0, [$1..1000]); # Robert Israel, Jul 03 2017

Join[{1},Select[Range[250],Mod[Total[Times@@@FactorInteger[#]],3]==0&]] (* Harvey P. Dale, Mar 16 2020 *)

s(n)=my(f=factor(n),p=f[,1],e=f[,2]);sum(k=1,#p,e[k]*p[k]);
for(n=1,200,if(s(n)%3==0,print1(n,","))); \\ Joerg Arndt, Jun 26 2017

isA289142 = A373371; \\ Antti Karttunen, Jun 08 2024

For n >= 2, a(n) = A102217(n-1)/3. - Antti Karttunen, Jun 08 2024

Corrected by Robert Israel, Jul 03 2017

A373597 Non-multiples of 3 whose multiplicies of prime factors of types 3m-1 and 3m+1 are both multiples of 3.

Original entry on oeis.org

1, 8, 20, 44, 50, 64, 68, 92, 110, 116, 125, 160, 164, 170, 188, 212, 230, 236, 242, 275, 284, 290, 332, 343, 352, 356, 374, 400, 404, 410, 425, 428, 452, 470, 506, 512, 524, 530, 544, 548, 575, 578, 590, 596, 605, 637, 638, 668, 692, 710, 716, 725, 736, 764, 782, 788, 830, 880, 890, 902, 908, 928, 931, 932, 935

Offset: 1

Antti Karttunen, Jun 10 2024

nonn

A multiplicative semigroup: if m and n are in the sequence, then so is m*n. This is generated by semigroups A373589 and A373590.

			20 = 2*2*5 has 0 primes of type 3m+1 (A002476) and 3 primes of type 3m-1 (A003627) in its prime factorization, and as 0 and 3 are both multiples of 3, 20 is included as a term.
21952 = 2^6 * 7^3 is a term because there are 3 primes of type 3m+1 and 6 primes of type 3m-1, and as 6 and 3 are both multiples of 3, 21952 is included as a term.

Antti Karttunen, Table of n, a(n) for n = 1..20000

Cf. A002476, A003627, A373596 (characteristic function).
Subsequences: A373589 and A373590.
Subsequence of A001651, and of A145784.
Subsequence of the sequences A369659, A369644, A327863, A289142, A373385, and some of their intersections: A373473, A373475, A373478, A373492, A373494.
Differs from A373492 for the first time at n=91, where a(91) = 1325, which skips the value A373492(91) = 1323 present in A373492.
Cf. also A046337 (roughly analogous sequence for k=2, instead of k=3).

PARI
```
isA373597 = A373596;
```

A373494 Numbers k for which A059975(k) and A003415(k) are both multiples of 3, where A059975 is fully additive with a(p) = p-1, and A003415 is the arithmetic derivative.

Original entry on oeis.org

1, 8, 20, 27, 36, 44, 50, 64, 68, 90, 92, 110, 116, 125, 160, 162, 164, 170, 188, 189, 198, 212, 216, 225, 230, 236, 242, 252, 275, 284, 288, 290, 306, 332, 343, 351, 352, 356, 374, 400, 404, 405, 410, 414, 425, 428, 452, 468, 470, 495, 506, 512, 513, 522, 524, 530, 540, 544, 548, 575, 578, 590, 596, 605, 630, 637

Offset: 1

Antti Karttunen, Jun 10 2024

nonn

A multiplicative semigroup: if m and n are in the sequence, then so is m*n.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A003415, A059975, A373492 (subsequence), A373493 (characteristic function).
Positions of multiples of 3 in A373378.
Intersection of A373385 and A327863.

PARI
```
isA373494 = A373493;
```

A373473 Numbers k such that A001414(k) and A059975(k) are both multiples of 3, where A001414 and A059975 are fully additive with a(p) = p and a(p) = p-1, respectively.

Original entry on oeis.org

1, 8, 20, 27, 42, 44, 50, 64, 68, 78, 92, 105, 110, 114, 116, 125, 160, 164, 170, 186, 188, 195, 212, 216, 222, 230, 231, 236, 242, 258, 275, 284, 285, 290, 332, 336, 343, 352, 356, 357, 366, 374, 400, 402, 404, 410, 425, 428, 429, 438, 452, 465, 470, 474, 483, 506, 512, 524, 530, 540, 544, 548, 555, 575, 578, 582

Offset: 1

Antti Karttunen, Jun 06 2024

nonn

A multiplicative semigroup: if m and n are in the sequence, then so is m*n.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Intersection of A289142 and A373385.
Positions of multiples of 3 in A373369.
Cf. A001414, A059975.

PARI
```
isA373473 = A373472;
```

A373492 Numbers k for which A059975(k) and A083345(k) are both multiples of 3, where A059975 is fully additive with a(p) = p-1, and A083345 is the numerator of the fully additive function with a(p) = 1/p.

Original entry on oeis.org

1, 8, 20, 44, 50, 64, 68, 92, 110, 116, 125, 160, 164, 170, 188, 212, 230, 236, 242, 275, 284, 290, 332, 343, 352, 356, 374, 400, 404, 410, 425, 428, 452, 470, 506, 512, 524, 530, 544, 548, 575, 578, 590, 596, 605, 637, 638, 668, 692, 710, 716, 725, 736, 764, 782, 788, 830, 880, 890, 902, 908, 928, 931, 932, 935

Offset: 1

Antti Karttunen, Jun 10 2024

nonn

A multiplicative semigroup: if m and n are in the sequence, then so is m*n.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A059975, A083345, A373491 (characteristic function).
Positions of multiples of 3 in A373377.
Intersection of A373385 and A369644.
Subsequence of A373494.

PARI
```
isA373492 = A373491;
```

A373384 Numbers k that are multiples of 3 and also A059975(k) is a multiple of 3, where A059975 is fully additive with a(p) = p-1.

Original entry on oeis.org

6, 15, 27, 33, 36, 42, 48, 51, 69, 78, 87, 90, 105, 114, 120, 123, 141, 159, 162, 177, 186, 189, 195, 198, 213, 216, 222, 225, 231, 249, 252, 258, 264, 267, 285, 288, 294, 300, 303, 306, 321, 336, 339, 351, 357, 366, 384, 393, 402, 405, 408, 411, 414, 429, 438, 447, 465, 468, 474, 483, 495, 501, 513, 519, 522, 537

Offset: 1

Antti Karttunen, Jun 06 2024

nonn

A multiplicative semigroup: if m and n are in the sequence, then so is m*n.

			6 = 2*3 is present as A059975(6) = (2-1)+(3-1) = 1+2 = 3 is also a multiple of 3.
27 = 3*3*3 is present as A059975(27) = (3-1)+(3-1)+(3-1) = 2+2+2 = 6 is also a multiple of 3.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Positions of multiples of 3 in A373368.
Cf. A059975, A373383 (characteristic function).
Intersection of A008585 and A373385.

PARI
```
isA373384 = A373383;
```

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

A289142 Numbers whose sum of prime factors (taken with multiplicity) is divisible by 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A373597 Non-multiples of 3 whose multiplicies of prime factors of types 3m-1 and 3m+1 are both multiples of 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A373494 Numbers k for which A059975(k) and A003415(k) are both multiples of 3, where A059975 is fully additive with a(p) = p-1, and A003415 is the arithmetic derivative.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A373473 Numbers k such that A001414(k) and A059975(k) are both multiples of 3, where A001414 and A059975 are fully additive with a(p) = p and a(p) = p-1, respectively.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A373492 Numbers k for which A059975(k) and A083345(k) are both multiples of 3, where A059975 is fully additive with a(p) = p-1, and A083345 is the numerator of the fully additive function with a(p) = 1/p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A373384 Numbers k that are multiples of 3 and also A059975(k) is a multiple of 3, where A059975 is fully additive with a(p) = p-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI