OFFSET
1,3
COMMENTS
For more information see the Comments in A061020.
a(n) is the number of integers j such that 1 <= j <= n and gcd(n,j) is a perfect square. For example, a(12) = 6 because |{1,4,5,7,8,11}|=6 and the respective GCDs with 12 are 1,4,1,1,4,1, which are squares. - Geoffrey Critzer, Feb 16 2015
If m is squarefree (A005117), then a(m) = A000010(m) where A000010 is the Euler totient function. - Michel Marcus, Nov 08 2017
Also it appears that the primorials (A002110) is the sequence of indices of minimum records for a(n)/n, and these records are A038110(n)/A060753(n). - Michel Marcus, Nov 09 2017
Also called rho(n). When rho(n) | n, then n is called k-imperfect, with k = n/rho(n), cf. A127724. - M. F. Hasler, Feb 13 2020
REFERENCES
P. J. McCarthy, Introduction to Arithmetical Functions, Springer Verlag, 1986, page 25.
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
László Tóth, A survey of the alternating sum-of-divisors function, arXiv:1111.4842 [math.NT], 2011-2014.
FORMULA
a(n) = abs(A061020(n)).
a(n) = n*Sum_{d|n} lambda(d)/d, where lambda(n) is A008836(n). - Enrique Pérez Herrero, Sep 23 2012
Dirichlet g.f.: zeta(s - 1)*zeta(2*s)/zeta(s). - Geoffrey Critzer, Feb 25 2015
From Michel Marcus, Nov 05 2017: (Start)
a(2^n) = A001045(n+1);
a(3^n) = A015518(n+1);
a(5^n) = A015531(n+1);
a(7^n) = A015552(n+1);
a(11^n) = A015592(n+1). (End)
a(p^k) = p^k - a(p^(k - 1)) for k > 0 and prime p. - David A. Corneth, Nov 09 2017
a(n) = Sum_{d|n, d is a perfect square} phi(n/d), where phi(k) is the Euler totient function. - Daniel Suteu, Jun 27 2018
a(p^k) = A071324(p^k), for k >= 0 and prime p. - Michel Marcus, Aug 11 2018
Sum_{k=1..n} a(k) ~ Pi^2 * n^2 / 30. - Vaclav Kotesovec, Feb 07 2019
G.f.: Sum_{k>=1} lambda(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, May 23 2019
a(n) = Sum_{i=1..n} A010052(gcd(n,i)). - Ridouane Oudra, Nov 24 2019
a(p^k) = round(p^(k+1)/(p+1)). - M. F. Hasler, Feb 13 2020
MAPLE
a:= n-> mul(add(i[1]^(i[2]-j)*(-1)^j, j=0..i[2]), i=ifactors(n)[2]):
seq(a(n), n=1..100); # Alois P. Heinz, Nov 03 2017
MATHEMATICA
Table[Length[Select[Range[n], IntegerQ[GCD[n, #]^(1/2)] &]], {n, 72}] (* Geoffrey Critzer, Feb 16 2015 *)
a[n_] := n*DivisorSum[n, LiouvilleLambda[#]/#&]; Array[a, 72] (* Jean-François Alcover, Dec 04 2017, after Enrique Pérez Herrero *)
f[p_, e_] := Sum[(-1)^(e-k)*p^k, {k, 0, e}]; a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Jan 01 2020 *)
PROG
(Haskell)
a206369 n = product $
zipWith h (a027748_row n) (map toInteger $ a124010_row n) where
h p e = sum $ take (fromInteger e + 1) $
iterate ((* p) . negate) (1 - 2 * (e `mod` 2))
-- Reinhard Zumkeller, Feb 08 2012
(PARI) a(n) = sum(k=1, n, issquare(gcd(n, k)));
(PARI) ak(p, e)=my(s=1); for(i=1, e, s=s*p + (-1)^i); s
a(n)=my(f=factor(n)); prod(i=1, #f~, ak(f[i, 1], f[i, 2])) \\ Charles R Greathouse IV, Dec 27 2016
(PARI) a(n) = sumdiv(n, d, eulerphi(n/d) * issquare(d)); \\ Daniel Suteu, Jun 27 2018
(PARI) apply( {A206369(n)=vecprod([f[1]^(f[2]+1)\/(f[1]+1)|f<-factor(n)~])}, [1..99]) \\ M. F. Hasler, Feb 13 2020
(Python)
from math import prod
from sympy import factorint
def A206369(n): return prod((lambda x:x[0]+int((x[1]<<1)>=p+1))(divmod(p**(e+1), p+1)) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 05 2024
CROSSREFS
Cf. A078429.
KEYWORD
nonn,mult
AUTHOR
N. J. A. Sloane, Feb 06 2012
STATUS
approved