|
%I #97 Mar 05 2024 15:38:27
%S 1,1,2,3,4,2,6,5,7,4,10,6,12,6,8,11,16,7,18,12,12,10,22,10,21,12,20,
%T 18,28,8,30,21,20,16,24,21,36,18,24,20,40,12,42,30,28,22,46,22,43,21,
%U 32,36,52,20,40,30,36,28,58,24,60,30,42,43,48,20,66,48,44,24,70,35
%N a(p^k) = p^k - p^(k-1) + p^(k-2) - ... +- 1, and then extend by multiplicativity.
%C For more information see the Comments in A061020.
%C 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
%C If m is squarefree (A005117), then a(m) = A000010(m) where A000010 is the Euler totient function. - _Michel Marcus_, Nov 08 2017
%C 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
%C 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
%D P. J. McCarthy, Introduction to Arithmetical Functions, Springer Verlag, 1986, page 25.
%H Reinhard Zumkeller, <a href="/A206369/b206369.txt">Table of n, a(n) for n = 1..10000</a>
%H László Tóth, <a href="http://arxiv.org/abs/1111.4842">A survey of the alternating sum-of-divisors function</a>, arXiv:1111.4842 [math.NT], 2011-2014.
%F a(n) = abs(A061020(n)).
%F a(n) = n*Sum_{d|n} lambda(d)/d, where lambda(n) is A008836(n). - _Enrique Pérez Herrero_, Sep 23 2012
%F Dirichlet g.f.: zeta(s - 1)*zeta(2*s)/zeta(s). - _Geoffrey Critzer_, Feb 25 2015
%F From _Michel Marcus_, Nov 05 2017: (Start)
%F a(2^n) = A001045(n+1);
%F a(3^n) = A015518(n+1);
%F a(5^n) = A015531(n+1);
%F a(7^n) = A015552(n+1);
%F a(11^n) = A015592(n+1). (End)
%F a(p^k) = p^k - a(p^(k - 1)) for k > 0 and prime p. - _David A. Corneth_, Nov 09 2017
%F 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
%F a(p^k) = A071324(p^k), for k >= 0 and prime p. - _Michel Marcus_, Aug 11 2018
%F Sum_{k=1..n} a(k) ~ Pi^2 * n^2 / 30. - _Vaclav Kotesovec_, Feb 07 2019
%F G.f.: Sum_{k>=1} lambda(k)*x^k/(1 - x^k)^2. - _Ilya Gutkovskiy_, May 23 2019
%F a(n) = Sum_{i=1..n} A010052(gcd(n,i)). - _Ridouane Oudra_, Nov 24 2019
%F a(p^k) = round(p^(k+1)/(p+1)). - _M. F. Hasler_, Feb 13 2020
%p a:= n-> mul(add(i[1]^(i[2]-j)*(-1)^j, j=0..i[2]), i=ifactors(n)[2]):
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Nov 03 2017
%t Table[Length[Select[Range[n], IntegerQ[GCD[n, #]^(1/2)] &]], {n, 72}] (* _Geoffrey Critzer_, Feb 16 2015 *)
%t a[n_] := n*DivisorSum[n, LiouvilleLambda[#]/#&]; Array[a, 72] (* _Jean-François Alcover_, Dec 04 2017, after _Enrique Pérez Herrero_ *)
%t 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 *)
%o (Haskell)
%o a206369 n = product $
%o zipWith h (a027748_row n) (map toInteger $ a124010_row n) where
%o h p e = sum $ take (fromInteger e + 1) $
%o iterate ((* p) . negate) (1 - 2 * (e `mod` 2))
%o -- _Reinhard Zumkeller_, Feb 08 2012
%o (PARI) a(n) = sum(k=1, n, issquare(gcd(n, k)));
%o (PARI) ak(p,e)=my(s=1); for(i=1,e, s=s*p + (-1)^i); s
%o a(n)=my(f=factor(n)); prod(i=1,#f~, ak(f[i,1],f[i,2])) \\ _Charles R Greathouse IV_, Dec 27 2016
%o (PARI) a(n) = sumdiv(n, d, eulerphi(n/d) * issquare(d)); \\ _Daniel Suteu_, Jun 27 2018
%o (PARI) apply( {A206369(n)=vecprod([f[1]^(f[2]+1)\/(f[1]+1)|f<-factor(n)~])}, [1..99]) \\ _M. F. Hasler_, Feb 13 2020
%o (Python)
%o from math import prod
%o from sympy import factorint
%o 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
%Y Cf. A061020, A206368.
%Y Cf. A027748 row, A124010, A206475 (first differences).
%Y Cf. A078429.
%Y Cf. A127724 (k-imperfect), A127725 (2-imperfect), A127726 (3-imperfect).
%K nonn,mult
%O 1,3
%A _N. J. A. Sloane_, Feb 06 2012
|
