A046951 a(n) is the number of squares dividing n.
1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 3, 1, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 3, 2, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 1, 1, 1, 4, 1, 1, 2, 2, 1, 1, 1, 3, 3, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 3, 1, 2, 2, 4, 1, 1, 1, 2, 1, 1, 1, 4, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2
Offset: 1
Examples
a(16) = 3 because the squares 1, 4, and 16 divide 16. G.f. = x + x^2 + x^3 + 2*x^4 + x^5 + x^6 + x^7 + 2*x^8 + 2*x^9 + x^10 + ...
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
- Antonio Amariti, Claudius Klare, Domenico Orlando and Susanne Reffert, The M-theory origin of global properties of gauge theories, Nuclear Physics B, Vol. 901 (2015), pp. 318-337, arXiv preprint, arXiv:1507.04743 [hep-th], 2015 (see (A.13)).
- Simon Colton, Refactorable Numbers - A Machine Invention, J. Integer Sequences, Vol. 2 (1999), Article 99.1.2.
- Simon Colton, HR - Automatic Theory Formation in Pure Mathematics
- Ian G. Connell, A number theory problem concerning finite groups and rings, Canad. Math. Bull, 7 (1964), 23-34. See delta(n).
- Andrew V. Lelechenko, Average number of squares dividing mn, arXiv preprint arXiv:1407.1222 [math.NT], 2014.
- Werner Georg Nowak and László Tóth, On the average number of subgroups of the group Z_m X Z_n, International Journal of Number Theory, Vol. 10, No. 2 (2014), pp. 363-374, arXiv preprint, arXiv:1307.1414 [math.NT], 2013.
- N. J. A. Sloane, Transforms.
- Index entries for sequences computed from exponents in factorization of n.
Crossrefs
Cf. A000005, A000188, A004101, A005117 (positions of 1's), A008619, A008833, A013936 (partial sums), A038538, A046952, A052304, A056595, A159631, A007814, A010052, A027750, A239930, A007862, A046523, A064989, A065704, A130279, A156552, A166684, A278161, A307445 (Dirichlet inverse).
One more than A071325.
Differs from A096309 for the first time at n=32, where a(32) = 3, while A096309(32) = 2 (and also A185102(32) = 2).
Sum of the k-th powers of the square divisors of n for k=0..10: this sequence (k=0), A035316 (k=1), A351307 (k=2), A351308 (k=3), A351309 (k=4), A351310 (k=5), A351311 (k=6), A351313 (k=7), A351314 (k=8), A351315 (k=9), A351315 (k=10).
Programs
-
Haskell
a046951 = sum . map a010052 . a027750_row -- Reinhard Zumkeller, Dec 16 2013
-
Magma
[#[d: d in Divisors(n)|IsSquare(d)]:n in [1..120]]; // Marius A. Burtea, Jan 21 2020
-
Maple
A046951 := proc(n) local a,s; a := 1 ; for p in ifactors(n)[2] do a := a*(1+floor(op(2,p)/2)) ; end do: a ; end proc: # R. J. Mathar, Sep 17 2012 # Alternatively: isbidivisible := (n, d) -> igcd(n, d) = d and igcd(n/d, d) = d: a := n -> nops(select(k -> isbidivisible(n, k), [seq(1..n)])): # Peter Luschny, Jun 13 2025
-
Mathematica
a[n_] := Length[ Select[ Divisors[n], IntegerQ[Sqrt[#]]& ] ]; Table[a[n], {n, 1, 105}] (* Jean-François Alcover, Jun 26 2012 *) Table[Length[Intersection[Divisors[n], Range[10]^2]], {n, 100}] (* Alonso del Arte, Dec 10 2012 *) a[ n_] := If[ n < 1, 0, Sum[ Mod[ DivisorSigma[ 0, d], 2], {d, Divisors @ n}]]; (* Michael Somos, Jun 13 2014 *) a[ n_] := If[ n < 2, Boole[ n == 1], Times @@ (Quotient[ #[[2]], 2] + 1 & /@ FactorInteger @ n)]; (* Michael Somos, Jun 13 2014 *) a[ n_] := If[ n < 0, 0, SeriesCoefficient[ Sum[ x^k^2 / (1 - x^k^2), {k, Sqrt @ n}], {x, 0, n}]]; (* Michael Somos, Jun 13 2014 *) f[p_, e_] := 1 + Floor[e/2]; a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Sep 15 2020 *) -
PARI
a(n)=my(f=factor(n));for(i=1,#f[,1],f[i,2]\=2);numdiv(factorback(f)) \\ Charles R Greathouse IV, Dec 11 2012
-
PARI
a(n) = direuler(p=2, n, 1/((1-X^2)*(1-X)))[n]; \\ Michel Marcus, Mar 08 2015
-
PARI
a(n)=factorback(apply(e->e\2+1, factor(n)[,2])) \\ Charles R Greathouse IV, Sep 17 2015
-
Python
from math import prod from sympy import factorint def A046951(n): return prod((e>>1)+1 for e in factorint(n).values()) # Chai Wah Wu, Aug 04 2024
-
Python
def is_bidivisible(n, d) -> bool: return gcd(n, d) == d and gcd(n//d, d) == d def aList(n) -> list[int]: return [k for k in range(1, n+1) if is_bidivisible(n, k)] print([len(aList(n)) for n in range(1, 126)]) # Peter Luschny, Jun 13 2025
-
Scheme
(definec (A046951 n) (if (= 1 n) 1 (* (A008619 (A007814 n)) (A046951 (A064989 n))))) (define (A008619 n) (+ 1 (/ (- n (modulo n 2)) 2))) ;; Antti Karttunen, Nov 14 2016
Formula
a(p^k) = A008619(k) = [k/2] + 1. a(A002110(n)) = 1 for all n. (This is true for any squarefree number, A005117). - Original notes clarified by Antti Karttunen, Nov 14 2016
a(n) = |{(i, j) : i*j = n AND i|j}| = |{(i, j) : i*j^2 = n}|. Also tau(A000188(n)), where tau = A000005.
Multiplicative with p^e --> floor(e/2) + 1, p prime. - Reinhard Zumkeller, May 20 2007
a(A130279(n)) = n and a(m) <> n for m < A130279(n); A008966(n)=0^(a(n) - 1). - Reinhard Zumkeller, May 20 2007
Inverse Moebius transform of characteristic function of squares (A010052). Dirichlet g.f.: zeta(s)*zeta(2s).
G.f.: Sum_{k > 0} x^(k^2)/(1 - x^(k^2)). - Vladeta Jovovic, Dec 13 2002
a(n) = Sum_{k = 1..n} ( floor(n/k^2) - floor((n-1)/k^2) ). - Peter Bala, Feb 17 2014
From Antti Karttunen, Nov 14 2016: (Start)
G.f.: Sum_{k>0}(theta(q^k)-1)/2, where theta(q)=1+2q+2q^4+2q^9+2q^16+... - Mamuka Jibladze, Dec 04 2016
From Antti Karttunen, Nov 12 2017: (Start)
a(n) = 1 + A071325(n).
L.g.f.: -log(Product_{k>=1} (1 - x^(k^2))^(1/k^2)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Jul 30 2018
a(n) = Sum_{d divides n} mu(core(d)^2), where core(n) = A007913(n). - Peter Bala, Jan 24 2024
Extensions
Data section filled up to 125 terms and wrong claim deleted from Crossrefs section by Antti Karttunen, Nov 14 2016
Comments