A096309 -id:A096309 - cp's OEIS frontend

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

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

Rediscovered by the HR automatic theory formation program.
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).
First differences of A013936. Average value tends towards Pi^2/6 = 1.644934... (A013661, A013679). - Henry Bottomley, Aug 16 2001
We have a(n) = A159631(n) for all n < 125, but a(125) = 2 < 3 = A159631(125). - Steven Finch, Apr 22 2009
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]
Number of ways of writing n = r*s such that r|s. - Eric M. Schmidt, Jan 08 2015
The number of divisors of the square root of the largest square dividing n. - Amiram Eldar, Jul 07 2020
The number of unordered factorizations of n into cubefree powers of primes (1, primes and squares of primes, A166684). - Amiram Eldar, Jun 12 2025

			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 + ...

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.

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

a046951 = sum . map a010052 . a027750_row
-- Reinhard Zumkeller, Dec 16 2013

[#[d: d in Divisors(n)|IsSquare(d)]:n in [1..120]]; // Marius A. Burtea, Jan 21 2020

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

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 *)

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

a(n) = direuler(p=2, n, 1/((1-X^2)*(1-X)))[n]; \\ Michel Marcus, Mar 08 2015

a(n)=factorback(apply(e->e\2+1, factor(n)[,2])) \\ Charles R Greathouse IV, Sep 17 2015

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

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

(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

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..A000005(n)} A010052(A027750(n,k)). - Reinhard Zumkeller, Dec 16 2013
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)
a(1) = 1; for n > 1, a(n) = A008619(A007814(n)) * a(A064989(n)).
a(n) = A278161(A156552(n)). (End)
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) = A000005(n) - A056595(n).
a(n) = 1 + A071325(n).
a(n) = 1 + A001222(A293515(n)). (End)
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|n} A000005(d) * A008836(n/d). - Torlach Rush, Jan 21 2020
a(n) = A000005(sqrt(A008833(n))). - Amiram Eldar, Jul 07 2020
a(n) = Sum_{d divides n} mu(core(d)^2), where core(n) = A007913(n). - Peter Bala, Jan 24 2024

Data section filled up to 125 terms and wrong claim deleted from Crossrefs section by Antti Karttunen, Nov 14 2016

A185102 a(n) is the recursion depth of repeatedly factoring n and then the exponents in its prime product factorization, until 1 is reached.

Original entry on oeis.org

0, 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, 2, 1, 1, 1, 2, 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, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 3, 3, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1

Offset: 1

Colm Bhandal, Jan 23 2012

nonn

a(n) is the depth of a tree whose root is n and whose construction follows the rule: The children of n are the exponents in its prime factorization. If the number is 1, the convention is taken that the prime factorization is empty, and hence the set of children of 1 is the null set. The formulaic sequence definition given uses pattern matching on n as a product of primes, which is always possible by the fundamental theorem of arithmetic. The max{...} notation refers to the maximum value of the specified set.
The sequence differs from A096309 only at a(1) = 0. The justification for this choice is that the null product of primes has 0 levels.
For all numbers i less than or equal to 2^^x, i.e., 2 tetrated to the x, a(i) < x. Tetration is the next hyperoperation after exponentiation, and can be defined: x^^0 = 1 and x^^y = x^(x^^(y - 1)). Due to this bound the sequence can be seen to grow very slowly.

			a(156) = a(2^2*3*13) = 1 + max{a(2), a(1)} = 1 + max{1, 0} = 1 + 1 = 2

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Vitalii V. Iudelevich, On The Tree Structure of Natural Numbers, II, arXiv:2210.06055 [math.NT], 2022. See Figure 2 p. 2.
Wikipedia, Tetration

Cf. A096309.

f[n_Integer] := FactorInteger[n][[All, 2]]; a[1] = 0; a[n_] := Depth[f[n] //. k_Integer /; k > 1 :> f[k]] - 1; Table[a[n], {n, 1, 105}] (* Jean-François Alcover, Nov 20 2013 *)
a = {0}; Do[AppendTo[a, 1 + Max @@ a[[Union[FactorInteger[n][[All, 2]]]]]], {n, 2, 105}]; a (* Ray Chandler, Nov 22 2013 *)

a(n)=if(n<4,n>1,vecmax(apply(a,Set(factor(n)[,2])))+1) \\ Charles R Greathouse IV, Nov 21 2013

a(1) = 0. a(p1^k1*p2^k2*...*pn^kn) = 1 + max{a(k1), a(k2), ..., a(kn)} with all pi prime and distinct.

a(n) <= lg*(n), where lg*(x) = 0 if x < 2 and lg*(x) = lg*(log_2(x)) otherwise. - Charles R Greathouse IV, Nov 21 2013

Corrected (n=32, 36, 64, 72, 96, 100) by Jean-François Alcover, Nov 20 2013

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Scheme

Formula

Extensions

A185102 a(n) is the recursion depth of repeatedly factoring n and then the exponents in its prime product factorization, until 1 is reached.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions