%I #182 Aug 04 2024 01:25:08

%S 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 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 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 a(n) is the number of squares dividing n.

%C Rediscovered by the HR automatic theory formation program.

%C 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 First differences of A013936. Average value tends towards Pi^2/6 = 1.644934... (A013661, A013679). - _Henry Bottomley_, Aug 16 2001

%C We have a(n) = A159631(n) for all n < 125, but a(125) = 2 < 3 = A159631(125). - _Steven Finch_, Apr 22 2009

%C 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 Number of ways of writing n = r*s such that r|s. - _Eric M. Schmidt_, Jan 08 2015

%C The number of divisors of the square root of the largest square dividing n. - _Amiram Eldar_, Jul 07 2020

%H Reinhard Zumkeller, <a href="/A046951/b046951.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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, #2.

%H Simon Colton, <a href="http://www.dai.ed.ac.uk/homes/simonco/research/hr/">HR - Automatic Theory Formation in Pure Mathematics</a>

%H 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 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 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 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

%F 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 a(n) = |{(i, j) : i*j = n AND i|j}| = |{(i, j) : i*j^2 = n}|. Also tau(A000188(n)), where tau = A000005.

%F Multiplicative with p^e --> floor(e/2) + 1, p prime. - _Reinhard Zumkeller_, May 20 2007

%F a(A130279(n)) = n and a(m) <> n for m < A130279(n); A008966(n)=0^(a(n) - 1). - _Reinhard Zumkeller_, May 20 2007

%F Inverse Moebius transform of characteristic function of squares (A010052). Dirichlet g.f.: zeta(s)*zeta(2s).

%F G.f.: Sum_{k > 0} x^(k^2)/(1 - x^(k^2)). - _Vladeta Jovovic_, Dec 13 2002

%F a(n) = Sum_{k=1..A000005(n)} A010052(A027750(n,k)). - _Reinhard Zumkeller_, Dec 16 2013

%F a(n) = Sum_{k = 1..n} ( floor(n/k^2) - floor((n-1)/k^2) ). - _Peter Bala_, Feb 17 2014

%F From _Antti Karttunen_, Nov 14 2016: (Start)

%F a(1) = 1; for n > 1, a(n) = A008619(A007814(n)) * a(A064989(n)).

%F a(n) = A278161(A156552(n)).

%F (End)

%F 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 From _Antti Karttunen_, Nov 12 2017: (Start)

%F a(n) = A000005(n) - A056595(n).

%F a(n) = 1 + A071325(n).

%F a(n) = 1 + A001222(A293515(n)).

%F (End)

%F 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 a(n) = Sum_{d|n} A000005(d) * A008836(n/d). - _Torlach Rush_, Jan 21 2020

%F a(n) = A000005(sqrt(A008833(n))). - _Amiram Eldar_, Jul 07 2020

%F a(n) = Sum_{d divides n} mu(core(d)^2), where core(n) = A007913(n). - _Peter Bala_, Jan 24 2024

%e a(16) = 3 because the squares 1, 4, and 16 divide 16.

%e 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 := proc(n)

%p local a,s;

%p a := 1 ;

%p for p in ifactors(n)[2] do

%p a := a*(1+floor(op(2,p)/2)) ;

%p end do:

%p a ;

%p end proc: # _R. J. Mathar_, Sep 17 2012

%t a[n_] := Length[ Select[ Divisors[n], IntegerQ[Sqrt[#]]& ] ]; Table[a[n], {n, 1, 105}] (* _Jean-François Alcover_, Jun 26 2012 *)

%t Table[Length[Intersection[Divisors[n], Range[10]^2]], {n, 100}] (* _Alonso del Arte_, Dec 10 2012 *)

%t a[ n_] := If[ n < 1, 0, Sum[ Mod[ DivisorSigma[ 0, d], 2], {d, Divisors @ n}]]; (* _Michael Somos_, Jun 13 2014 *)

%t a[ n_] := If[ n < 2, Boole[ n == 1], Times @@ (Quotient[ #[[2]], 2] + 1 & /@ FactorInteger @ n)]; (* _Michael Somos_, Jun 13 2014 *)

%t 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 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 (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 (PARI) a(n) = direuler(p=2, n, 1/((1-X^2)*(1-X)))[n]; \\ _Michel Marcus_, Mar 08 2015

%o (PARI) a(n)=factorback(apply(e->e\2+1, factor(n)[,2])) \\ _Charles R Greathouse IV_, Sep 17 2015

%o (Haskell)

%o a046951 = sum . map a010052 . a027750_row

%o -- _Reinhard Zumkeller_, Dec 16 2013

%o (Scheme)

%o (definec (A046951 n) (if (= 1 n) 1 (* (A008619 (A007814 n)) (A046951 (A064989 n)))))

%o (define (A008619 n) (+ 1 (/ (- n (modulo n 2)) 2)))

%o ;; _Antti Karttunen_, Nov 14 2016

%o (Magma) [#[d: d in Divisors(n)|IsSquare(d)]:n in [1..120]]; // _Marius A. Burtea_, Jan 21 2020

%o (Python)

%o from math import prod

%o from sympy import factorint

%o def A046951(n): return prod((e>>1)+1 for e in factorint(n).values()) # _Chai Wah Wu_, Aug 04 2024

%Y 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, A278161.

%Y One more than A071325.

%Y Differs from A096309 for the first time at n=32, where a(32) = 3, while A096309(32) = 2 (and also A185102(32) = 2).

%Y 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 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 Cf. A082293 (a(n)==2), A082294 (a(n)==3).

%K nice,nonn,mult

%O 1,4

%A Simon Colton (simonco(AT)cs.york.ac.uk)

%E Data section filled up to 125 terms and wrong claim deleted from Crossrefs section by _Antti Karttunen_, Nov 14 2016