|
|
A206369
|
|
a(p^k) = p^k - p^(k-1) + p^(k-2) - ... +- 1, and then extend by multiplicativity.
|
|
42
|
|
|
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, 18, 28, 8, 30, 21, 20, 16, 24, 21, 36, 18, 24, 20, 40, 12, 42, 30, 28, 22, 46, 22, 43, 21, 32, 36, 52, 20, 40, 30, 36, 28, 58, 24, 60, 30, 42, 43, 48, 20, 66, 48, 44, 24, 70, 35
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
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
|
|
|
FORMULA
|
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
|
|
MAPLE
|
a:= n-> mul(add(i[1]^(i[2]-j)*(-1)^j, j=0..i[2]), i=ifactors(n)[2]):
|
|
MATHEMATICA
|
Table[Length[Select[Range[n], IntegerQ[GCD[n, #]^(1/2)] &]], {n, 72}] (* Geoffrey Critzer, Feb 16 2015 *)
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))
(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
(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
|
|
|
KEYWORD
|
nonn,mult
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|