A373368 -id:A373368

Search: a373368 -id:a373368

Displaying 1-5 of 5 results found.

page 1

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.

+10
27

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

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

REFERENCES

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

LINKS

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.

FORMULA

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

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 *)

PROG

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

CROSSREFS

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#).

KEYWORD

nonn

AUTHOR

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

EXTENSIONS

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

STATUS

approved

A373377

a(n) = gcd(A059975(n), A083345(n)), 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.

+10
6

0, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 4, 1, 1, 2, 2, 1, 1, 1, 6, 2, 1, 1, 1, 2, 1, 1, 8, 1, 1, 1, 5, 2, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 12, 1, 1, 1, 1, 2, 9, 2, 14, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 18, 2, 1, 1, 1, 1, 1, 1, 20, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 24, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,8

COMMENTS

For each n >= 2, a(n) is a divisor of A373378(n).

LINKS

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

PROG

(PARI)

A059975(n) = { my(f = factor(n)); sum(i = 1, #f~, f[i, 2]*(f[i, 1] - 1)); };

A083345(n) = { my(f=factor(n)); numerator(vecsum(vector(#f~, i, f[i, 2]/f[i, 1]))); };

A373377(n) = gcd(A059975(n), A083345(n));

CROSSREFS

Cf. A059975, A083345.

Cf. A369002 (positions of even terms), A369003 (of odd terms).

Cf. also A373363, A373368, A373369, A373378.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jun 05 2024

STATUS

approved

A373378

a(n) = gcd(A003415(n), A059975(n)), where A003415 is the arithmetic derivative and A059975 is fully additive with a(p) = p-1.

+10
4

0, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 4, 1, 1, 2, 4, 1, 1, 1, 6, 2, 1, 1, 1, 2, 1, 3, 8, 1, 1, 1, 5, 2, 1, 2, 6, 1, 1, 2, 1, 1, 1, 1, 12, 1, 1, 1, 2, 2, 9, 2, 14, 1, 1, 2, 1, 2, 1, 1, 4, 1, 1, 1, 6, 2, 1, 1, 18, 2, 1, 1, 1, 1, 1, 5, 20, 2, 1, 1, 8, 4, 1, 1, 2, 2, 1, 2, 1, 1, 3, 2, 24, 2, 1, 2, 1, 1, 1, 1, 10, 1, 1, 1, 1, 1

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

LINKS

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

FORMULA

For n >= 1, a(n) is a multiple of A373377(n).

PROG

(PARI)

A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));

A059975(n) = {my(f = factor(n)); sum(i = 1, #f~, f[i, 2]*(f[i, 1] - 1)); };

A373378(n) = gcd(A003415(n), A059975(n));

CROSSREFS

Cf. A003415, A059975.

Cf. A368998 (positions of even terms), A368999 (of odd terms).

Cf. also A373364, A373368, A373369, A373377.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jun 05 2024

STATUS

approved

A373383

a(n) = 1 if n and A059975(n) are both multiples of 3, otherwise 0, where A059975 is fully additive with a(p) = p-1.

+10
3

0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0

(list; graph; refs; listen; history; text; internal format)

OFFSET

COMMENTS

Question: What is the asymptotic mean of this sequence?

LINKS

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

Index entries for characteristic functions

FORMULA

a(n) = [A373368(n) == 0 (mod 3)], where [ ] is the Iverson bracket.

PROG

(PARI)

A059975(n) = {my(f = factor(n)); sum(i = 1, #f~, f[i, 2]*(f[i, 1] - 1)); };

A373383(n) = !(gcd(n, A059975(n))%3);

CROSSREFS

Characteristic function of A373384.

Cf. A059975, A373368.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jun 06 2024

STATUS

approved

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.

+10
3

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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

LINKS

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

EXAMPLE

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.

PROG

(PARI) isA373384 = A373383;

CROSSREFS

Positions of multiples of 3 in A373368.

Cf. A059975, A373383 (characteristic function).

Intersection of A008585 and A373385.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jun 06 2024

STATUS

approved

page 1

Search completed in 0.006 seconds