A097945 -id:A097945 - cp's OEIS frontend

A349356 Dirichlet convolution of A003959 with A097945 (Dirichlet inverse of A003958), where A003958 and A003959 are fully multiplicative with a(p) = p-1 and p+1 respectively.

1, 2, 2, 6, 2, 4, 2, 18, 8, 4, 2, 12, 2, 4, 4, 54, 2, 16, 2, 12, 4, 4, 2, 36, 12, 4, 32, 12, 2, 8, 2, 162, 4, 4, 4, 48, 2, 4, 4, 36, 2, 8, 2, 12, 16, 4, 2, 108, 16, 24, 4, 12, 2, 64, 4, 36, 4, 4, 2, 24, 2, 4, 16, 486, 4, 8, 2, 12, 4, 8, 2, 144, 2, 4, 24, 12, 4, 8, 2, 108, 128, 4, 2, 24, 4, 4, 4, 36, 2, 32, 4, 12, 4

Offset: 1

Antti Karttunen, Nov 16 2021

In Dirichlet ring this sequence works as a kind of replacement operator which replaces the factor A003958 with factor A003959. For example, convolving this with A349133 produces A349173.

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

Cf. A003958, A003959, A097945, A349355 (Dirichlet inverse), A349357 (sum with it).

Cf. also A349133, A349173, A349381.

f[p_, e_] := 2*(p + 1)^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 16 2021 *)

A003959(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1]++); factorback(f); };
A097945(n) = (moebius(n)*eulerphi(n)); \\ Also Dirichlet inverse of A003958.
A349356(n) = sumdiv(n,d,A003959(n/d)*A097945(d));

a(n) = Sum_{d|n} A003959(n/d) * A097945(d).

Multiplicative with a(p^e) = 2*(p+1)^(e-1). - Amiram Eldar, Nov 16 2021

A007947 Largest squarefree number dividing n: the squarefree kernel of n, rad(n), radical of n.

Original entry on oeis.org

1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 29, 30, 31, 2, 33, 34, 35, 6, 37, 38, 39, 10, 41, 42, 43, 22, 15, 46, 47, 6, 7, 10, 51, 26, 53, 6, 55, 14, 57, 58, 59, 30, 61, 62, 21, 2, 65, 66, 67, 34, 69, 70, 71, 6, 73, 74, 15, 38, 77, 78

Offset: 1

R. Muller, Mar 15 1996

Multiplicative with a(p^e) = p.
Product of the distinct prime factors of n.
a(k)=k for k=squarefree numbers A005117. - Lekraj Beedassy, Sep 05 2006
A note on square roots of numbers: we can write sqrt(n) = b*sqrt(c) where c is squarefree. Then b = A000188(n) is the "inner square root" of n, c = A007913(n), b*c = A019554(n) = "outer square root" of n, and a(n) = lcm(a(b),c). Unless n is biquadrateful (A046101), a(n) = lcm(b,c). [Edited by Jeppe Stig Nielsen, Oct 10 2021, and Andrey Zabolotskiy, Feb 12 2025]
a(n) = A128651(A129132(n-1) + 2) for n > 1. - Reinhard Zumkeller, Mar 30 2007
Also the least common multiple of the prime factors of n. - Peter Luschny, Mar 22 2011
The Mobius transform of the sequence generates the sequence of absolute values of A097945. - R. J. Mathar, Apr 04 2011
Appears to be the period length of k^n mod n. For example, n^12 mod 12 has period 6, repeating 1,4,9,4,1,0, so a(12)= 6. - Gary Detlefs, Apr 14 2013
a(n) differs from A014963(n) when n is a term of A024619. - Eric Desbiaux, Mar 24 2014
a(n) is also the smallest base (also termed radix) for which the representation of 1/n is of finite length.  For example a(12) = 6 and 1/12 in base 6 is 0.03, which is of finite length. - Lee A. Newberg, Jul 27 2016
a(n) is also the divisor k of n such that d(k) = 2^omega(n). a(n) is also the smallest divisor u of n such that n divides u^n. - Juri-Stepan Gerasimov, Apr 06 2017

			G.f. = x + 2*x^2 + 3*x^3 + 2*x^4 + 5*x^5 + 6*x^6 + 7*x^7 + 2*x^8 + 3*x^9 + ... - _Michael Somos_, Jul 15 2018

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from T. D. Noe)
Masum Billal, Divisible Sequence and its Characteristic Sequence, arXiv:1501.00609 [math.NT], 2015, theorem 11 page 5.
Henry Bottomley, Some Smarandache-type multiplicative sequences
Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
Jarosław Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
Neville Holmes, Integer Sequences [Broken link]
Serge Lang, Old and New Conjectured Diophantine Inequalities, Bull. Amer. Math. Soc., 23 (1990), 37-75. see p. 39.
Wolfdieter Lang, Cantor's List of Real Algebraic Numbers of Heights 1 to 7, arXiv:2307.10645 [math.NT], 2023.
D. H. Lehmer, Euler constants for arithmetical progressions, Collection of articles in memory of Juriĭ Vladimirovič Linnik. Acta Arith. 27 (1975), 125--142. MR0369233 (51 #5468). See N_k on page 131.
Ivar Peterson, The Amazing ABC Conjecture
Paul Tarau, Emulating Primality with Multiset Representations of Natural Numbers, in Theoretical Aspects of Computing, ICTAC 2011, Lecture Notes in Computer Science, 2011, Volume 6916/2011, 218-238
Paul Tarau, Towards a generic view of primality through multiset decompositions of natural numbers, Theoretical Computer Science, Volume 537, 5 June 2014, Pages 105-124.
Wikipedia, Radical of an integer.

See A007913, A062953, A000188, A019554, A003557, A066503, A087207 for other properties related to square and squarefree divisors of n.
More general factorization-related properties, specific to n: A020639, A028234, A020500, A010051, A284318, A000005, A001221, A005361, A034444, A014963, A128651, A267116.
Range of values is A005117.
Cf. A048803, A019565, A024619, A053462, A060735, A073355 (partial sums), A079277, A097945, A129132, A225546.
Bisections: A099984, A099985.
Sequences about numbers that have the same squarefree kernel: A065642, array A284311 (A284457).
A003961, A059896 are used to express relationship between terms of this sequence.
Cf. A001615, A008683, A076479, A078615.

a007947 = product . a027748_row  -- Reinhard Zumkeller, Feb 27 2012

[ &*PrimeDivisors(n): n in [1..100] ]; // Klaus Brockhaus, Dec 04 2008

with(numtheory); A007947 := proc(n) local i,t1,t2; t1 := ifactors(n)[2]; t2 := mul(t1[i][1],i=1..nops(t1)); end;
A007947 := n -> ilcm(op(numtheory[factorset](n))):
seq(A007947(i),i=1..69); # Peter Luschny, Mar 22 2011
A:= n -> convert(numtheory:-factorset(n),`*`):
seq(A(n),n=1..100); # Robert Israel, Aug 10 2014
seq(NumberTheory:-Radical(n), n = 1..78); # Peter Luschny, Jul 20 2021

rad[n_] := Times @@ (First@# & /@ FactorInteger@ n); Array[rad, 78] (* Robert G. Wilson v, Aug 29 2012 *)
Table[Last[Select[Divisors[n],SquareFreeQ]],{n,100}] (* Harvey P. Dale, Jul 14 2014 *)
a[ n_] := If[ n < 1, 0, Sum[ EulerPhi[d] Abs @ MoebiusMu[d], {d, Divisors[ n]}]]; (* Michael Somos, Jul 15 2018 *)
Table[Product[p, {p, Select[Divisors[n], PrimeQ]}], {n, 1, 100}] (* Vaclav Kotesovec, May 20 2020 *)

a(n) = factorback(factorint(n)[,1]); \\ Andrew Lelechenko, May 09 2014

for(n=1, 100, print1(direuler(p=2, n, (1 + p*X - X)/(1 - X))[n], ", ")) \\ Vaclav Kotesovec, Jun 14 2020

from sympy import primefactors, prod
def a(n): return 1 if n < 2 else prod(primefactors(n))
[a(n) for n in range(1, 51)]  # Indranil Ghosh, Apr 16 2017

def A007947(n): return mul(p for p in prime_divisors(n))
[A007947(n) for n in (1..60)] # Peter Luschny, Mar 07 2017

(define (A007947 n) (if (= 1 n) n (* (A020639 n) (A007947 (A028234 n))))) ;; ;; Needs also code from A020639 and A028234. - Antti Karttunen, Jun 18 2017

If n = Product_j (p_j^k_j) where p_j are distinct primes, then a(n) = Product_j (p_j).
a(n) = Product_{k=1..A001221(n)} A027748(n,k). - Reinhard Zumkeller, Aug 27 2011
Dirichlet g.f.: zeta(s)*Product_{primes p} (1+p^(1-s)-p^(-s)). - R. J. Mathar, Jan 21 2012
a(n) = Sum_{d|n} phi(d) * mu(d)^2 = Sum_{d|n} |A097945(d)|. - Enrique Pérez Herrero, Apr 23 2012
a(n) = Product_{d|n} d^moebius(n/d) (see Billal link). - Michel Marcus, Jan 06 2015
a(n) = n/( Sum_{k=1..n} (floor(k^n/n)-floor((k^n - 1)/n)) ) = e^(Sum_{k=2..n} (floor(n/k) - floor((n-1)/k))*A010051(k)*M(k)) where M(n) is the Mangoldt function. - Anthony Browne, Jun 17 2016
a(n) = n/A003557(n). - Juri-Stepan Gerasimov, Apr 07 2017
G.f.: Sum_{k>=1} phi(k)*mu(k)^2*x^k/(1 - x^k). - Ilya Gutkovskiy, Apr 11 2017
From Antti Karttunen, Jun 18 2017: (Start)
a(1) = 1; for n > 1, a(n) = A020639(n) * a(A028234(n)).
a(n) = A019565(A087207(n)). (End)
Dirichlet g.f.: zeta(s-1) * zeta(s) * Product_{primes p} (1 + p^(1-2*s) - p^(2-2*s) - p^(-s)). - Vaclav Kotesovec, Dec 18 2019
From Peter Munn, Jan 01 2020: (Start)
a(A059896(n,k)) = A059896(a(n), a(k)).
a(A003961(n)) = A003961(a(n)).
a(n^2) = a(n).
a(A225546(n)) = A019565(A267116(n)). (End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = A065463/2. - Vaclav Kotesovec, Jun 24 2020
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))^2.
a(n) = Sum_{k=1..n} mu(gcd(n,k))^2*phi(gcd(n,k))/phi(n/gcd(n,k)).
For n>1, Sum_{k=1..n} a(gcd(n,k))*mu(a(gcd(n,k)))*phi(gcd(n,k))/gcd(n,k) = 0.
For n>1, Sum_{k=1..n} a(n/gcd(n,k))*mu(a(n/gcd(n,k)))*phi(gcd(n,k))*gcd(n,k) = 0. (End)
a(n) = (-1)^omega(n) * Sum_{d|n} mu(d)*psi(d), where omega = A001221 and psi = A001615. - Ridouane Oudra, Aug 01 2025

More terms from several people including David W. Wilson

Definition expanded by Jonathan Sondow, Apr 26 2013

A003557 n divided by largest squarefree divisor of n; if n = Product p(k)^e(k) then a(n) = Product p(k)^(e(k)-1), with a(1) = 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 4, 3, 1, 1, 2, 1, 1, 1, 8, 1, 3, 1, 2, 1, 1, 1, 4, 5, 1, 9, 2, 1, 1, 1, 16, 1, 1, 1, 6, 1, 1, 1, 4, 1, 1, 1, 2, 3, 1, 1, 8, 7, 5, 1, 2, 1, 9, 1, 4, 1, 1, 1, 2, 1, 1, 3, 32, 1, 1, 1, 2, 1, 1, 1, 12, 1, 1, 5, 2, 1, 1, 1, 8, 27, 1, 1, 2, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 16, 1, 7

Offset: 1

Marc LeBrun

a(n) is the size of the Frattini subgroup of the cyclic group C_n - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 07 2001.
Also of the Frattini subgroup of the dihedral group with 2*n elements. - Sharon Sela (sharonsela(AT)hotmail.com), Jan 01 2002
Number of solutions to x^m==0 (mod n) provided that n < 2^(m+1), i.e. the sequence of sequences A000188, A000189, A000190, etc. converges to this sequence. - Henry Bottomley, Sep 18 2001
a(n) is the number of nilpotent elements in the ring Z/nZ. - Laszlo Toth, May 22 2009
The sequence of partial products of a(n) is A085056(n). - Peter Luschny, Jun 29 2009
The first occurrence of n in this sequence is at A064549(n). - Franklin T. Adams-Watters, Jul 25 2014
From Hal M. Switkay, Jul 03 2025: (Start)
For n > 1, a(n) is a proper divisor of n. Thus the sequence n, a(n), a(a(n)), ... eventually becomes 1. This yields a minimal factorization of n as a product of squarefree numbers (A005117), each factor dividing all larger factors, in a factorization that is conjugate to the minimal factorization of n as a product of prime powers (A000961), as follows.
Let f(n,0) = n, and let f(n,k) = a(f(n,k-1)) for k > 0. A051903(n) is the minimal value of k such that f(n,k) = 1. A051903(n) <= log(n)/log(2). Since n/a(n) = A007947(n) is always squarefree by definition, n is a product of squarefree factors in the form Product_{i=1..A051903(n)} [f(n,i-1)/f(n,i)].
The two factorizations correspond to conjugate partitions of bigomega(n) = A001222(n). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Henry Bottomley, Some Smarandache-type multiplicative sequences.
Steven R. Finch, Idempotents and Nilpotents Modulo n, arXiv:math/0605019 [math.NT], 2006-2017.

Cf. A007947, A062378, A062379, A064549, A300717 (Möbius transform), A326306 (inv. Möbius transf.), A328572.
Sequences that are multiples of this sequence (the other factor of a pointwise product is given in parentheses): A000010 (A173557), A000027 (A007947), A001615 (A048250), A003415 (A342001), A007434 (A345052), A057521 (A071773).
Cf. A082695 (Dgf at s=2), A065487 (Dgf at s=3).
Cf. A000961, A001222, A005117, A051903.

a003557 n = product $ zipWith (^)
                      (a027748_row n) (map (subtract 1) $ a124010_row n)
-- Reinhard Zumkeller, Dec 20 2013

using Nemo
function A003557(n)
    n < 4 && return 1
    q = prod([p for (p, e) ∈ Nemo.factor(fmpz(n))])
    return n == q ? 1 : div(n, q)
end
[A003557(n) for n in 1:90] |> println  # Peter Luschny, Feb 07 2021

[(&+[(Floor(k^n/n)-Floor((k^n-1)/n)): k in [1..n]]): n in [1..100]]; // G. C. Greubel, Nov 02 2018

A003557 := n -> n/ilcm(op(numtheory[factorset](n))):
seq(A003557(n), n=1..98); # Peter Luschny, Mar 23 2011
seq(n / NumberTheory:-Radical(n), n = 1..98); # Peter Luschny, Jul 20 2021

Prepend[ Array[ #/Times@@(First[ Transpose[ FactorInteger[ # ] ] ])&, 100, 2 ], 1 ] (* Olivier Gérard, Apr 10 1997 *)

a(n)=n/factorback(factor(n)[,1]) \\ Charles R Greathouse IV, Nov 17 2014

for(n=1, 100, print1(direuler(p=2, n, (1 - p*X + X)/(1 - p*X))[n], ", ")) \\ Vaclav Kotesovec, Jun 20 2020

from sympy.ntheory.factor_ import core
from sympy import divisors
def a(n): return n / max(i for i in divisors(n) if core(i) == i)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Apr 16 2017

from math import prod
from sympy import primefactors
def A003557(n): return n//prod(primefactors(n)) # Chai Wah Wu, Nov 04 2022

def A003557(n) : return n*mul(1/p for p in prime_divisors(n))
[A003557(n) for n in (1..98)] # Peter Luschny, Jun 10 2012

Multiplicative with a(p^e) = p^(e-1). - Vladeta Jovovic, Jul 23 2001
a(n) = n/rad(n) = n/A007947(n) = sqrt(J_2(n)/J_2(rad(n))), where J_2(n) is A007434. - Enrique Pérez Herrero, Aug 31 2010
a(n) = (J_k(n)/J_k(rad(n)))^(1/k), where J_k is the k-th Jordan Totient Function: (J_2 is A007434 and J_3 A059376). - Enrique Pérez Herrero, Sep 03 2010
Dirichlet convolution of A000027 and A097945. - R. J. Mathar, Dec 20 2011
a(n) = A000010(n)/|A023900(n)|. - Eric Desbiaux, Nov 15 2013
a(n) = Product_{k = 1..A001221(n)} (A027748(n,k)^(A124010(n,k)-1)). - Reinhard Zumkeller, Dec 20 2013
a(n) = Sum_{k=1..n}(floor(k^n/n)-floor((k^n-1)/n)). - Anthony Browne, May 11 2016
a(n) = e^[Sum_{k=2..n} (floor(n/k)-floor((n-1)/k))*(1-A010051(k))*Mangoldt(k)] where Mangoldt is the Mangoldt function. - Anthony Browne, Jun 16 2016
a(n) = Sum_{d|n} mu(d) * phi(d) * (n/d), where mu(d) is the Moebius function and phi(d) is the Euler totient function (rephrases formula of Dec 2011). - Daniel Suteu, Jun 19 2018
G.f.: Sum_{k>=1} mu(k)*phi(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Nov 02 2018
Dirichlet g.f.: Product_{primes p} (1 + 1/(p^s - p)). - Vaclav Kotesovec, Jun 24 2020
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))*gcd(n,k).
a(n) = Sum_{k=1..n} mu(gcd(n,k))*(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
a(n) = A001615(n)/A048250(n) = A003415/A342001(n) = A057521(n)/A071773(n). - Antti Karttunen, Jun 08 2021

Secondary definition added to the name by Antti Karttunen, Jun 08 2021

A003958 If n = Product p(k)^e(k) then a(n) = Product (p(k)-1)^e(k).

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 6, 1, 4, 4, 10, 2, 12, 6, 8, 1, 16, 4, 18, 4, 12, 10, 22, 2, 16, 12, 8, 6, 28, 8, 30, 1, 20, 16, 24, 4, 36, 18, 24, 4, 40, 12, 42, 10, 16, 22, 46, 2, 36, 16, 32, 12, 52, 8, 40, 6, 36, 28, 58, 8, 60, 30, 24, 1, 48, 20, 66, 16, 44, 24, 70, 4, 72, 36, 32, 18, 60, 24, 78, 4, 16

Offset: 1

Marc LeBrun

Completely multiplicative.

Dirichlet inverse of A097945. - R. J. Mathar, Aug 29 2011

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 1000 terms from T. D. Noe)
Vaclav Kotesovec, Graph - the asymptotic ratio (10^7 terms).
Index to divisibility sequences

Cf. A003959, A168065, A168066, A027746, A006093, A027748, A124010.

a003958 1 = 1
a003958 n = product $ map (subtract 1) $ a027746_row n
-- Reinhard Zumkeller, Apr 09 2012, Mar 02 2012

a:= n-> mul((i[1]-1)^i[2], i=ifactors(n)[2]):
seq(a(n), n=1..80);  # Alois P. Heinz, Sep 13 2017

DirichletInverse[f_][1] = 1/f[1]; DirichletInverse[f_][n_] := DirichletInverse[f][n] = -1/f[1]*Sum[ f[n/d]*DirichletInverse[f][d], {d, Most[ Divisors[n]]}]; muphi[n_] := MoebiusMu[n]*EulerPhi[n]; Table[ DirichletInverse[ muphi][n], {n, 1, 81}] (* Jean-François Alcover, Dec 12 2011, after R. J. Mathar *)
a[1] = 1; a[n_] := (fi = FactorInteger[n]; Times @@ ((fi[[All, 1]] - 1)^fi[[All, 2]])); Table[a[n], {n, 1, 50}] (* G. C. Greubel, Jun 10 2016 *)

a(n)=if(n<1,0,direuler(p=2,n,1/(1-p*X+X))[n]) /* Ralf Stephan */

from math import prod
from sympy import factorint
def a(n): return prod((p-1)**e for p, e in factorint(n).items())
print([a(n) for n in range(1, 82)]) # Michael S. Branicky, Feb 27 2022

Multiplicative with a(p^e) = (p-1)^e. - David W. Wilson, Aug 01 2001
a(n) = A000010(n) iff n is squarefree (see A005117). - Reinhard Zumkeller, Nov 05 2004
a(n) = abs(A125131(n)). - Tom Edgar, May 26 2014
Sum_{k=1..n} a(k) ~ c * n^2, where c = Pi^4 / (315 * zeta(3)) = 1/(2*A082695) = 0.25725505075419... - Vaclav Kotesovec, Jun 14 2020
Dirichlet g.f.: Product_{p prime} 1 / (1 - p^(1-s) + p^(-s)). - Ilya Gutkovskiy, Feb 27 2022
Dirichlet g.f.: zeta(s-1) * zeta(s) * Product_{primes p} (1 + (p^(1-s) - 2) / (1 - p + p^s)), (with a product that converges for s=2). - Vaclav Kotesovec, Feb 11 2023

Definition reedited (from formula) by Daniel Forgues, Nov 17 2009

A300717 Möbius transform of A003557, n divided by its largest squarefree divisor.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 6, 0, 0, 0, 0, 8, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 6

Offset: 1

Antti Karttunen, Mar 11 2018

Multiplicative because A003557 is. - Andrew Howroyd, Jul 27 2018

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

Cf. A000010, A008683, A003557, A300718, A300719, A003958.

with(numtheory): A003557 := n -> n/ilcm(op(numtheory[factorset](n))):
seq(add(mobius(d)*A003557(n/d), d in divisors(n)), n=1..100); # Ridouane Oudra, Nov 18 2019

Table[DivisorSum[n, MoebiusMu[#] EulerPhi[#] EulerPhi[n/#] &], {n, 108}] (* Michael De Vlieger, Nov 18 2019 *)
f[p_, e_] := If[e == 1, 0, (p - 1)*p^(e - 2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Dec 06 2022 *)

A003557(n) = { my(f=factor(n)); for (i=1, #f~, f[i, 2] = max(0,f[i, 2]-1)); factorback(f); }; \\ From A003557
A300717(n) = sumdiv(n,d,moebius(n/d)*A003557(d));

a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i,2] == 1, 0, (f[i,1] - 1)*f[i,1]^(f[i,2] - 2)));} \\ Amiram Eldar, Dec 06 2022

a(n) = Sum_{d|n} A008683(n/d)*A003557(d).
a(n) = A000010(n) - A300718(n).
a(n) = A003557(n) - A300719(n).
Multiplicative with a(p) = 0 and a(p^e) = (p-1)*p^(e-2) for prime p and e>1. - Werner Schulte, Sep 27 2018
Dirichlet convolution with A003958 equals A000010. - Werner Schulte, Sep 28 2018
a(n) = Sum_{d|n} mu(d)*phi(d)*phi(n/d). - Ridouane Oudra, Nov 18 2019
Dirichlet convolution of A000010 and A097945. - R. J. Mathar, Jun 02 2020
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} phi(gcd(n,k))*mu(gcd(n,k)).
a(n) = Sum_{k=1..n} phi(gcd(n,k))*mu(n/gcd(n,k)). (End)

A176345 Sum of gcd(k,n) from k = 1 to n over "regular" integers only (an integer k is regular if there is an x such that k^2 x == k (mod n)).

Original entry on oeis.org

1, 3, 5, 6, 9, 15, 13, 12, 15, 27, 21, 30, 25, 39, 45, 24, 33, 45, 37, 54, 65, 63, 45, 60, 45, 75, 45, 78, 57, 135, 61, 48, 105, 99, 117, 90, 73, 111, 125, 108, 81, 195, 85, 126, 135, 135, 93, 120, 91, 135, 165, 150, 105, 135, 189, 156, 185, 171, 117, 270, 121, 183, 195

Offset: 1

Jeffrey Shallit, Apr 15 2010

It is also the product of n and (2-1/p), taken over all primes p dividing n.

			For n = 8, the regular integers mod 8 are 1,3,5,7,8, so the sum of gcd's of 8 with these numbers is 12.

Daniel Suteu, Table of n, a(n) for n = 1..10000
S. Chen and W. Zhai, Reciprocals of the Gcd-Sum Functions, J. Int. Seq. 14 (2011) # 11.8.3.
J.-M. De Koninck and I. Katai, Some remarks on a paper of L. Toth, JIS 13 (2010) 10.1.2.
Vaclav Kotesovec, Graph - the asymptotic ratio (1000000 terms)
Laszlo Toth, A Gcd-Sum Function Over Regular Integers Modulo n, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.5.
Laszlo Toth, A survey of gcd-sum functions, J. Int. Seq. 13 (2010) # 10.8.1.
D. Zhang and W. Zhai, Mean Values of a Gcd-Sum Function Over Regular Integers Modulo n, J. Int. Seq. 13 (2010), 10.4.7.
D. Zhang and W. Zhai, Mean Values of a Class of Arithmetical Functions, J. Int. Seq. 14 (2011) #11.6.5.

Cf. A007947, A143869.

A176345 := proc(n)
    n*mul(2-1/p,p=numtheory[factorset](n)) ;
end proc:
seq(A176345(n),n=1..40) ; # R. J. Mathar, Sep 13 2016

f[p_, e_] := 2*p^e - p^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 11 2020 *)

isregg(k, n) = {g = gcd(k, n); if ((n % g == 0) && (gcd(g, n/g) == 1), return(g), return(0));}
a(n) = sum(k=1, n, isregg(k, n)) \\ Michel Marcus, May 25 2013

a(n) = sumdiv(n, d, d * eulerphi(n/d) * moebius(n/d)^2); \\ Daniel Suteu, Jun 27 2018

a(n) = my(f=factor(n)); prod(k=1, #f~, 2*f[k,1]^f[k,2] - f[k,1]^(f[k,2]-1)); \\ Daniel Suteu, Jun 27 2018

for(n=1, 100, print1(direuler(p=2, n, (1 + p*X^2 - p^2*X^2 - X)/(1-p*X)^2)[n], ", ")) \\ Vaclav Kotesovec, Aug 20 2021

Multiplicative with a(p^e) = 2*p^e-p^(e-1).
Dirichlet g.f.: zeta(s-1)*product_p (1+p^(1-s)-p^(-s)). Dirichlet convolution of the series of absolute values of A097945 with A000027. - R. J. Mathar, Jun 11 2011
From Daniel Suteu, Jun 27 2018: (Start)
a(n) = Sum_{d|n} d * phi(n/d) * mu(n/d)^2.
a(n) = Sum_{d|n, gcd(n/d, d) = 1} d * phi(n/d). (End)
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))^2*gcd(n,k).
a(n) = Sum_{k=1..n} mu(gcd(n,k))^2*n/gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
From Vaclav Kotesovec, Aug 20 2021: (Start)
Dirichlet g.f.: zeta(s-1)^2 * Product_{primes p} (1 + p^(1-2*s) - p^(2-2*s) - p^(-s)).
Let f(s) = Product_{primes p} (1 + p^(1-2*s) - p^(2-2*s) - p^(-s)), then Sum_{k=1..n} a(k) ~ n^2 * (f(2)*(log(n)/2 + gamma - 1/4) + f'(2)/2), where f(2) = Product_{primes p} (1 - 2/p^2 + 1/p^3) = A065464 = 0.428249505677094..., f'(2) = f(2) * Sum_{primes p} log(p) * (3*p - 2) / (p^3 - 2*p + 1) = 0.6293283828324697510445630056425352981207558777167836747744750359407300858... and gamma is the Euler-Mascheroni constant A001620. (End)
a(n) = Sum_{k = 1..n} rad(gcd(k, n)) = Sum_{d divides n} rad(d)*phi(n/d), where rad(n) = A007947(n). - Peter Bala, Jan 22 2024

A276833 Sum of mu(d)*phi(d) over divisors d of n.

Original entry on oeis.org

1, 0, -1, 0, -3, 0, -5, 0, -1, 0, -9, 0, -11, 0, 3, 0, -15, 0, -17, 0, 5, 0, -21, 0, -3, 0, -1, 0, -27, 0, -29, 0, 9, 0, 15, 0, -35, 0, 11, 0, -39, 0, -41, 0, 3, 0, -45, 0, -5, 0, 15, 0, -51, 0, 27, 0, 17, 0, -57, 0, -59, 0, 5, 0, 33, 0, -65, 0, 21, 0, -69, 0, -71, 0, 3, 0, 45, 0, -77, 0, -1, 0, -81, 0, 45, 0, 27, 0, -87, 0, 55, 0, 29, 0, 51, 0, -95, 0, 9

Offset: 1

Jurjen N.E. Bos, Sep 20 2016

Discovered when incorrectly applying Mobius inversion formula.
a(n)*a(m) = a(n*m) if gcd(n,m)=1 (has a simple proof).
Strongly multiplicative: a(p^e) = 2 - p. - Charles R Greathouse IV, Oct 01 2019

			mu(d)*phi(d) = 1*1,-1*1,-1*2, 1*2 for d=1,2,3,6, so a(6) = 1*1-1*1-1*2+1*2 = 0.

Indranil Ghosh, Table of n, a(n) for n = 1..1000

For squarefree numbers, the absolute value is equal to A166586 (first exception at 25).

Cf. A097945.

with(numtheory):seq(convert(map(x->2-x,factorset(n)),`*`),n=1..99); # Robert FERREOL, Mar 14 2020

Table[Sum[MoebiusMu[d] EulerPhi[d], {d, Divisors[n]}], {n, 99}] (* Indranil Ghosh, Mar 10 2017 *)
a[1] = 1; a[n_] := Times @@ ((2 - First[#])& /@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Sep 21 2020 *)

r=0;fordiv(n,d,r+=moebius(d)*eulerphi(d));r

a(n) = sumdiv(n, d, moebius(d)*eulerphi(d)); \\ Michel Marcus, Sep 30 2016

a(n)=my(f=factor(n)[,1]); prod(i=1,#f, 2-f[i]) \\ Charles R Greathouse IV, Oct 01 2019

for(n=1, 100, print1(direuler(p=2, n, (1 - p*X + X)/(1 - X))[n], ", ")) \\ Vaclav Kotesovec, Jun 14 2020

a(n) = Sum_{d|n} mu(d)*phi(d).
G.f.: Sum_{k>=1} mu(k)*phi(k)*x^k/(1 - x^k). - Ilya Gutkovskiy, Nov 06 2018
a(n) = Product_{p prime and p|n} (2-p). - Robert FERREOL, Mar 14 2020
Dirichlet g.f.: zeta(s) * Product_{primes p} (1 - p^(1-s) + p^(-s)). - Vaclav Kotesovec, Jun 14 2020
a(n) = Sum_{k = 1..n} mu(lcm(k, n)/k). - Peter Bala, Jan 16 2024

cp's OEIS Frontend

A322581 Sum of A003958 and its Dirichlet inverse: a(n) = A003958(n) + A097945(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349356 Dirichlet convolution of A003959 with A097945 (Dirichlet inverse of A003958), where A003958 and A003959 are fully multiplicative with a(p) = p-1 and p+1 respectively.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A007947 Largest squarefree number dividing n: the squarefree kernel of n, rad(n), radical of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Scheme

Formula

Extensions

A003557 n divided by largest squarefree divisor of n; if n = Product p(k)^e(k) then a(n) = Product p(k)^(e(k)-1), with a(1) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Sage

Formula

Extensions

A003958 If n = Product p(k)^e(k) then a(n) = Product (p(k)-1)^e(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A300717 Möbius transform of A003557, n divided by its largest squarefree divisor.

Views

Author