cp's OEIS Frontend

A046951 a(n) is the number of squares dividing n.

%I A046951 #199 Jun 14 2025 06:46:01
%S A046951 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,
%T A046951 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,
%U A046951 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
%N A046951 a(n) is the number of squares dividing n.
%C A046951 Rediscovered by the HR automatic theory formation program.
%C A046951 a(n) depends only on prime signature of n (cf. A025487, A046523). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3, 1).
%C A046951 First differences of A013936. Average value tends towards Pi^2/6 = 1.644934... (A013661, A013679). - _Henry Bottomley_, Aug 16 2001
%C A046951 We have a(n) = A159631(n) for all n < 125, but a(125) = 2 < 3 = A159631(125). - _Steven Finch_, Apr 22 2009
%C A046951 Number of 2-generated Abelian groups of order n, if n > 1. - _Álvar Ibeas_, Dec 22 2014 [In other words, number of order-n abelian groups with rank <= 2. Proof: let b(n) be such number. A finite abelian group is the inner direct product of all Sylow-p subgroups, so {b(n)} is multiplicative. Obviously b(p^e) = floor(e/2)+1 (corresponding to the groups C_(p^r) X C_(p^(e-r)) for 0 <= r <= floor(e/2)), hence b(n) = a(n) for all n. - _Jianing Song_, Nov 05 2022]
%C A046951 Number of ways of writing n = r*s such that r|s. - _Eric M. Schmidt_, Jan 08 2015
%C A046951 The number of divisors of the square root of the largest square dividing n. - _Amiram Eldar_, Jul 07 2020
%C A046951 The number of unordered factorizations of n into cubefree powers of primes (1, primes and squares of primes, A166684). - _Amiram Eldar_, Jun 12 2025
%H A046951 Reinhard Zumkeller, <a href="/A046951/b046951.txt">Table of n, a(n) for n = 1..10000</a>
%H A046951 Antonio Amariti, Claudius Klare, Domenico Orlando and Susanne Reffert, <a href="https://doi.org/10.1016/j.nuclphysb.2015.10.011">The M-theory origin of global properties of gauge theories</a>, Nuclear Physics B, Vol. 901 (2015), pp. 318-337, <a href="http://arxiv.org/abs/1507.04743">arXiv preprint</a>, arXiv:1507.04743 [hep-th], 2015 (see (A.13)).
%H A046951 Simon Colton, <a href="http://www.cs.uwaterloo.ca/journals/JIS/colton/joisol.html">Refactorable Numbers - A Machine Invention</a>, J. Integer Sequences, Vol. 2 (1999), Article 99.1.2.
%H A046951 Simon Colton, <a href="http://www.dai.ed.ac.uk/homes/simonco/research/hr/">HR - Automatic Theory Formation in Pure Mathematics</a>
%H A046951 Ian G. Connell, <a href="https://doi.org/10.4153/CMB-1964-002-1">A number theory problem concerning finite groups and rings</a>, Canad. Math. Bull, 7 (1964), 23-34. See delta(n).
%H A046951 Andrew V. Lelechenko, <a href="http://arxiv.org/abs/1407.1222">Average number of squares dividing mn</a>, arXiv preprint arXiv:1407.1222 [math.NT], 2014.
%H A046951 Werner Georg Nowak and László Tóth, <a href="https://doi.org/10.1142/S179304211350098X">On the average number of subgroups of the group Z_m X Z_n</a>, International Journal of Number Theory, Vol. 10, No. 2 (2014), pp. 363-374, <a href="http://arxiv.org/abs/1307.1414">arXiv preprint</a>, arXiv:1307.1414 [math.NT], 2013.
%H A046951 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.
%H A046951 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>.
%F A046951 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
%F A046951 a(n) = |{(i, j) : i*j = n AND i|j}| = |{(i, j) : i*j^2 = n}|. Also tau(A000188(n)), where tau = A000005.
%F A046951 Multiplicative with p^e --> floor(e/2) + 1, p prime. - _Reinhard Zumkeller_, May 20 2007
%F A046951 a(A130279(n)) = n and a(m) <> n for m < A130279(n); A008966(n)=0^(a(n) - 1). - _Reinhard Zumkeller_, May 20 2007
%F A046951 Inverse Moebius transform of characteristic function of squares (A010052). Dirichlet g.f.: zeta(s)*zeta(2s).
%F A046951 G.f.: Sum_{k > 0} x^(k^2)/(1 - x^(k^2)). - _Vladeta Jovovic_, Dec 13 2002
%F A046951 a(n) = Sum_{k=1..A000005(n)} A010052(A027750(n,k)). - _Reinhard Zumkeller_, Dec 16 2013
%F A046951 a(n) = Sum_{k = 1..n} ( floor(n/k^2) - floor((n-1)/k^2) ). - _Peter Bala_, Feb 17 2014
%F A046951 From _Antti Karttunen_, Nov 14 2016: (Start)
%F A046951 a(1) = 1; for n > 1, a(n) = A008619(A007814(n)) * a(A064989(n)).
%F A046951 a(n) = A278161(A156552(n)). (End)
%F A046951 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
%F A046951 From  _Antti Karttunen_, Nov 12 2017: (Start)
%F A046951 a(n) = A000005(n) - A056595(n).
%F A046951 a(n) = 1 + A071325(n).
%F A046951 a(n) = 1 + A001222(A293515(n)). (End)
%F A046951 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
%F A046951 a(n) = Sum_{d|n} A000005(d) * A008836(n/d). - _Torlach Rush_, Jan 21 2020
%F A046951 a(n) = A000005(sqrt(A008833(n))). - _Amiram Eldar_, Jul 07 2020
%F A046951 a(n) = Sum_{d divides n} mu(core(d)^2), where core(n) = A007913(n). - _Peter Bala_, Jan 24 2024
%e A046951 a(16) = 3 because the squares 1, 4, and 16 divide 16.
%e A046951 G.f. = x + x^2 + x^3 + 2*x^4 + x^5 + x^6 + x^7 + 2*x^8 + 2*x^9 + x^10 + ...
%p A046951 A046951 := proc(n)
%p A046951     local a,s;
%p A046951     a := 1 ;
%p A046951     for p in ifactors(n)[2] do
%p A046951         a := a*(1+floor(op(2,p)/2)) ;
%p A046951     end do:
%p A046951     a ;
%p A046951 end proc: # _R. J. Mathar_, Sep 17 2012
%p A046951 # Alternatively:
%p A046951 isbidivisible := (n, d) -> igcd(n, d) = d and igcd(n/d, d) = d:
%p A046951 a := n -> nops(select(k -> isbidivisible(n, k), [seq(1..n)])): # _Peter Luschny_, Jun 13 2025
%t A046951 a[n_] := Length[ Select[ Divisors[n], IntegerQ[Sqrt[#]]& ] ]; Table[a[n], {n, 1, 105}] (* _Jean-François Alcover_, Jun 26 2012 *)
%t A046951 Table[Length[Intersection[Divisors[n], Range[10]^2]], {n, 100}] (* _Alonso del Arte_, Dec 10 2012 *)
%t A046951 a[ n_] := If[ n < 1, 0, Sum[ Mod[ DivisorSigma[ 0, d], 2], {d, Divisors @ n}]]; (* _Michael Somos_, Jun 13 2014 *)
%t A046951 a[ n_] := If[ n < 2, Boole[ n == 1], Times @@ (Quotient[ #[[2]], 2] + 1 & /@ FactorInteger @ n)]; (* _Michael Somos_, Jun 13 2014 *)
%t A046951 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 *)
%t A046951 f[p_, e_] := 1 + Floor[e/2]; a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* _Amiram Eldar_, Sep 15 2020 *)
%o A046951 (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
%o A046951 (PARI) a(n) = direuler(p=2, n, 1/((1-X^2)*(1-X)))[n]; \\ _Michel Marcus_, Mar 08 2015
%o A046951 (PARI) a(n)=factorback(apply(e->e\2+1, factor(n)[,2])) \\ _Charles R Greathouse IV_, Sep 17 2015
%o A046951 (Haskell)
%o A046951 a046951 = sum . map a010052 . a027750_row
%o A046951 -- _Reinhard Zumkeller_, Dec 16 2013
%o A046951 (Scheme)
%o A046951 (definec (A046951 n) (if (= 1 n) 1 (* (A008619 (A007814 n)) (A046951 (A064989 n)))))
%o A046951 (define (A008619 n) (+ 1 (/ (- n (modulo n 2)) 2)))
%o A046951 ;; _Antti Karttunen_, Nov 14 2016
%o A046951 (Magma) [#[d: d in Divisors(n)|IsSquare(d)]:n in [1..120]]; // _Marius A. Burtea_, Jan 21 2020
%o A046951 (Python)
%o A046951 from math import prod
%o A046951 from sympy import factorint
%o A046951 def A046951(n): return prod((e>>1)+1 for e in factorint(n).values()) # _Chai Wah Wu_, Aug 04 2024
%o A046951 (Python)
%o A046951 def is_bidivisible(n, d) -> bool: return gcd(n, d) == d and gcd(n//d, d) == d
%o A046951 def aList(n) -> list[int]: return [k for k in range(1, n+1) if is_bidivisible(n, k)]
%o A046951 print([len(aList(n)) for n in range(1, 126)])  # _Peter Luschny_, Jun 13 2025
%Y A046951 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).
%Y A046951 One more than A071325.
%Y A046951 Differs from A096309 for the first time at n=32, where a(32) = 3, while A096309(32) = 2 (and also A185102(32) = 2).
%Y A046951 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).
%Y A046951 Sequences of the form n^k * Sum_{d^2|n} 1/d^k for k = 0..10: this sequence (k=0), A340774 (k=1), A351600 (k=2), A351601 (k=3), A351602 (k=4), A351603 (k=5), A351604 (k=6), A351605 (k=7), A351606 (k=8), A351607 (k=9), A351608 (k=10).
%Y A046951 Cf. A082293 (a(n)==2), A082294 (a(n)==3).
%K A046951 nice,nonn,mult,easy
%O A046951 1,4
%A A046951 Simon Colton (simonco(AT)cs.york.ac.uk)
%E A046951 Data section filled up to 125 terms and wrong claim deleted from Crossrefs section by _Antti Karttunen_, Nov 14 2016