A027750 -id:A027750 - cp's OEIS frontend

A007955 Product of divisors of n.

1, 2, 3, 8, 5, 36, 7, 64, 27, 100, 11, 1728, 13, 196, 225, 1024, 17, 5832, 19, 8000, 441, 484, 23, 331776, 125, 676, 729, 21952, 29, 810000, 31, 32768, 1089, 1156, 1225, 10077696, 37, 1444, 1521, 2560000, 41, 3111696, 43, 85184, 91125, 2116, 47, 254803968, 343

Offset: 1

R. Muller

All terms of this sequence occur only once. See the second T. D. Noe link for a proof. - T. D. Noe, Jul 07 2008
Every natural number has a unique representation in terms of divisor products. See the W. Lang link. - Wolfdieter Lang, Feb 08 2011
a(n) = n only if n is prime or 1 (or, if n is in A008578). - Alonso del Arte, Apr 18 2011
Sometimes called the "divisorial" of n. - Daniel Forgues, Aug 03 2012
a(n) divides EulerPhi(x^n-y^n) (see A. Rotkiewicz link). - Michel Marcus, Dec 15 2012
The proof that all the terms of this sequence occur only once (mentioned above) was given by Niven in 1984. - Amiram Eldar, Aug 16 2020

			Divisors of 10 = [1, 2, 5, 10]. So, a(10) = 2*5*10 = 100. - _Indranil Ghosh_, Mar 22 2017

József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 1, p. 57.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 83.

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Wolfdieter Lang, Divisor Product Representation for Natural Numbers.
M. Le, On Smarandache Divisor Products, Smarandache Notions Journal, Vol. 10, No. 1-2-3, 1999, 144-145.
F. Luca, On the product of divisors of n and sigma(n), J. Ineq. Pure Appl. Math. 4 (2) 2003, Article 46.
T. D. Noe, The Divisor Product is Unique
A. Rotkiewicz, On the numbers Phi(a^n +/- b^n), Proc. Amer. Math. Soc. 12 (1961), 419-421.
Rodica Simon and Frank W. Schmid, Problem E 2946, The American Mathematical Monthly, Vol. 89, No. 5 (1982), p. 333, Ivan Niven, Product of all Positive Divisors of n, solution to problem E 2946, ibid., Vol. 91, No. 10 (1984), p. 650.
F. Smarandache, Only Problems, Not Solutions!.
Eric Weisstein's World of Mathematics, Divisor Product.
Zhu Weiyi, On the divisor product sequences, Smarandache Notions J., Vol. 14 (2004), pp. 144-146.
OEIS Wiki, Divisorial.

Cf. A000005, A000196, A001222, A007422, A007956, A027750, A030628, A046523, A069264, A072046, A111398, A162947, A224381, A243103, A280076, A283995.
Cf. A000203 (sums of divisors).
Cf. A000010 (comments on product formulas).

List(List([1..50],n->DivisorsInt(n)),Product); # Muniru A Asiru, Feb 17 2019

a007955 = product . a027750_row  -- Reinhard Zumkeller, Feb 06 2012

f := function(n); t1 := &*[d : d in Divisors(n) ]; return t1; end function;

A007955 := proc(n) mul(d,d=numtheory[divisors](n)) ; end proc: # R. J. Mathar, Mar 17 2011
seq(isqrt(n^numtheory[tau](n)), n=1..50); # Gary Detlefs, Feb 15 2019

Array [ Times @@ Divisors[ # ]&, 100 ]
a[n_] := n^(DivisorSigma[0, n]/2); Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 21 2013 *)

a(n)=if(issquare(n,&n),n^numdiv(n^2),n^(numdiv(n)/2)) \\ Charles R Greathouse IV, Feb 11 2011

from sympy import prod, divisors
print([prod(divisors(n)) for n in range(1, 51)]) # Indranil Ghosh, Mar 22 2017

from math import isqrt
from sympy import divisor_count
def A007955(n):
    d = divisor_count(n)
    return isqrt(n)**d if d % 2 else n**(d//2) # Chai Wah Wu, Jan 05 2022

[prod(divisors(n)) for n in (1..100)] # Giuseppe Coppoletta, Dec 16 2014

[n^(sigma(n,0)/2) for n in (1..49)] # Stefano Spezia, Jul 14 2025

;; A naive stand-alone implementation:
(define (A007955 n) (let loop ((d n) (m 1)) (cond ((zero? d) m) ((zero? (modulo n d)) (loop (- d 1) (* m d))) (else (loop (- d 1) m)))))
;; Faster, if A000005 and A000196 are available:
(define (A007955 n) (A000196 (expt n (A000005 n))))
;; Antti Karttunen, Mar 22 2017

a(n) = n^(d(n)/2) = n^(A000005(n)/2). Since a(n) = Product_(d|n) d = Product_(d|n) n/d, we have a(n)*a(n) = Product_(d|n) d*(n/d) = Product_(d|n) n = n^(tau(n)), whence a(n) = n^(tau(n)/2).
a(p^k) = p^A000217(k). - Enrique Pérez Herrero, Jul 22 2011
a(n) = A078599(n) * A178649(n). - Reinhard Zumkeller, Feb 06 2012
a(n) = A240694(n, A000005(n)). - Reinhard Zumkeller, Apr 10 2014
From Antti Karttunen, Mar 22 2017: (Start)
a(n) = A000196(n^A000005(n)). [From the original formula.]
A001222(a(n)) = A069264(n). [See Geoffrey Critzer's Feb 03 2015 comment in the latter sequence.]
A046523(a(n)) = A283995(n).
(End)
a(n) = Product_{k=1..n} gcd(n,k)^(1/phi(n/gcd(n,k))) = Product_{k=1..n} (n/gcd(n,k))^(1/phi(n/gcd(n,k))) where phi = A000010. - Richard L. Ollerton, Nov 07 2021
From Bernard Schott, Jan 11 2022: (Start)
a(n) = n^2 iff n is in A007422.
a(n) = n^3 iff n is in A162947.
a(n) = n^4 iff n is in A111398.
a(n) = n^5 iff n is in A030628.
a(n) = n^(3/2) iff n is in A280076. (End)
From Amiram Eldar, Oct 29 2022: (Start)
a(n) = n * A007956(n).
Sum_{k=1..n} 1/a(k) ~ log(log(n)) + c + O(1/log(n)), where c is a constant (Weiyi, 2004; Sandor and Crstici, 2004). (End)
a(n) = Product_{k=1..n} (n * (1 - ceiling(n/k - floor(n/k))))/k + ceiling(n/k - floor(n/k)). - Adriano Steffler, Feb 08 2024

A001037 Number of degree-n irreducible polynomials over GF(2); number of n-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period n; number of binary Lyndon words of length n.

Original entry on oeis.org

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557, 364722, 698870, 1342176, 2580795, 4971008, 9586395, 18512790, 35790267, 69273666, 134215680, 260300986, 505286415, 981706806, 1908866960, 3714566310, 7233615333, 14096302710, 27487764474

Offset: 0

N. J. A. Sloane

Also dimensions of free Lie algebras - see A059966, which is essentially the same sequence.
This sequence also represents the number N of cycles of length L in a digraph under x^2 seen modulo a Mersenne prime M_q=2^q-1. This number does not depend on q and L is any divisor of q-1. See Theorem 5 and Corollary 3 of the Shallit and Vasiga paper: N=sum(eulerphi(d)/order(d,2)) where d is a divisor of 2^(q-1)-1 such that order(d,2)=L. - Tony Reix, Nov 17 2005
Except for a(0) = 1, Bau-Sen Du's [1985/2007] Table 1, p. 6, has this sequence as the 7th (rightmost) column. Other columns of the table include (but are not identified as) A006206-A006208. - Jonathan Vos Post, Jun 18 2007
"Number of binary Lyndon words" means: number of binary strings inequivalent modulo rotation (cyclic permutation) of the digits and not having a period smaller than n. This provides a link to A103314, since these strings correspond to the inequivalent zero-sum subsets of U_m (m-th roots of unity) obtained by taking the union of U_n (n|m) with 0 or more U_d (n | d, d | m) multiplied by some power of exp(i 2Pi/n) to make them mutually disjoint. (But not all zero-sum subsets of U_m are of that form.) - M. F. Hasler, Jan 14 2007
Also the number of dynamical cycles of period n of a threshold Boolean automata network which is a quasi-minimal positive circuit of size a multiple of n and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb 25 2009
Also, the number of periodic points with (minimal) period n in the iteration of the tent map f(x):=2min{x,1-x} on the unit interval. - Pietro Majer, Sep 22 2009
Number of distinct cycles of minimal period n in a shift dynamical system associated with a totally disconnected hyperbolic iterated function system (see Barnsley link). - Michel Marcus, Oct 06 2013
From Jean-Christophe Hervé, Oct 26 2014: (Start)
For n > 0, a(n) is also the number of orbits of size n of the transform associated to the Kolakoski sequence A000002 (and this is true for any map with 2^n periodic points of period n). The Kolakoski transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The Kolakoski sequence is one of the two fixed points of this transform, the other being the same sequence without the initial term. A025142 and A025143 are the periodic points of the orbit of size 2. A027375(n) = n*a(n) gives the number of periodic points of minimal period n.
For n > 1, this sequence is equal to A059966 and to A060477, and for n = 1, a(1) = A059966(1)+1 = A060477(1)-1; this because the n-th term of all 3 sequences is equal to (1/n)*sum_{d|n} mu(n/d)*(2^d+e), with e = -1/0/1 for resp. A059966/this sequence/A060477, and sum_{d|n} mu(n/d) equals 1 for n = 1 and 0 for all n > 1. (End)
Warning: A000031 and A001037 are easily confused, since they have similar formulas.
From Petros Hadjicostas, Jul 14 2020: (Start)
Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.
Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) = A001221(N) being the number of distinct primes of N).
For N = 3, a = phi(3)/2 + omega(3) = 2/2 + 1 = 2 and b = omega(3) - 1 = 0. It follows that D(w, N=3) = A000079(w) = 2^w.
For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.
For N = 3, we get that c(w, N=3) = A000079(w)/w = 2^w/w.
He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.)
Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).
For N = 3, we saw that a = 2 and b = 0, and hence d*(w, N=3) = a(w) = Sum_{k | w} (mu(k)/k) * 2^(w/k) / (w/k) = (1/w) * Sum_{k | w} mu(k) * 2^(w/k) for w >= 1. See Table 1 on p. 6 in Kam Cheong Au (2020). (End)

			Binary strings (Lyndon words, cf. A102659):
a(0) = 1 = #{ "" },
a(1) = 2 = #{ "0", "1" },
a(2) = 1 = #{ "01" },
a(3) = 2 = #{ "001", "011" },
a(4) = 3 = #{ "0001", "0011", "0111" },
a(5) = 6 = #{ "00001", "00011", "00101", "00111", "01011", "01111" }.

Michael F. Barnsley, Fractals Everywhere, Academic Press, San Diego, 1988, page 171, Lemma 3.
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie. On the digraph defined by squaring mod m, when m has primitive roots. Congr. Numer. 82 (1991), 167-177.
P. J. Freyd and A. Scedrov, Categories, Allegories, North-Holland, Amsterdam, 1990. See 1.925.
M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983, pp. 65, 79.
Robert M. May, "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - N. J. A. Sloane, Mar 17 2019
Guy Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
M. R. Nester, (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in entries N0046 and N0287).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..3333 (terms 0..200 from T. D. Noe)
Per Alexandersson and Joakim Uhlin, Cyclic sieving, skew Macdonald polynomials and Schur positivity, arXiv:1908.00083 [math.CO], 2019.
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See p. 17.
Joerg Arndt, Matters Computational (The Fxtbook), pp.379-383, pp.843-845.
Kam Cheong Au, Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series, arXiv:2007.03957 [math.NT], 2020. See 3rd line of Table 1 (p. 6).
E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie, On a digraph defined by squaring modulo n, Fibonacci Quart. 30 (1992), 322-333.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Émilie Charlier, Manon Philibert, and Manon Stipulanti, Nyldon words, arXiv:1804.09735 [math.CO], 2018. Also J. Comb. Thy. A, 167 (2019), 60-90.
R. Church, Tables of irreducible polynomials for the first four prime moduli, Annals Math., 36 (1935), 198-209.
J. Demongeot, M. Noual and S. Sene, On the number of attractors of positive and negative threshold Boolean automata circuits, 2010 IEEE 24th Intl. Conf. Advan. Inf. Network. Appl. Workshops (WAINA), p 782-789.
Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, Conjugation, loop and closure invariants of the iterated-integrals signature, arXiv:2412.19670 [math.RA], 2024. See p. 6.
Bau-Sen Du, The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem, arXiv:0706.2297 [math.DS], 2007; Bull. Austral. Math. Soc. 31(1985), 89-103. Corrigendum: 32 (1985), 159.
S. V. Duzhin and D. V. Pasechnik, Groups acting on necklaces and sandpile groups, 2014. See page 85. - _N. J. A. Sloane_, Jun 30 2014
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
M. A. Harrison, On the classification of Boolean functions by the general linear and affine groups, J. Soc. Indust. Appl. Math. 12 (1964) 285-299.
A. Knopfmacher and M. E. Mays, Graph Compositions I: Basic enumeration, Integers 1 (2001), A4, eq. (1).
T. Laarhoven and B de Weger, The Collatz conjecture and De Bruijn graphs, arXiv preprint arXiv:1209.3495 [math.NT], 2012. - From _N. J. A. Sloane_, Dec 27 2012
J. C. Lagarias, The set of rational cycles for the 3x+1 problem, Acta Arithmetica, LVI (1990), pp. 33-53.
Piotr Laskawiec, Joint Spectral Radius with focus on pairs of 2 X 2 matrices, Ph. D. Dissertation, Penn. State Univ. (2025). See p. 55.
R. J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, sequence gamma_{2,j}^(T), arXiv:0903.2514 [math.NT], 2009-2011.
Ueli M. Maurer, Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs, Discrete applied mathematics 37 (1992): 421-436. See Table 1.
Romeo Meštrović, Different classes of binary necklaces and a combinatorial method for their enumerations, arXiv:1804.00992 [math.CO], 2018.
H. Meyn and W. Götz, Self-reciprocal polynomials over finite fields, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.
J.-F. Michon and P. Ravache, On different families of invariant irreducible polynomials over F_2, Finite fields & Applications 16 (2010) 163-174.
Hans Z. Munthe-Kaas and Jonatan Stava, Lie Admissible Triple Algebras: The Connection Algebra of Symmetric Spaces, arXiv:2306.15582 [math.DG], 2023.
Mathilde Noual, Dynamics of Circuits and Intersecting Circuits, in Language and Automata Theory and Applications, Lecture Notes in Computer Science, 2012, Volume 7183/2012, 433-444, ArXiv 1011.3930 [cs.DM]. - _N. J. A. Sloane_, Jul 07 2012
Cormac O'Sullivan, Topographs for binary quadratic forms and class numbers, arXiv:2408.14405 [math.NT], 2024. See p. 30.
George Petrides and Johannes Mykkeltveit, On the Classification of Periodic Binary Sequences into Nonlinear Complexity Classes, in Sequences and Their Applications SETA 2006, Lecture Notes in Computer Science, Volume 4086/2006, pp 209-222. [From _N. J. A. Sloane_, Jul 09 2009]
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Primitive and Irreducible Polynomials
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 2004, pages 219-240.
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
M. Waldschmidt, Lectures on Multiple Zeta Values, IMSC 2011.
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Eric Weisstein's World of Mathematics, Lyndon Word
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words
Index entries for "core" sequences

Column 2 of A074650.
Row sums of A051168, which gives the number of Lyndon words with fixed number of zeros and ones.
Euler transform is A000079.
See A058943 and A102569 for initial terms. See also A058947, A011260, A059966.
Irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058943, A058944, A058948, A058945, A058946. Primitive irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058947, A058949, A058952, A058950, A058951.
Cf. A000031 (n-bead necklaces but may have period dividing n), A014580, A046211, A046209, A006206-A006208, A038063, A060477, A103314.
Cf. A027750, A008683, A254040.
See also A102659 for the list of binary Lyndon words themselves.
Cf. A000010, A008683.

a001037 0 = 1
a001037 n = (sum $ map (\d -> (a000079 d) * a008683 (n `div` d)) $
                       a027750_row n) `div` n
-- Reinhard Zumkeller, Feb 01 2013

with(numtheory): A001037 := proc(n) local a,d; if n = 0 then RETURN(1); else a := 0: for d in divisors(n) do a := a+mobius(n/d)*2^d; od: RETURN(a/n); fi; end;

f[n_] := Block[{d = Divisors@ n}, Plus @@ (MoebiusMu[n/d]*2^d/n)]; Array[f, 32]

A001037(n)=if(n>1,sumdiv(n,d,moebius(d)*2^(n/d))/n,n+1) \\ Edited by M. F. Hasler, Jan 11 2016

{a(n)=polcoeff(1-sum(k=1,n,moebius(k)/k*log(1-2*x^k+x*O(x^n))),n)} \\ Paul D. Hanna, Oct 13 2010

a(n)=if(n>1,my(s);forstep(i=2^n+1,2^(n+1),2,s+=polisirreducible(Mod(1,2) * Pol(binary(i))));s,n+1) \\ Charles R Greathouse IV, Jan 26 2012

from sympy import divisors, mobius
def a(n): return sum(mobius(d) * 2**(n//d) for d in divisors(n))/n if n>1 else n + 1 # Indranil Ghosh, Apr 26 2017

For n >= 1:
a(n) = (1/n)*Sum_{d | n} mu(n/d)*2^d.
A000031(n) = Sum_{d | n} a(d).
2^n = Sum_{d | n} d*a(d).
a(n) = A027375(n)/n.
a(n) = A000048(n) + A051841(n).
For n > 1, a(n) = A059966(n) = A060477(n).
G.f.: 1 - Sum_{n >= 1} moebius(n)*log(1 - 2*x^n)/n, where moebius(n) = A008683(n). - Paul D. Hanna, Oct 13 2010
From Richard L. Ollerton, May 10 2021: (Start)
For n >= 1:
a(n) = (1/n)*Sum_{k=1..n} mu(gcd(n,k))*2^(n/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*Sum_{k=1..n} mu(n/gcd(n,k))*2^gcd(n,k)/phi(n/gcd(n,k)). (End)
a(n) ~ 2^n / n. - Vaclav Kotesovec, Aug 11 2021

Revised by N. J. A. Sloane, Jun 10 2012

A004111 Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).

Original entry on oeis.org

0, 1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6299, 14426, 33209, 76851, 178618, 416848, 976296, 2294224, 5407384, 12780394, 30283120, 71924647, 171196956, 408310668, 975662480, 2335443077, 5599508648, 13446130438, 32334837886, 77863375126, 187737500013, 453203435319, 1095295264857, 2649957419351

Offset: 0

N. J. A. Sloane

The nodes are unlabeled.
There is a natural correspondence between rooted identity trees and finitary sets (sets whose transitive closure is finite); each node represents a set, with the children of that node representing the members of that set. When the set corresponding to an identity tree is written out using braces, there is one set of braces for each node of the tree; thus a(n) is also the number of sets that can be made using n pairs of braces. - Franklin T. Adams-Watters, Oct 25 2011
Shifts left under WEIGH transform. - Franklin T. Adams-Watters, Jan 17 2007
Is this the sequence mentioned in the middle of page 355 of Motzkin (1948)? - N. J. A. Sloane, Jul 04 2015. Answer from David Broadhurst, Apr 06 2022: The answer is No. Motzkin was considering a sequence asymptotic to Catalan(n)/(4*n), namely A006082, which begins 1, 1, 1, 2, 3, 6, 12, 27, ... but he miscalculated and got 1, 1, 1, 2, 3, 6, 12, 25, ... instead! - N. J. A. Sloane, Apr 06 2022

			The 2 identity trees with 4 nodes are:
     O    O
    / \   |
   O   O  O
       |  |
       O  O
          |
          O
These correspond to the sets {{},{{}}} and {{{{}}}}.
G.f.: x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 12*x^7 + 25*x^8 + 52*x^9 + ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 330.
S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 301 and 562.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 64, Eq. (3.3.15); p. 80, Problem 3.10.
D. E. Knuth, Fundamental Algorithms, 3rd Ed., 1997, pp. 386-388.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..2500 (first 201 terms from T. D. Noe)
Joerg Arndt, All identity trees for n = 1..11.
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
A. Genitrini, Full asymptotic expansion for Polya structures, arXiv:1605.00837 [math.CO], May 03 2016, p. 8.
Bernhard Gittenberger, Emma Yu Jin, Michael Wallner, On the shape of random Pólya structures, arXiv|1707.02144 [math.CO], 2017-2018; Discrete Math., 341 (2018), 896-911.
Frank Harary and Geert Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503.
F. Harary, R. W. Robinson and A. J. Schwenk, Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 56.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
N. J. A. Sloane, Sketch showing trees with 2 through 6 nodes.
Index entries for sequences related to rooted trees

Cf. A000009, A000081, A000220, A196118, A196154, A196161, A227819.
Cf. A027750, A035056, A246169.
Column k=1 of A255517, A316074, A316101, A318757.

import Data.List (genericIndex)
a004111 = genericIndex a004111_list
a004111_list = 0 : 1 : f 1 [1] where
   f x zs = y : f (x + 1) (y : zs) where
            y = (sum $ zipWith (*) zs $ map g [1..]) `div` x
   g k = sum $ zipWith (*) (map (((-1) ^) . (+ 1)) $ reverse divs)
                           (zipWith (*) divs $ map a004111 divs)
                           where divs = a027750_row k
-- Reinhard Zumkeller, Apr 29 2014

A004111 := proc(n)
        spec := [ A, {A=Prod(Z,PowerSet(A))} ]:
        combstruct[count](spec, size=n) ;
end proc:
# second Maple program:
with(numtheory):
a:= proc(n) a(n):= `if`(n<2, n, add(a(n-k)*add(a(d)*d*
       (-1)^(k/d+1), d=divisors(k)), k=1..n-1)/(n-1))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jul 15 2014

s[ n_, k_ ] := s[ n, k ]=a[ n+1-k ]+If[ n<2k, 0, -s[ n-k, k ] ]; a[ 1 ]=1; a[ n_ ] := a[ n ]=Sum[ a[ i ]s[ n-1, i ]i, {i, 1, n-1} ]/(n-1); Table[ a[ i ], {i, 1, 30} ] (* Robert A. Russell *)
a[ n_] := If[ n < 2, Boole[n == 1], Nest[ CoefficientList[ Normal[ Times @@ (Table[1 + x^k, {k, Length@#}]^#) + x O[x]^Length@#], x] &, {}, n - 1][[n]]]; (* Michael Somos, Jul 10 2014 *)
a[n_] := a[n] = Sum[a[n-k]*Sum[a[d]*d*(-1)^(k/d+1),{d, Divisors[k]}], {k, 1, n-1}]/(n-1); a[0]=0; a[1]=1; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 02 2015 *)

N=66;  A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, (-1)^(k/d+1) * d * A[d]) * A[n-k+1] ) );
concat([0], A)
\\ Joerg Arndt, Jul 10 2014

Recurrence: a(n+1) = (1/n) * Sum_{k=1..n} ( Sum_{d|k} (-1)^(k/d+1) d*a(d) ) * a(n-k+1). - Mitchell Harris, Dec 02 2004
G.f. satisfies A(x) = x*exp(A(x) - A(x^2)/2 + A(x^3)/3 - A(x^4)/4 + ...). [Harary and Prins]
Also A(x) = Sum_{n >= 1} a(n)*x^n = x * Product_{n >= 1} (1+x^n)^a(n).
a(n) ~ c * d^n / n^(3/2), where d = A246169 = 2.51754035263200389079535..., c = 0.3625364233974198712298411097408713812865256408189512533230825639621448038... . - Vaclav Kotesovec, Aug 22 2014, updated Dec 26 2020

A038548 Number of divisors of n that are at most sqrt(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 2, 3, 1, 4, 1, 3, 2, 2, 2, 5, 1, 2, 2, 4, 1, 4, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 6, 1, 2, 3, 4, 2, 4, 1, 3, 2, 4, 1, 6, 1, 2, 3, 3, 2, 4, 1, 5, 3, 2, 1, 6, 2, 2, 2, 4, 1, 6, 2, 3, 2, 2, 2, 6, 1, 3, 3, 5, 1, 4, 1, 4, 4

Offset: 1

Tom Verhoeff, N. J. A. Sloane

Number of ways to arrange n identical objects in a rectangle, modulo rotation.
Number of unordered solutions of x*y = n. - Colin Mallows, Jan 26 2002
Number of ways to write n-1 as n-1 = x*y + x + y, 0 <= x <= y <= n. - Benoit Cloitre, Jun 23 2002
Also number of values for x where x+2n and x-2n are both squares (e.g., if n=9, then 18+18 and 18-18 are both squares, as are 82+18 and 82-18 so a(9)=2); this is because a(n) is the number of solutions to n=k(k+r) in which case if x=r^2+2n then x+2n=(r+2k)^2 and x-2n=r^2 (cf. A061408). - Henry Bottomley, May 03 2001
Also number of sums of sequences of consecutive odd numbers or consecutive even numbers including sequences of length 1 (e.g., 12 = 5+7 or 2+4+6 or 12 so a(12)=3). - Naohiro Nomoto, Feb 26 2002
Number of partitions whose consecutive parts differ by exactly two.
a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24=2^3*3 and 375=3*5^3 both have prime signature (3,1). - Christian G. Bower, Jun 06 2005
Also number of partitions of n such that if k is the largest part, then each of the parts 1,2,...,k-1 occurs exactly twice. Example: a(12)=3 because we have [3,3,2,2,1,1],[2,2,2,2,2,1,1] and [1,1,1,1,1,1,1,1,1,1,1,1]. - Emeric Deutsch, Mar 07 2006
a(n) is also the number of nonnegative integer solutions of the Diophantine equation 4*x^2 - y^2 = 16*n. For example, a(24)=4 because there are 4 solutions: (x,y) = (10,4), (11,10), (14,20), (25,46). - N-E. Fahssi, Feb 27 2008
a(n) is the number of even divisors of 2*n that are <= sqrt(2*n). - Joerg Arndt, Mar 04 2010
First differences of A094820. - John W. Layman, Feb 21 2012
a(n) = #{k: A027750(n,k) <= A000196(n)}; a(A008578(n)) = 1; a(A002808(n)) > 1. - Reinhard Zumkeller, Dec 26 2012
Row lengths of the tables in A161906 and A161908. - Reinhard Zumkeller, Mar 08 2013
Number of positive integers in the sequence defined by x_0 = n, x_(k+1) = (k+1)*(x_k-2)/(k+2) or equivalently by x_k = n/(k+1) - k. - Luc Rousseau, Mar 03 2018
Expanding the first comment: Number of rectangles with area n and integer side lengths, modulo rotation. Also number of 2D grids of n congruent squares, in a rectangle, modulo rotation (cf. A000005 for rectangles instead of squares; cf. A034836 for the 3D case). - Manfred Boergens, Jun 08 2021
Number of divisors of n that have an even number of prime divisors (counted with multiplicity), or in other words, number of terms of A028260 that divide n. - Antti Karttunen, Apr 17 2022

			a(4) = 2 since 4 = 2 * 2 = 4 * 1. Also A034178(4*4) = 2 since 16 = 4^2 - 0^2 = 5^2 - 3^2. - _Michael Somos_, May 11 2011
x + x^2 + x^3 + 2*x^4 + x^5 + 2*x^6 + x^7 + 2*x^8 + 2*x^9 + 2*x^10 + x^11 + ...

George E. Andrews and Kimmo Eriksson, Integer Partitions, Cambridge Univ. Press, 2004, page 18, exer. 21, 22.

T. D. Noe, Table of n, a(n) for n = 1..10000
Cristina Ballantine and Mircea Merca, New convolutions for the number of divisors, Journal of Number Theory, 2016, vol. 170, pp. 17-34.
Christopher Briggs, Y. Hirano, and H. Tsutsui, Positive Solutions to Some Systems of Diophantine Equations, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.4.
S.-H. Cha, E. G. DuCasse, and L. V. Quintas, Graph invariants based on the divides relation and ordered by prime signatures, arXiv:1405.5283 [math.NT], 2014, (2.27).
Madeline Locus Dawsey, Matthew Just and Robert Schneider, A "supernormal" partition statistic, arXiv:2107.14284 [math.NT], 2021. See Table 2 p. 21.
T. Verhoeff, Rectangular and Trapezoidal Arrangements, J. Integer Sequences, Vol. 2 (1999), Article 99.1.6.
Index entries for sequences computed from exponents in factorization of n.

Different from A068108. Records give A038549, A004778, A086921.
Cf. A000005, A001620, A028260, A056924, A072670, A094820, A161841, A108504.
Cf. A066839, A033676, row sums of A303300.
Inverse Möbius transform of A065043.
Cf. A244664 (Dgf at s=2), A244665 (Dgf at s=3).

a038548 n = length $ takeWhile (<= a000196 n) $ a027750_row n
-- Reinhard Zumkeller, Dec 26 2012
(C#)
int A038548(int n)  {
    System.Numerics.BigInteger erg = 0, i;
    for (i = 1; i * i <= n; i++)
        if (n % i == 0) erg++;
    return (int)erg;
} // Frank Hollstein, Jan 08 2023

with(numtheory): A038548 := n->ceil(sigma[0](n)/2);

Table[ Floor[ (DivisorSigma[0, n] + 1)/2], {n, 105}] (* Robert G. Wilson v, Mar 02 2009 *)
Table[Count[Divisors[n],?(#<=Sqrt[n]&)],{n,110}] (* _Harvey P. Dale, Jul 10 2021 *)
Table[Sum[If[n > k*(k-1), 1, 0], {k, Divisors[n]}], {n, 1, 100}] (* Vaclav Kotesovec, Oct 22 2024 *)

{a(n) = if( n<1, 0, sumdiv(n, d, d*d <= n))} /* Michael Somos, Jan 25 2005 */

a(n)=ceil(numdiv(n)/2) \\ Charles R Greathouse IV, Sep 28 2012

from sympy import divisor_count
def A038548(n): return divisor_count(n)+1>>1 # Chai Wah Wu, Dec 19 2023

a(n) = ceiling(d(n)/2), where d(n) = number of divisors of n (A000005).
a(2k) = A034178(2k) + A001227(k). a(2k+1) = A034178(2k+1). - Naohiro Nomoto, Feb 26 2002
G.f.: Sum_{k>=1} x^(k^2)/(1-x^k). - Jon Perry, Sep 10 2004
Dirichlet g.f.: (zeta(s)^2 + zeta(2*s))/2. - Christian G. Bower, Jun 06 2005 [corrected by Vaclav Kotesovec, Aug 19 2019]
a(n) = (A000005(n) + A010052(n))/2. - Omar E. Pol, Jun 23 2009
a(n) = A034178(4*n). - Michael Somos, May 11 2011
2*a(n) = A161841(n). - R. J. Mathar, Mar 07 2021
a(n) = A000005(n) - A056924(n) = A056924(n) + A010052(n) = Sum_{d|n} A065043(d). - Antti Karttunen, Apr 17 2022
Sum_{k=1..n} a(k) ~ n*log(n)/2 + (gamma - 1/2)*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 27 2022

A003238 Number of rooted trees with n vertices in which vertices at the same level have the same degree.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 10, 11, 16, 19, 26, 27, 40, 41, 53, 61, 77, 78, 104, 105, 134, 147, 175, 176, 227, 233, 275, 294, 350, 351, 438, 439, 516, 545, 624, 640, 774, 775, 881, 924, 1069, 1070, 1265, 1266, 1444, 1521, 1698, 1699

Offset: 1

N. J. A. Sloane

Also, number of sequences of positive integers b_1, b_2, ..., b_k such that 1 + b_1*(1 + b_2*(...(1 + b_k) ... )) = n. If you take mu(b_1)*mu(b_2)*...*mu(b_k) for each sequence you get 1's 0's and -1's. Add them up and you get the terms for A007554. - Christian G. Bower, Oct 15 1998
Note that this applies also to planar rooted trees and other similar objects (mountain ranges, parenthesizations) encoded by A014486. - Antti Karttunen, Sep 07 2000
Equals sum of (n-1)-th row terms of triangle A152434. - Gary W. Adamson, Dec 04 2008
Equals the eigensequence of A051731, the inverse binomial transform. - Gary W. Adamson, Dec 26 2008
From Emeric Deutsch, Aug 18 2012: (Start)
The considered rooted trees are called generalized Bethe trees; in the Goldberg-Livshitz reference they are called uniform trees.
Also, a(n) = number of partitions of n-1 in which each part is divisible by the next. Example: a(5)=5 because we have 4, 31, 22, 211, and 1111.
There is a simple bijection between generalized Bethe trees with n+1 vertices and partitions of n in which each part is divisible by the next (the parts are given by the number of edges at the successive levels). We have the correspondences: number of edges --- sum of parts; root degree --- last part; number of leaves --- first part; height --- number of parts. (End)
a(n+1) = a(n) + 1 if and only if n is prime. - Jon Perry, Nov 24 2012
According to the MathOverflow link, log(a(n)) ~ log(4)*log(n)^2, and a more precise asymptotic expansion is similar to that of A018819 and hence A000123, so the conjecture in the Formula section is partly correct. - Andrey Zabolotskiy, Jan 22 2017

			a(4) = 3 because we have the path P(4), the tree Y, and the star \|/ . - _Emeric Deutsch_, Aug 18 2012
The planted achiral trees with up to 7 nodes are:
 1  -
 1  (-)
 2  (--),     ((-))
 3  (---),    ((--)),      (((-)))
 5  (----),   ((-)(-)),    ((---)),    (((--))),     ((((-))))
 6  (-----),  ((----)),    (((-)(-))), (((---))),    ((((--)))), (((((-)))))
10 (------), ((-)(-)(-)), ((--)(--)), (((-))((-))), ((-----)),  (((----))), ((((-)(-)))), ((((---)))), (((((--))))), ((((((-)))))). - _Gus Wiseman_, Jan 12 2017

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Robert Israel, Table of n, a(n) for n = 1..10000
G. Gati, F. Harary, and R. W. Robinson, Line colored trees with extendable automorphisms, Acta Mathematica Scientia 2.1 (1982), 105-110. (Annotated scanned copy)
M. K. Goldberg and E. M. Livshits, On minimal universal trees, Mathematical Notes of the Acad. of Sciences of the USSR, 4, 1968, 713-717 (translation from the Russian Mat. Zametki 4 1968 371-379).
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335. (Annotated scanned copy)
B. S. Kochkarev, Absolutely symmetric trees and complexity of natural number, arXiv:1205.0344 [math.CO], 2012.
MathOverflow, Are the asymptotics of A003238 known?
O. Rojo, Spectra of weighted generalized Bethe trees joined at the root, Linear Algebra and its Appl., 428, 2008, 2961-2979.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Transforms
Gus Wiseman, Planted achiral trees n=1..10.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A007439, A007554, A057546, A152434, A051731, A002033, A027750, A281487, A000123.
Row sums of A122934 (offset by 1).
Cf. A004111, A280994.

a003238 n = a003238_list !! (n-1)
a003238_list = 1 : f 1 where
   f x = (sum (map a003238 $ a027750_row x)) : f (x + 1)
-- Reinhard Zumkeller, Dec 20 2014

a = new Array();
for (i = 1; i < 50; i++) a[i] = 1;
for (i = 3; i < 50; i++) for (j = 2; j < i; j++) if (i % j == 1) a[i] += a[j];
document.write(a + "
"); // Jon Perry, Nov 20 2012

with(numtheory): aa := proc (n) if n = 0 then 1 else add(aa(divisors(n)[i]-1), i = 1 .. tau(n)) end if end proc: a := proc (n) options operator, arrow: aa(n-1) end proc: seq(a(n), n = 1 .. 48); # Emeric Deutsch, Aug 18 2012
A003238:= proc(n) option remember; uses numtheory; add(A003238(m),m=divisors(n-1)) end proc;
A003238(1):= 1;
[seq(A003238(n),n=1..48)]; # Robert Israel, Mar 10 2014

(* b = A068336 *) b[1] = 1; b[n_] := b[n] = 1 + Sum[b[k], {k, Divisors[n-1]}]; a[n_] := b[n]/2; a[1] = 1; Table[ a[n], {n, 1, 48}] (* Jean-François Alcover, Dec 20 2011, after Ralf Stephan *)
achi[n_]:=If[n===1,1,Total[achi/@Divisors[n-1]]];Array[achi,50] (* Gus Wiseman, Jan 12 2017 *)

seq(n) = {my(v=vector(n)); v[1]=1; for(i=2, n, v[i]=sumdiv(i-1, d, v[d])); v} \\ Andrew Howroyd, Jun 08 2025

Shifts one place left under inverse Moebius transform: a(n+1) = Sum_{k|n} a(k).
Conjecture: log(a(n)) is asymptotic to c*log(n)^2 where 0.4 < c < 0.5 - Benoit Cloitre, Apr 13 2004
For n > 1, a(n) = (1/2) * A068336(n) and Sum_{k = 1..n} a(k) = A003318(n). - Ralf Stephan, Mar 27 2004
Generating function P(x) for the sequence with offset 2 obeys P(x) = x^2*(1 + Sum_{n >= 1} P(x^n)/x^n). [Harary & Robinson]. - R. J. Mathar, Sep 28 2011
a(n) = 1 + sum of a(i) such that n == 1 (mod i). - Jon Perry, Nov 20 2012
From Ilya Gutkovskiy, Apr 28 2019: (Start)
G.f.: x * (1 + Sum_{n>=1} a(n)*x^n/(1 - x^n)).
L.g.f.: -log(Product_{n>=1} (1 - x^n)^(a(n)/n)) = Sum_{n>=1} a(n+1)*x^n/n. (End)

Description improved by Christian G. Bower, Oct 15 1998

A017665 Numerator of sum of reciprocals of divisors of n.

Original entry on oeis.org

1, 3, 4, 7, 6, 2, 8, 15, 13, 9, 12, 7, 14, 12, 8, 31, 18, 13, 20, 21, 32, 18, 24, 5, 31, 21, 40, 2, 30, 12, 32, 63, 16, 27, 48, 91, 38, 30, 56, 9, 42, 16, 44, 21, 26, 36, 48, 31, 57, 93, 24, 49, 54, 20, 72, 15, 80, 45, 60, 14, 62, 48, 104, 127, 84, 24, 68, 63, 32, 72, 72, 65, 74, 57

Offset: 1

N. J. A. Sloane

Sum_{d|n} 1/d^k is equal to sigma_k(n)/n^k. So sequences A017665-A017712 also give the numerators and denominators of sigma_k(n)/n^k for k = 1..24. The power sums sigma_k(n) are in sequences A000203 (k=1), A001157-A001160 (k=2,3,4,5), A013954-A013972 for k = 6,7,...,24. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 05 2001
Numerators of coefficients in expansion of Sum_{n >= 1} x^n / (n*(1-x^n)) = Sum_{n >= 1} log(1/(1-x^n)).
The primes in this sequence, in order of appearance (without multiplicity), begin: 3, 7, 2, 13, 31, 5, 127. The first occurrence of prime(k) = a(n) for k = 1, 2, 3, ... is at n = 6, 2, 24, 4, 35640, 9, 297600, 588, ... - Jonathan Vos Post, Apr 02 2011
With amicable numbers, we have a(A002025(n)) = a(A002046(n)). - Michel Marcus, Dec 29 2013
Numerator of sigma(n)/n = A000203(n)/n. See A239578(n) - the smallest number k such that a(k) = n. - Jaroslav Krizek, Sep 23 2014

			1, 3/2, 4/3, 7/4, 6/5, 2, 8/7, 15/8, 13/9, 9/5, 12/11, 7/3, 14/13, 12/7, 8/5, 31/16, ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 162, #16, (6), 4th formula.

T. D. Noe, Table of n, a(n) for n = 1..10000
Paul A. Weiner, The abundancy ratio, a measure of perfection, Math. Mag. 73 (4) (2000) 307-310.
Eric Weisstein's World of Mathematics, Abundancy.

Cf. A000203, A002025, A002046, A013661, A013954-A013972, A017666 (denominators), A027750, A239578.

import Data.Ratio ((%), numerator)
a017665 = numerator . sum . map (1 %) . a027750_row
-- Reinhard Zumkeller, Apr 06 2012

[Numerator(DivisorSigma(1,n)/n): n in [1..50]]; // G. C. Greubel, Nov 08 2018

with(numtheory): seq(numer(sigma(n)/n), n=1..74) ; # Zerinvary Lajos, Jun 04 2008

Numerator[DivisorSigma[-1,Range[80]]] (* Harvey P. Dale, May 31 2013 *)
Table[Numerator[DivisorSigma[1, n]/n], {n, 1, 50}] (* G. C. Greubel, Nov 08 2018 *)

a(n)=sigma(n)/gcd(n, sigma(n)) \\ Charles R Greathouse IV, Feb 11 2011

a(n)=numerator(sigma(n,-1)) \\ Charles R Greathouse IV, Apr 04 2011

from math import gcd
from sympy import divisor_sigma
def A017665(n): return (m:=divisor_sigma(n))//gcd(m,n) # Chai Wah Wu, Mar 20 2023

a(n) = sigma(n)/gcd(n, sigma(n)). - Jon Perry, Jun 29 2003
Dirichlet g.f.: zeta(s)*zeta(s+1) [for fraction A017665/A017666]. - Franklin T. Adams-Watters, Sep 11 2005
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k)/A017666(k) = Pi^2/6 (A013661). - Amiram Eldar, Nov 21 2022

A005153 Practical numbers: positive integers m such that every k <= sigma(m) is a sum of distinct divisors of m. Also called panarithmic numbers.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72, 78, 80, 84, 88, 90, 96, 100, 104, 108, 112, 120, 126, 128, 132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, 196, 198, 200, 204, 208, 210, 216, 220, 224, 228, 234, 240, 252

Offset: 1

N. J. A. Sloane

Equivalently, positive integers m such that every number k <= m is a sum of distinct divisors of m.
2^r is a member for all r as every number < = sigma(2^r) = 2^(r+1)-1 is a sum of a distinct subset of divisors {1, 2, 2^2, ..., 2^m}. - Amarnath Murthy, Apr 23 2004
Also, numbers m such that A030057(m) > m. This is a consequence of the following theorem (due to Stewart), found at the McLeman link: An integer m >= 2 with factorization Product_{i=1..k} p_i^e_i with the p_i in ascending order is practical if and only if p_1 = 2 and, for 1 < i <= k, p_i <= sigma(Product_{j < i} p_j^e_j) + 1. - Franklin T. Adams-Watters, Nov 09 2006
Practical numbers first appear in Srinivasan's short paper, which contains terms up to 200. Let m be a practical number. He states that (1) if m>2, m is a multiple of 4 or 6; (2) sigma(m) >= 2*m-1 (A103288); and (3) 2^t*m is practical. He also states that highly composite numbers (A002182), perfect numbers (A000396), and primorial numbers (A002110) are practical. - T. D. Noe, Apr 02 2010
Conjecture: The sequence a(n)^(1/n) (n=3,4,...) is strictly decreasing to the limit 1. - Zhi-Wei Sun, Jan 12 2013
Conjecture: For any positive rational number r, there are finitely many pairwise distinct practical numbers q(1)..q(k) such that r = Sum_{j=1..k} 1/q(j). For example, 2 = 1/1 + 1/2 + 1/4 + 1/6 + 1/12 with 1, 2, 4, 6 and 12 all practical, and 10/11 = 1/2 + 1/4 + 1/8 + 1/48 + 1/132 + 1/176 with 2, 4, 8, 48, 132 and 176 all practical. - Zhi-Wei Sun, Sep 12 2015
Analogous with the {1 union primes} (A008578), practical numbers form a complete sequence. This is because it contains all powers of 2 as a subsequence. - Frank M Jackson, Jun 21 2016
Sun's 2015 conjecture on the existence of Egyptian fractions with practical denominators for any positive rational number is true. See the link "Egyptian fractions with practical denominators". - David Eppstein, Nov 20 2016
Conjecture: if all divisors of m are 1 = d_1 < d_2 < ... < d_k = m, then m is practical if and only if d_(i+1)/d_i <= 2 for 1 <= i <= k-1. - Jianing Song, Jul 18 2018
The above conjecture is incorrect. The smallest counterexample is 78 (for which one of these quotients is 13/6; see A174973). m is practical if and only if the divisors of m form a complete subsequence. See Wikipedia links. - Frank M Jackson, Jul 25 2018
Reply to the comment above: Yes, and now I can show the opposite: The largest value of d_(i+1)/d_i is not bounded for practical numbers. Note that sigma(n)/n is not bounded for primorials, and primorials are practical numbers. For any constant c >= 2, let k be a practical number such that sigma(k)/k > 2c. By Bertrand's postulate there exists some prime p such that c*k < p < 2c*k < sigma(k), so k*p is a practical number with consecutive divisors k and p where p/k > c. For example, for k = 78 we have 13/6 > 2, and for 97380 we have 541/180 > 3. - Jianing Song, Jan 05 2019
Erdős (1950) and Erdős and Loxton (1979) proved that the asymptotic density of practical numbers is 0. - Amiram Eldar, Feb 13 2021
Let P(x) denote the number of practical numbers up to x. P(x) has order of magnitude x/log(x) (see Saias 1997). Moreover, we have P(x) = c*x/log(x) + O(x/(log(x))^2), where c = 1.33607... (see Weingartner 2015, 2020 and Remark 1 of Pomerance & Weingartner 2021). As a result, a(n) = k*n*log(n*log(n)) + O(n), where k = 1/c = 0.74846... - Andreas Weingartner, Jun 26 2021
From Hal M. Switkay, Dec 22 2022: (Start)
Every number of least prime signature (A025487) is practical, thereby including two classes of number mentioned in Noe's comment. This follows from Stewart's characterization of practical numbers, mentioned in Adams-Watters's comment, combined with Bertrand's postulate (there is a prime between every natural number and its double, inclusive).
Also, the first condition in Stewart's characterization (p_1 = 2) is equivalent to the second condition with index i = 1, given that an empty product is equal to 1. (End)
Conjecture: every odd number, beginning with 3, is the sum of a prime number and a practical number. Note that this conjecture occupies the space between the unproven Goldbach conjecture and the theorem that every even number, beginning with 2, is the sum of two practical numbers (Melfi's 1996 proof of Margenstern's conjecture). - Hal M. Switkay, Jan 28 2023

H. Heller, Mathematical Buds, Vol. 1, Chap. 2, pp. 10-22, Mu Alpha Theta OK, 1978.
Malcolm R. Heyworth, More on Panarithmic Numbers, New Zealand Math. Mag., Vol. 17 (1980), pp. 28-34 [ ISSN 0549-0510 ].
Ross Honsberger, Mathematical Gems, M.A.A., 1973, p. 113.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A. K. Srinivasan, Practical numbers, Current Science, 17 (1948), 179-180.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 146-147.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Thomas Bloom, Problem 18, Erdős Problems.
Wayne Dymacek, Letter to N. J. A. Sloane, Jun 15 1978.
David Eppstein, Egyptian fractions with practical denominators, Nov 20, 2016
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
Paul Erdős, On a Diophantine equation (in Hungarian, with Russian and English summaries), Mat. Lapok, Vol. 1 (1950), pp. 192-210.
Paul Erdős and J. H. Loxton, Some problems in partitio numerorum, Journal of the Australian Mathematical Society, Vol. 27, No. 3 (1979), pp. 319-331.
James Grimes and Brady Haran, Practical Numbers, Numberphile video (2023).
Harvey J. Hindin, Quasipractical numbers, IEEE Communications Magazine, Vol. 18, No. 2 (March 1980), pp. 41-45.
Paolo Leonetti and Carlo Sanna, Practical numbers among the binomial coefficients, Journal of Number Theory, Vol. 207 (2020), pp. 145-155; arXiv preprint, arXiv:1905.12023 [math.NT], 2019.
Maurice Margenstern, Sur les nombres pratiques, (in French), Groupe d'étude en théorie analytique des nombres, 1 (1984-1985), Exposé No. 21, 13 p.
Maurice Margenstern, Les nombres pratiques: théorie, observations et conjectures, Journal of Number Theory, Volume 37, Issue 1 (January 1991), pp. 1-36.
C. McLeman, Practical number, PlanetMath.org.
Giuseppe Melfi, On two conjectures about practical numbers, J. Number Theory, Vol. 56, No. 1 (1996), pp. 205-210 [MR96i:11106].
Giuseppe Melfi, On certain positive integer sequences, arXiv:0404555 [math.NT], 2004.
Giuseppe Melfi, A survey on practical numbers, Rend. Sem. Mat. Univ. Politec. Torino, Vol. 53, No. 4 (1995), pp. 347-359.
Giuseppe Melfi, Practical Numbers (old link).
Paul Pollack and Lola Thompson, Practical pretenders, arXiv:1201.3168 [math.NT], Jan 16 2012.
Carl Pomerance, Lola Thompson and Andreas Weingartner, On integers n for which X^n-1 has a divisor of every degree, arXiv:1511.03357 [math.NT], 2015.
Carl Pomerance and Andreas Weingartner, On primes and practical numbers, Ramanujan J. (2021); arXiv preprint, arXiv:2007.11062 [math.NT], 2020.
Eric Saias, Entiers à diviseurs denses 1, J. Number Theory, Vol. 62, No. 1 (1997), pp. 163-191; uses this definition.
Carlo Sanna, Practical central binomial coefficients, arXiv:2004.05376 [math.NT], 2020.
Sai Teja Somu, Ting Hon Stanford Li, and Andrzej Kukla, On Some Results on Practical Numbers, INTEGERS, Volume 23, A68, 2023 [MR4643065].
Sai Teja Somu and Duc Van Khanh Tran, On Sums of Practical Numbers and Polygonal Numbers, arXiv:2403.13533 [math.NT], 2024.
A. K. Srinivasan, Practical numbers, Current Science, 17 (1948), 179-180.
B. M. Stewart, Sums of distinct divisors, Amer. J. Math., Vol. 76, No. 4 (1954), pp. 779-785 [MR64800]
Zhi-Wei Sun, A conjecture on unit fractions involving primes, preprint, 2015.
Terence Tao, Erdős problem database, see entry no. 18.
Peter Taylor, Table of n, a(n) for n = 1..1000000.
Andreas Weingartner, Practical numbers and the distribution of divisors, The Quarterly Journal of Mathematics, Vol. 66, No. 2 (2015), pp. 743-758; arXiv preprint, arXiv:1405.2585 [math.NT], 2014-2015.
Andreas Weingartner, The constant factor in the asymptotic for practical numbers, Int. J. Number Theory, 16 (2020), no. 3, 629-638; arXiv preprint, arXiv:1906.07819 [math.NT], 2019.
Andreas Weingartner, Uniform distribution of alpha*n modulo one for a family of integer sequences, arXiv:2303.16819 [math.NT], 2023.
Eric Weisstein's World of Mathematics, Practical Number.
Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - _N. J. A. Sloane_, May 20 2023]
Wikipedia, Practical number.
Robert G. Wilson v, Letter to N. J. A. Sloane, date unknown.

Subsequence of A103288.
Cf. A002093, A007620 (second definition), A030057, A033630, A119348, A174533, A174973.
Cf. A027750.

a005153 n = a005153_list !! (n-1)
a005153_list = filter (\x -> all (p $ a027750_row x) [1..x]) [1..]
   where p _  0 = True
         p [] _ = False
         p ds'@(d:ds) m = d <= m && (p ds (m - d) || p ds m)
-- Reinhard Zumkeller, Feb 23 2014, Oct 27 2011

isA005153 := proc(n)
    local ifs,pprod,p,i ;
    if n = 1 then
        return true;
    elif type(n,'odd') then
        return false ;
    end if;
    # not using ifactors here directly because no guarantee primes are sorted...
    ifs := ifactors(n)[2] ;
    pprod := 1;
    for p in sort(numtheory[factorset](n) ) do
        for i in ifs do
            if op(1,i) = p then
                if p > 2 and p > 1+numtheory[sigma](pprod) then
                    return false ;
                end if;
                pprod := pprod*p^op(2,i) ;
            end if;
        end do:
    end do:
    return true ;
end proc:
for n from 1 to 300 do
    if isA005153(n)  then
        printf("%d,",n) ;
    end if;
end do: # R. J. Mathar, Jul 07 2023

PracticalQ[n_] := Module[{f,p,e,prod=1,ok=True}, If[n<1 || (n>1 && OddQ[n]), False, If[n==1, True, f=FactorInteger[n]; {p,e} = Transpose[f]; Do[If[p[[i]] > 1+DivisorSigma[1,prod], ok=False; Break[]]; prod=prod*p[[i]]^e[[i]], {i,Length[p]}]; ok]]]; Select[Range[200], PracticalQ] (* T. D. Noe, Apr 02 2010 *)

is_A005153(n)=bittest(n,0) && return(n==1); my(P=1); n && !for(i=2,#n=factor(n)~,n[1,i]>1+(P*=sigma(n[1,i-1]^n[2,i-1])) && return) \\ M. F. Hasler, Jan 13 2013

from sympy import factorint
def is_A005153(n):
    if n & 1: return n == 1
    f = factorint(n) ; P = (2 << f.pop(2)) - 1
    for p in f: # factorint must have prime factors in increasing order
        if p > 1 + P: return
        P *= p**(f[p]+1)//(p-1)
    return True # M. F. Hasler, Jan 02 2023

from sympy import divisors;from more_itertools import powerset
[i for i in range(1,253) if (lambda x:len(set(map(sum,powerset(x))))>sum(x))(divisors(i))] # Nicholas Stefan Georgescu, May 20 2023

Weingartner proves that a(n) ~ k*n log n, strengthening an earlier result of Saias. In particular, a(n) = k*n log n + O(n log log n). - Charles R Greathouse IV, May 10 2013

More precisely, a(n) = k*n*log(n*log(n)) + O(n), where k = 0.74846... (see comments). - Andreas Weingartner, Jun 26 2021

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 09 2004
Erroneous comment removed by T. D. Noe, Nov 14 2010
Definition changed to exclude n = 0 explicitly by M. F. Hasler, Jan 19 2013

A272919 Numbers of the form 2^(n-1)(2^(nm)-1)/(2^n-1), n >= 1, m >= 1.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 10, 15, 16, 31, 32, 36, 42, 63, 64, 127, 128, 136, 170, 255, 256, 292, 511, 512, 528, 682, 1023, 1024, 2047, 2048, 2080, 2184, 2340, 2730, 4095, 4096, 8191, 8192, 8256, 10922, 16383, 16384, 16912, 18724, 32767, 32768, 32896, 34952, 43690, 65535, 65536, 131071

Offset: 1

Ivan Neretin, May 10 2016

nonn

In other words, numbers whose binary representation consists of one or more repeating blocks with only one 1 in each block.
Also, fixed points of the permutations A139706 and A139708.
Each a(n) is a term of A064896 multiplied by some power of 2. As such, this sequence must also be a subsequence of A125121.
Also the numbers that uniquely index a Haar graph (i.e., 5 and 6 are not in the sequence since H(5) is isomorphic to H(6)). - Eric W. Weisstein, Aug 19 2017
From Gus Wiseman, Apr 04 2020: (Start)
The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. This sequence lists all positive integers k such that the k-th composition in standard order is constant. For example, the sequence together with the corresponding constant compositions begins:
()                  136: (4,4)
(1)                 170: (2,2,2,2)
(2)                 255: (1,1,1,1,1,1,1,1)
(1,1)               256: (9)
(3)                 292: (3,3,3)
(1,1,1)             511: (1,1,1,1,1,1,1,1,1)
(4)                 512: (10)
(2,2)               528: (5,5)
(1,1,1,1)           682: (2,2,2,2,2)
(5)                1023: (1,1,1,1,1,1,1,1,1,1)
(1,1,1,1,1)        1024: (11)
(6)                2047: (1,1,1,1,1,1,1,1,1,1,1)
(3,3)              2048: (12)
(2,2,2)            2080: (6,6)
(1,1,1,1,1,1)      2184: (4,4,4)
(7)                2340: (3,3,3,3)
(1,1,1,1,1,1,1)    2730: (2,2,2,2,2,2)
(8)                4095: (1,1,1,1,1,1,1,1,1,1,1,1)
(End)

Ivan Neretin, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Haar Graph

Cf. A064896, A139708.
Cf. A137706 (smallest number indexing a new Haar graph).
Compositions in standard order are A066099.
Strict compositions are ranked by A233564.
Cf. A000120, A027750, A070939, A098504, A124767, A164894, A228351, A238279.

N:= 10^6: # to get all terms <= N
R:= select(`<=`,{seq(seq(2^(n-1)*(2^(n*m)-1)/(2^n-1), m = 1 .. ilog2(2*N)/n), n = 1..ilog2(2*N))},N):
sort(convert(R,list)); # Robert Israel, May 10 2016

Flatten@Table[d = Reverse@Divisors[n]; 2^(d - 1)*(2^n - 1)/(2^d - 1), {n, 17}]

From Gus Wiseman, Apr 04 2020: (Start)
A333381(a(n)) = A027750(n).
For n > 0, A124767(a(n)) = 1.
If n is a power of two, A333628(a(n)) = 0, otherwise = 1.
A333627(a(n)) is a power of 2.
(End)

A007425 d_3(n), or tau_3(n), the number of ordered factorizations of n as n = r s t.

Original entry on oeis.org

1, 3, 3, 6, 3, 9, 3, 10, 6, 9, 3, 18, 3, 9, 9, 15, 3, 18, 3, 18, 9, 9, 3, 30, 6, 9, 10, 18, 3, 27, 3, 21, 9, 9, 9, 36, 3, 9, 9, 30, 3, 27, 3, 18, 18, 9, 3, 45, 6, 18, 9, 18, 3, 30, 9, 30, 9, 9, 3, 54, 3, 9, 18, 28, 9, 27, 3, 18, 9, 27, 3, 60, 3, 9, 18, 18, 9, 27, 3, 45, 15, 9, 3, 54, 9, 9, 9, 30, 3

Offset: 1

N. J. A. Sloane, May 24 1994

Let n = Product p_i^e_i. Tau (A000005) is tau_2, this sequence is tau_3, A007426 is tau_4, where tau_k(n) (also written as d_k(n)) = Product_i binomial(k-1+e_i, k-1) is the k-th Piltz function. It gives the number of ordered factorizations of n as a product of k terms. - Len Smiley
Inverse Möbius transform applied twice to all 1's sequence.
A085782 gives the range of values of this sequence. - Matthew Vandermast, Jul 12 2004
Appears to equal the number of plane partitions of n that can be extended in exactly 3 ways to a plane partition of n+1 by adding one element. - Wouter Meeussen, Sep 11 2004
Number of divisors of n's divisors. - Lekraj Beedassy, Sep 07 2004
Number of plane partitions of n that can be extended in exactly 3 ways to a plane partition of n+1 by adding one element. If the partition is not a box, there is a minimal i+j where b_{i,j} != b_{1,1} and an element can be added there. - Franklin T. Adams-Watters, Jun 14 2006
Equals row sums of A127170. - Gary W. Adamson, May 20 2007
Equals A134577 * [1/1, 1/2, 1/3, ...]. - Gary W. Adamson, Nov 02 2007
Equals row sums of triangle A143354. - Gary W. Adamson, Aug 10 2008
a(n) is congruent to 1 (mod 3) if n is a perfect cube, otherwise a(n) is congruent to 0 (mod 3). - Geoffrey Critzer, Mar 20 2015
Also row sums of A195050. - Omar E. Pol, Nov 26 2015
Number of 3D grids of n congruent boxes with three different edge lengths, in a box, modulo rotation (cf. A034836 for cubes instead of boxes and A140773 for boxes with two different edge lengths; cf. A000005 for the 2D case). - Manfred Boergens, Apr 06 2021
Number of ordered pairs of divisors of n, (d1,d2) with d1<=d2, such that d1|d2. - Wesley Ivan Hurt, Mar 22 2022

			a(6) = 9; the divisors of 6 are {1,2,3,6} and the numbers of divisors of these divisors are 1, 2, 2, and 4. Adding them, we get 9 as a result.
Also, since 6 is a squarefree number, the formula from Herrero can be used to obtain the result: a(6) = 3^omega(6) = 3^2 = 9. - _Wesley Ivan Hurt_, May 30 2014

M. N. Huxley, Area, Lattice Points and Exponential Sums, Oxford, 1996; p. 239.
A. Ivic, The Riemann Zeta-Function, Wiley, NY, 1985, see p. xv.
Paul J. McCarthy, Introduction to Arithmetical Functions, Springer, 1986.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
R. Eisinga, R. Breitling, and T. Heskes, The exact probability distribution of the rank product statistics for replicated experiments, FEBS Letters, 2013, 587: 677-682, doi:10.1016/j.febslet.2013.01.037
Karin Cvetko-Vah, Michael Kinyon, Jonathan Leech, and Tomaž Pisanski, Regular Antilattices, arXiv:1911.02858 [math.RA], 2019.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Adolf Piltz, Ueber das Gesetz, nach welchem die mittlere Darstellbarkeit der natürlichen Zahlen als Produkte einer gegebenen Anzahl Faktoren mit der Grösse der Zahlen wächst, Doctoral Dissertation, Friedrich-Wilhelms-Universität zu Berlin, 1881; the k-th Piltz function tau_k(n) is denoted by phi(n,k) and its recurrence and Dirichlet series appear on p. 6.
N. J. A. Sloane, Transforms.
Qingfeng Sun and Deyu Zhang, Sums of the triple divisor function over values of a ternary quadratic form, arXiv:1510.06170 [math.NT], 2015.
E. C. Titchmarsh, Some problems in the analytic theory of numbers, The Quarterly Journal of Mathematics 1 (1942): 129-152.
Wikipedia, Adolf Piltz.

Cf. A000005 (Mobius transform), A007426 (inverse Mobius transform), A061201 (partial sums), A127270, A143354, A027750, A007428 (Dirichlet inverse), A175596.
Column k=3 of A077592.
Additional cross-references mentioned in a comment: A034836, A038548, A140733.

a007425 = sum . map a000005 . a027750_row
-- Reinhard Zumkeller, Feb 16 2012

f:=proc(n) local t1,i,j,k; t1:=0; for i from 1 to n do for j from 1 to n do for k from 1 to n do if i*j*k = n then t1:=t1+1; fi; od: od: od: t1; end;
A007425 := proc(n) local e,j; e := ifactors(n)[2]: product(binomial(2+e[j][2],2), j=1..nops(e)); end; # Len Smiley

f[n_] := Plus @@ DivisorSigma[0, Divisors[n]]; Table[ f[n], {n, 90}] (* Robert G. Wilson v, Sep 13 2004 *)
SetAttributes[tau, Listable]; tau[1, n_] := 1; tau[k_, n_] := Plus @@ (tau[k-1, Divisors[n]]); Table[tau[3, n], {n, 100}] (* Enrique Pérez Herrero, Nov 08 2009 *)
Table[Sum[DivisorSigma[0, d], {d, Divisors[n]}], {n, 50}] (* Wesley Ivan Hurt, May 30 2014 *)
f[p_, e_] := (e+1)*(e+2)/2;  a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jan 27 2019 *)

for(n=1,100,print1(sumdiv(n,k,numdiv(k)),","))

a(n)=if(n<1,0,direuler(p=2,n,1/(1-X)^3)[n]) \\ Ralf Stephan

a(n)=sumdiv(n, x, sumdiv(x, y, 1 )) \\ Joerg Arndt, Oct 07 2012

a(n)=sumdivmult(n,k,numdiv(k)) \\ Charles R Greathouse IV, Aug 30 2013

for(n=1, 100, print1(numerator(direuler(p=2, n, 1/(1-X)^3)[n]), ", ")) \\ Vaclav Kotesovec, May 06 2025

from math import prod, comb
from sympy import factorint
def A007425(n): return prod(comb(2+e,2) for e in factorint(n).values()) # Chai Wah Wu, Dec 22 2024

a(n) = Sum_{d dividing n} tau(d). - Benoit Cloitre, Apr 04 2002
G.f.: Sum_{k>=1} tau(k)*x^k/(1-x^k). - Benoit Cloitre, Apr 21 2003
For n = Product p_i^e_i, a(n) = Product_i A000217(e_i + 1). - Lekraj Beedassy, Sep 07 2004
Dirichlet g.f.: zeta^3(s).
From Enrique Pérez Herrero, Nov 03 2009: (Start)
a(n^2) = tau_3(n^2) = tau_2(n^2)*tau_2(n), where tau_2 is A000005 and tau_3 is this sequence.
a(s) = 3^omega(s), if s>1 is squarefree (A005117) and omega(s) is: A001221. (End)
From Enrique Pérez Herrero, Nov 08 2009: (Start)
a(n) = tau_3(n) = tau_2(n)*tau_2(n*rad(n))/tau_2(rad(n)), where rad(n) is A007947 and tau_2(n) is A000005.
tau_3(n) >= 2*tau_2(n) - 1.
tau_3(n) <= tau_2(n)^2 + tau_2(n)-1. (End)
From Vladimir Shevelev, Dec 22 2017: (Start)
a(n) = sqrt(Sum_{d|n}(tau(d))^3);
a(n) = |Sum_{d|n} A008836(d)*(tau(d))^2|.
The first formula follows from the first Cloitre formula and a Liouville formula; the second formula follows from our analogous formula (cf. our comment in Formula section of A000005). (End)
L.g.f.: -log(Product_{k>=1} (1 - x^k)^(tau(k)/k)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 23 2018

A033676 Largest divisor of n <= sqrt(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 4, 1, 3, 1, 4, 3, 2, 1, 4, 5, 2, 3, 4, 1, 5, 1, 4, 3, 2, 5, 6, 1, 2, 3, 5, 1, 6, 1, 4, 5, 2, 1, 6, 7, 5, 3, 4, 1, 6, 5, 7, 3, 2, 1, 6, 1, 2, 7, 8, 5, 6, 1, 4, 3, 7, 1, 8, 1, 2, 5, 4, 7, 6, 1, 8, 9, 2, 1, 7, 5, 2, 3

Offset: 1

N. J. A. Sloane

a(n) = sqrt(n) is a new record if and only if n is a square. - Zak Seidov, Jul 17 2009
a(n) = A060775(n) unless n is a square, when a(n) = A033677(n) = sqrt(n) is strictly larger than A060775(n). It would be nice to have an efficient algorithm to calculate these terms when n has a large number of divisors, as for example in A060776, A060777 and related problems such as A182987. - M. F. Hasler, Sep 20 2011
a(n) = 1 when n = 1 or n is prime. - Alonso del Arte, Nov 25 2012
a(n) is the smallest central divisor of n. Column 1 of A207375. - Omar E. Pol, Feb 26 2019
a(n^4+n^2+1) = n^2-n+1: suppose that n^2-n+k divides n^4+n^2+1 = (n^2-n+k)*(n^2+n-k+2) - (k-1)*(2*n+1-k) for 2 <= k <= 2*n, then (k-1)*(2*n+1-k) >= n^2-n+k, or n^2 - (2*k-1)*n + (k^2-k+1) = (n-k+1/2)^2 + 3/4 < 0, which is impossible. Hence the next smallest divisor of n^4+n^2+1 than n^2-n+1 is at least n^2-n+(2*n+1) = n^2+n+1 > sqrt(n^4+n^2+1). - Jianing Song, Oct 23 2022

G. Tenenbaum, pp. 268 ff, in: R. L. Graham et al., eds., Mathematics of Paul Erdős I.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A033677 (n/a(n)), A000196 (sqrt), A027750 (list of divisors), A056737 (n/a(n) - a(n)), A219695 (half of this for odd numbers), A207375 (list the central divisor(s)).
The strictly inferior case is A060775. Cf. also A140271.
Indices of given values: A008578 (1 and the prime numbers: a(n) = 1), A161344 (a(n) = 2), A161345 (a(n) = 3), A161424 (4), A161835 (5), A162526 (6), A162527 (7), A162528 (8), A162529 (9), A162530 (10), A162531 (11), A162532 (12), A282668 (indices of primes).

a033676 n = last $ takeWhile (<= a000196 n) $ a027750_row n
-- Reinhard Zumkeller, Jun 04 2012

A033676 := proc(n) local a,d; a := 0 ; for d in numtheory[divisors](n) do if d^2 <= n then a := max(a,d) ; end if; end do: a; end proc: # R. J. Mathar, Aug 09 2009

largestDivisorLEQR[n_Integer] := Module[{dvs = Divisors[n]}, dvs[[Ceiling[Length@dvs/2]]]]; largestDivisorLEQR /@ Range[100] (* Borislav Stanimirov, Mar 28 2010 *)
Table[Last[Select[Divisors[n],#<=Sqrt[n]&]],{n,100}] (* Harvey P. Dale, Mar 17 2017 *)

A033676(n) = {local(d);if(n<2,1,d=divisors(n);d[(length(d)+1)\2])} \\ Michael B. Porter, Jan 30 2010

from sympy import divisors
def A033676(n):
    d = divisors(n)
    return d[(len(d)-1)//2]  # Chai Wah Wu, Apr 05 2021

a(n) = n / A033677(n).
a(n) = A161906(n,A038548(n)). - Reinhard Zumkeller, Mar 08 2013
a(n) = A162348(2n-1). - Daniel Forgues, Sep 29 2014

cp's OEIS Frontend

A007955 Product of divisors of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Python

Sage

Sage

Scheme

Formula

A001037 Number of degree-n irreducible polynomials over GF(2); number of n-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period n; number of binary Lyndon words of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A004111 Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A038548 Number of divisors of n that are at most sqrt(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A003238 Number of rooted trees with n vertices in which vertices at the same level have the same degree.

Views

Author

Keywords

Comments

Examples

A272919 Numbers of the form 2^(n-1)(2^(nm)-1)/(2^n-1), n >= 1, m >= 1.