A106737 -id:A106737 - cp's OEIS frontend

A000005 d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n.

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

Offset: 1

N. J. A. Sloane

If the canonical factorization of n into prime powers is Product p^e(p) then d(n) = Product (e(p) + 1). More generally, for k > 0, sigma_k(n) = Product_p ((p^((e(p)+1)*k))-1)/(p^k-1) is the sum of the k-th powers of the divisors of n.
Number of ways to write n as n = x*y, 1 <= x <= n, 1 <= y <= n. For number of unordered solutions to x*y=n, see A038548.
Note that d(n) is not the number of Pythagorean triangles with radius of the inscribed circle equal to n (that is A078644). For number of primitive Pythagorean triangles having inradius n, see A068068(n).
Number of factors in the factorization of the polynomial x^n-1 over the integers. - T. D. Noe, Apr 16 2003
Also equal to the number of partitions p of n such that all the parts have the same cardinality, i.e., max(p)=min(p). - Giovanni Resta, Feb 06 2006
Equals A127093 as an infinite lower triangular matrix * the harmonic series, [1/1, 1/2, 1/3, ...]. - Gary W. Adamson, May 10 2007
For odd n, this is the number of partitions of n into consecutive integers. Proof: For n = 1, clearly true. For n = 2k + 1, k >= 1, map each (necessarily odd) divisor to such a partition as follows: For 1 and n, map k + (k+1) and n, respectively. For any remaining divisor d <= sqrt(n), map (n/d - (d-1)/2) + ... + (n/d - 1) + (n/d) + (n/d + 1) + ... + (n/d + (d-1)/2) {i.e., n/d plus (d-1)/2 pairs each summing to 2n/d}. For any remaining divisor d > sqrt(n), map ((d-1)/2 - (n/d - 1)) + ... + ((d-1)/2 - 1) + (d-1)/2 + (d+1)/2 + ((d+1)/2 + 1) + ... + ((d+1)/2 + (n/d - 1)) {i.e., n/d pairs each summing to d}. As all such partitions must be of one of the above forms, the 1-to-1 correspondence and proof is complete. - Rick L. Shepherd, Apr 20 2008
Number of subgroups of the cyclic group of order n. - Benoit Jubin, Apr 29 2008
Equals row sums of triangle A143319. - Gary W. Adamson, Aug 07 2008
Equals row sums of triangle A159934, equivalent to generating a(n) by convolving A000005 prefaced with a 1; (1, 1, 2, 2, 3, 2, ...) with the INVERTi transform of A000005, (A159933): (1, 1,-1, 0, -1, 2, ...). Example: a(6) = 4 = (1, 1, 2, 2, 3, 2) dot (2, -1, 0, -1, 1, 1) = (2, -1, 0, -2, 3, 2) = 4. - Gary W. Adamson, Apr 26 2009
Number of times n appears in an n X n multiplication table. - Dominick Cancilla, Aug 02 2010
Number of k >= 0 such that (k^2 + k*n + k)/(k + 1) is an integer. - Juri-Stepan Gerasimov, Oct 25 2015
The only numbers k such that tau(k) >= k/2 are 1,2,3,4,6,8,12. - Michael De Vlieger, Dec 14 2016
a(n) is also the number of partitions of 2*n into equal parts, minus the number of partitions of 2*n into consecutive parts. - Omar E. Pol, May 03 2017
From Tomohiro Yamada, Oct 27 2020: (Start)
Let k(n) = log d(n)*log log n/(log 2 * log n), then lim sup k(n) = 1 (Hardy and Wright, Chapter 18, Theorem 317) and k(n) <= k(6983776800) = 1.537939... (the constant A280235) for every n (Nicolas and Robin, 1983).
There exist infinitely many n such that d(n) = d(n+1) (Heath-Brown, 1984). The number of such integers n <= x is at least c*x/(log log x)^3 (Hildebrand, 1987) but at most O(x/sqrt(log log x)) (Erdős, Carl Pomerance and Sárközy, 1987). (End)
Number of 2D grids of n congruent rectangles with two different side lengths, in a rectangle, modulo rotation (cf. A038548 for squares instead of rectangles). Also number of ways to arrange n identical objects in a rectangle (NOT modulo rotation, cf. A038548 for modulo rotation); cf. A007425 and A140773 for the 3D case. - Manfred Boergens, Jun 08 2021
The constant quoted above from Nicolas and Robin, 6983776800 = 2^5 * 3^3 * 5^2 * 7 * 11 * 13 * 17 * 19, appears arbitrary, but interestingly equals 2 * A095849(36). That second factor is highly composite and deeply composite. - Hal M. Switkay, Aug 08 2025

			G.f. = x + 2*x^2 + 2*x^3 + 3*x^4 + 2*x^5 + 4*x^6 + 2*x^7 + 4*x^8 + 3*x^9 + ...

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 38.
G. Chrystal, Algebra: An elementary text-book for the higher classes of secondary schools and for colleges, 6th ed, Chelsea Publishing Co., New York 1959 Part II, p. 345, Exercise XXI(16). MR0121327 (22 #12066)
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, p. 55.
G. H. Hardy and E. M. Wright, revised by D. R. Heath-Brown and J. H. Silverman, An Introduction to the Theory of Numbers, 6th ed., Oxford Univ. Press, 2008.
K. Knopp, Theory and Application of Infinite Series, Blackie, London, 1951, p. 451.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Chap. II. (For inequalities, etc.)
S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962. Has many references to this sequence. - N. J. A. Sloane, Jun 02 2014
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
B. Spearman and K. S. Williams, Handbook of Estimates in the Theory of Numbers, Carleton Math. Lecture Note Series No. 14, 1975; see p. 2.1.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 285.
E. C. Titchmarsh, The Theory of Functions, Oxford, 1938, p. 160.
Terence Tao, Poincaré's Legacies, Part I, Amer. Math. Soc., 2009, see pp. 31ff for upper bounds on d(n).

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy, requires Flash plugin].
G. E. Andrews, Some debts I owe, Séminaire Lotharingien de Combinatoire, Paper B42a, Issue 42, 2000; see (7.1).
J. Bell, Lambert series in analytic number theory
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. [From _N. J. A. Sloane_, Mar 12 2009]
Henry Bottomley, Illustration of initial terms
D. M. Bressoud and M. V. Subbarao, On Uchimura's connection between partitions and the number of divisors, Can. Math. Bull. 27, 143-145 (1984). Zbl 0536.10013.
C. K. Caldwell, The Prime Glossary, Number of divisors
Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget Sound.
Jimmy Devillet and Gergely Kiss, Characterizations of biselective operations, arXiv:1806.02073 [math.RA], 2018.
P. Erdős and L. Mirsky, The distribution of values of the divisor function d(n), Proc. London Math. Soc. 2 (1952), pp. 257-271.
Paul Erdős, Carl Pomerance and András Sárközy, On locally repeated values of certain arithmetic functions, III, Proc. Amer. Math. Soc. 101 (1987), 1-7.
C. R. Fletcher, Rings of small order, Math. Gaz. vol. 64, p. 13, 1980.
Robbert Fokkink and Jan van Neerven, Problemen/UWC (in Dutch)
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors ..., J. Integer Seqs., Vol. 6, 2003.
D. R. Heath-Brown, The divisor function at consecutive integers, Mathematika 31 (1984), 141-149.
Adolf Hildebrand, The divisor function at consecutive integers, Pacific J. Math. 129 (1987), 307-319.
J. J. Holt and J. W. Jones, Counting Divisors, Discovering Number Theory, Section 1.4.
P. A. MacMahon, Divisors of numbers and their continuations in the theory of partitions, Proc. London Math. Soc., 19 (1919), 75-113.
M. Maia and M. Mendez, On the arithmetic product of combinatorial species, arXiv:math/0503436 [math.CO], 2005.
R. G. Martinez, Jr., The Factor Zone, Number of Factors for 1 through 600.
Math Forum, Divisor Counting.
Mathematics Stack Exchange, A question on discrete Fourier Transform of some function
K. Matthews, Factorizing n and calculating phi(n), omega(n), d(n), sigma(n) and mu(n).
Mircea Merca, A new look on the generating function for the number of divisors, Journal of Number Theory, Volume 149, April 2015, Pages 57-69.
Mircea Merca, Combinatorial interpretations of a recent convolution for the number of divisors of a positive integer, Journal of Number Theory, Volume 160, March 2016, Pages 60-75, corollary 2.1.
J. L. Nicolas and G. Robin, Majorations Explicites Pour le Nombre de Diviseurs de N, Canadian Mathematical Bulletin, Volume 26, Issue 4, 01 December 1983, pp. 485-492.
Matthew Parker, The first 25 million terms (7-Zip compressed file).
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003. [Cached copy, with permission (pdf only)]
Omar E. Pol, Illustration of initial terms: figure 1, figure 2, figure 3, figure 4, figure 5, (2009), figure 6 (a, b, c), (2013)
S. Ramanujan, On The Number Of Divisors Of A Number.
H. B. Reiter, Counting Divisors.
W. Sierpiński, Number Of Divisors And Their Sum.
Terence Tao, Poincaré's Legacies: pages from year two of a mathematical blog, see page 59.
E. C. Titchmarsh, On a series of Lambert type, J. London Math. Soc., 13 (1938), 248-253.
Keisuke Uchimura, An identity for the divisor generating function arising from sorting theory, J. Combin. Theory Ser. A 31 (1981), no. 2, 131--135. MR0629588 (82k:05015)
Wang Zheng Bing, Robert Fokkink and Wan Fokkink, A Relation Between Partitions and the Number of Divisors, Am. Math. Monthly, 102 (Apr., 1995), no. 4, 345-347.
Eric Weisstein's World of Mathematics, Binomial Number, Dirichlet Series Generating Function, Divisor Function, and Moebius Transform.
Wikipedia, Table of divisors.
Wolfram Research, Divisors of first 50 numbers
Index entries for "core" sequences
Index entries for sequences computed from exponents in factorization of n

See A002183, A002182 for records. See A000203 for the sum-of-divisors function sigma(n).
For partial sums see A006218.
Cf. A007427 (Dirichlet Inverse), A001227, A001826, A001842, A005237, A005238, A006558, A006601, A019273, A027750, A034296, A039665, A049051, A049820, A051731, A061017, A066446, A091202, A091220, A106737, A115361, A127093, A129372, A129510, A143319, A156552, A159933, A159934, A163280, A183063, A237665, A263730.
Factorizations into given number of factors: writing n = x*y (A038548, unordered, A000005, ordered), n = x*y*z (A034836, unordered, A007425, ordered), n = w*x*y*z (A007426, ordered).
Cf. A000010, A095849.
Cf. A098198 (Dgf at s=2), A183030 (Dgf at s=3), A183031 (Dgf at s=3).

List([1..150],n->Tau(n)); # Muniru A Asiru, Mar 05 2019

divisors 1 = [1]
divisors n = (1:filter ((==0) . rem n)
               [2..n `div` 2]) ++ [n]
a = length . divisors
-- James Spahlinger, Oct 07 2012

a000005 = product . map (+ 1) . a124010_row  -- Reinhard Zumkeller, Jul 12 2013

function tau(n)
    i = 2; num = 1
    while i * i <= n
        if rem(n, i) == 0
            e = 0
            while rem(n, i) == 0
                e += 1
                n = div(n, i)
            end
            num *= e + 1
        end
        i += 1
    end
    return n > 1 ? num + num : num
end
println([tau(n) for n in 1:104])  # Peter Luschny, Sep 03 2023

[ NumberOfDivisors(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

with(numtheory): A000005 := tau; [ seq(tau(n), n=1..100) ];

Table[DivisorSigma[0, n], {n, 100}] (* Enrique Pérez Herrero, Aug 27 2009 *)
CoefficientList[Series[(Log[1 - q] + QPolyGamma[1, q])/(q Log[q]), {q, 0, 100}], q] (* Vladimir Reshetnikov, Apr 23 2013 *)
a[ n_] := SeriesCoefficient[ (QPolyGamma[ 1, q] + Log[1 - q]) / Log[q], {q, 0, Abs@n}]; (* Michael Somos, Apr 25 2013 *)
a[ n_] := SeriesCoefficient[ q/(1 - q)^2 QHypergeometricPFQ[ {q, q}, {q^2, q^2}, q, q^2], {q, 0, Abs@n}]; (* Michael Somos, Mar 05 2014 *)
a[n_] := SeriesCoefficient[q/(1 - q) QHypergeometricPFQ[{q, q}, {q^2}, q, q], {q, 0, Abs@n}] (* Mats Granvik, Apr 15 2015 *)
With[{M=500},CoefficientList[Series[(2x)/(1-x)-Sum[x^k (1-2x^k)/(1-x^k),{k,M}],{x,0,M}],x]] (* Mamuka Jibladze, Aug 31 2018 *)

numlib::tau (n)$ n=1..90 // Zerinvary Lajos, May 13 2008

{a(n) = if( n==0, 0, numdiv(n))}; /* Michael Somos, Apr 27 2003 */

{a(n) = n=abs(n); if( n<1, 0, direuler( p=2, n, 1 / (1 - X)^2)[n])}; /* Michael Somos, Apr 27 2003 */

{a(n)=polcoeff(sum(m=1, n+1, sumdiv(m, d, (-log(1-x^(m/d) +x*O(x^n) ))^d/d!)), n)} \\ Paul D. Hanna, Aug 21 2014

from sympy import divisor_count
for n in range(1, 20): print(divisor_count(n), end=', ') # Stefano Spezia, Nov 05 2018

[sigma(n, 0) for n in range(1, 105)]  # Zerinvary Lajos, Jun 04 2009

If n is written as 2^z*3^y*5^x*7^w*11^v*... then a(n)=(z+1)*(y+1)*(x+1)*(w+1)*(v+1)*...
a(n) = 2 iff n is prime.
G.f.: Sum_{n >= 1} a(n) x^n = Sum_{k>0} x^k/(1-x^k). This is usually called THE Lambert series (see Knopp, Titchmarsh).
a(n) = A083888(n) + A083889(n) + A083890(n) + A083891(n) + A083892(n) + A083893(n) + A083894(n) + A083895(n) + A083896(n).
a(n) = A083910(n) + A083911(n) + A083912(n) + A083913(n) + A083914(n) + A083915(n) + A083916(n) + A083917(n) + A083918(n) + A083919(n).
Multiplicative with a(p^e) = e+1. - David W. Wilson, Aug 01 2001
a(n) <= 2 sqrt(n) [see Mitrinovich, p. 39, also A046522].
a(n) is odd iff n is a square. - Reinhard Zumkeller, Dec 29 2001
a(n) = Sum_{k=1..n} f(k, n) where f(k, n) = 1 if k divides n, 0 otherwise (Mobius transform of A000012). Equivalently, f(k, n) = (1/k)*Sum_{l=1..k} z(k, l)^n with z(k, l) the k-th roots of unity. - Ralf Stephan, Dec 25 2002
G.f.: Sum_{k>0} ((-1)^(k+1) * x^(k * (k + 1)/2) / ((1 - x^k) * Product_{i=1..k} (1 - x^i))). - Michael Somos, Apr 27 2003
a(n) = n - Sum_{k=1..n} (ceiling(n/k) - floor(n/k)). - Benoit Cloitre, May 11 2003
a(n) = A032741(n) + 1 = A062011(n)/2 = A054519(n) - A054519(n-1) = A006218(n) - A006218(n-1) = 1 + Sum_{k=1..n-1} A051950(k+1). - Ralf Stephan, Mar 26 2004
G.f.: Sum_{k>0} x^(k^2)*(1+x^k)/(1-x^k). Dirichlet g.f.: zeta(s)^2. - Michael Somos, Apr 05 2003
Sequence = M*V where M = A129372 as an infinite lower triangular matrix and V = ruler sequence A001511 as a vector: [1, 2, 1, 3, 1, 2, 1, 4, ...]. - Gary W. Adamson, Apr 15 2007
Sequence = M*V, where M = A115361 is an infinite lower triangular matrix and V = A001227, the number of odd divisors of n, is a vector: [1, 1, 2, 1, 2, 2, 2, ...]. - Gary W. Adamson, Apr 15 2007
Row sums of triangle A051731. - Gary W. Adamson, Nov 02 2007
Sum_{n>0} a(n)/(n^n) = Sum_{n>0, m>0} 1/(n*m). - Gerald McGarvey, Dec 15 2007
Logarithmic g.f.: Sum_{n>=1} a(n)/n * x^n = -log( Product_{n>=1} (1-x^n)^(1/n) ). - Joerg Arndt, May 03 2008
a(n) = Sum_{k=1..n} (floor(n/k) - floor((n-1)/k)). - Enrique Pérez Herrero, Aug 27 2009
a(s) = 2^omega(s), if s > 1 is a squarefree number (A005117) and omega(s) is: A001221. - Enrique Pérez Herrero, Sep 08 2009
a(n) = A048691(n) - A055205(n). - Reinhard Zumkeller, Dec 08 2009
For n > 1, a(n) = 2 + Sum_{k=2..n-1} floor((cos(Pi*n/k))^2). And floor((cos(Pi*n/k))^2) = floor(1/4 * e^(-(2*i*Pi*n)/k) + 1/4 * e^((2*i*Pi*n)/k) + 1/2). - Eric Desbiaux, Mar 09 2010, corrected Apr 16 2011
a(n) = 1 + Sum_{k=1..n} (floor(2^n/(2^k-1)) mod 2) for every n. - Fabio Civolani (civox(AT)tiscali.it), Mar 12 2010
From Vladimir Shevelev, May 22 2010: (Start)
(Sum_{d|n} a(d))^2 = Sum_{d|n} a(d)^3 (J. Liouville).
Sum_{d|n} A008836(d)*a(d)^2 = A008836(n)*Sum_{d|n} a(d). (End)
a(n) = sigma_0(n) = 1 + Sum_{m>=2} Sum_{r>=1} (1/m^(r+1))*Sum_{j=1..m-1} Sum_{k=0..m^(r+1)-1} e^(2*k*Pi*i*(n+(m-j)*m^r)/m^(r+1)). - A. Neves, Oct 04 2010
a(n) = 2*A038548(n) - A010052(n). - Reinhard Zumkeller, Mar 08 2013
Sum_{n>=1} a(n)*q^n = (log(1-q) + psi_q(1)) / log(q), where psi_q(z) is the q-digamma function. - Vladimir Reshetnikov, Apr 23 2013
a(n) = Product_{k = 1..A001221(n)} (A124010(n,k) + 1). - Reinhard Zumkeller, Jul 12 2013
a(n) = Sum_{k=1..n} A238133(k)*A000041(n-k). - Mircea Merca, Feb 18 2013
G.f.: Sum_{k>=1} Sum_{j>=1} x^(j*k). - Mats Granvik, Jun 15 2013
The formula above is obtained by expanding the Lambert series Sum_{k>=1} x^k/(1-x^k). - Joerg Arndt, Mar 12 2014
G.f.: Sum_{n>=1} Sum_{d|n} ( -log(1 - x^(n/d)) )^d / d!. - Paul D. Hanna, Aug 21 2014
2*Pi*a(n) = Sum_{m=1..n} Integral_{x=0..2*Pi} r^(m-n)( cos((m-n)*x)-r^m cos(n*x) )/( 1+r^(2*m)-2r^m cos(m*x) )dx, 0 < r < 1 a free parameter. This formula is obtained as the sum of the residues of the Lambert series Sum_{k>=1} x^k/(1-x^k). - Seiichi Kirikami, Oct 22 2015
a(n) = A091220(A091202(n)) = A106737(A156552(n)). - Antti Karttunen, circa 2004 & Mar 06 2017
a(n) = A034296(n) - A237665(n+1) [Wang, Fokkink, Fokkink]. - George Beck, May 06 2017
G.f.: 2*x/(1-x) - Sum_{k>0} x^k*(1-2*x^k)/(1-x^k). - Mamuka Jibladze, Aug 29 2018
a(n) = Sum_{k=1..n} 1/phi(n / gcd(n, k)). - Daniel Suteu, Nov 05 2018
a(k*n) = a(n)*(f(k,n)+2)/(f(k,n)+1), where f(k,n) is the exponent of the highest power of k dividing n and k is prime. - Gary Detlefs, Feb 08 2019
a(n) = 2*log(p(n))/log(n), n > 1, where p(n)= the product of the factors of n = A007955(n). - Gary Detlefs, Feb 15 2019
a(n) = (1/n) * Sum_{k=1..n} sigma(gcd(n,k)), where sigma(n) = sum of divisors of n. - Orges Leka, May 09 2019
a(n) = A001227(n)*(A007814(n) + 1) = A001227(n)*A001511(n). - Ivan N. Ianakiev, Nov 14 2019
From Richard L. Ollerton, May 11 2021: (Start)
a(n) = A038040(n) / n = (1/n)*Sum_{d|n} phi(d)*sigma(n/d), where phi = A000010 and sigma = A000203.
a(n) = (1/n)*Sum_{k=1..n} phi(gcd(n,k))*sigma(n/gcd(n,k))/phi(n/gcd(n,k)). (End)
From Ridouane Oudra, Nov 12 2021: (Start)
a(n) = Sum_{j=1..n} Sum_{k=1..j} (1/j)*cos(2*k*n*Pi/j);
a(n) = Sum_{j=1..n} Sum_{k=1..j} (1/j)*e^(2*k*n*Pi*i/j), where i^2=-1. (End)

Incorrect formula deleted by Ridouane Oudra, Oct 28 2021

A005940 The Doudna sequence: write n-1 in binary; power of prime(k) in a(n) is # of 1's that are followed by k-1 0's.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 9, 8, 7, 10, 15, 12, 25, 18, 27, 16, 11, 14, 21, 20, 35, 30, 45, 24, 49, 50, 75, 36, 125, 54, 81, 32, 13, 22, 33, 28, 55, 42, 63, 40, 77, 70, 105, 60, 175, 90, 135, 48, 121, 98, 147, 100, 245, 150, 225, 72, 343, 250, 375, 108, 625, 162, 243, 64, 17, 26, 39

Offset: 1

N. J. A. Sloane and J. H. Conway

A permutation of the natural numbers. - Robert G. Wilson v, Feb 22 2005
Fixed points: A029747. - Reinhard Zumkeller, Aug 23 2006
The even bisection, when halved, gives the sequence back. - Antti Karttunen, Jun 28 2014
From Antti Karttunen, Dec 21 2014: (Start)
This irregular table can be represented as a binary tree. Each child to the left is obtained by applying A003961 to the parent, and each child to the right is obtained by doubling the parent:
                                      1
                                      |
                   ...................2...................
                  3                                       4
        5......../ \........6                   9......../ \........8
       / \                 / \                 / \                 / \
      /   \               /   \               /   \               /   \
     /     \             /     \             /     \             /     \
    7       10         15       12         25       18         27       16
  11 14   21  20     35  30   45  24     49  50   75  36    125  54   81  32
etc.
Sequence A163511 is obtained by scanning the same tree level by level, from right to left. Also in binary trees A253563 and A253565 the terms on level of the tree are some permutation of the terms present on the level n of this tree. A252464(n) gives the distance of n from 1 in all these trees.
A252737(n) gives the sum and A252738(n) the product of terms on row n (where 1 is on row 0, 2 on row 1, 3 and 4 on row 2, etc.). A252745(n) gives the number of nodes on level n whose left child is larger than the right child, A252750 the difference between left and right child for each node from node 2 onward.
(End)
-A008836(a(1+n)) gives the corresponding numerator for A323505(n). - Antti Karttunen, Jan 19 2019
(a(2n+1)-1)/2 [= A244154(n)-1, for n >= 0] is a permutation of the natural numbers. - George Beck and Antti Karttunen, Dec 08 2019
From Peter Munn, Oct 04 2020: (Start)
Each term has the same even part (equivalently, the same 2-adic valuation) as its index.
Using the tree depicted in Antti Karttunen's 2014 comment:
Numbers are on the right branch (4 and descendants) if and only if divisible by the square of their largest prime factor (cf. A070003).
Numbers on the left branch, together with 2, are listed in A102750.
(End)
According to Kutz (1981), he learned of this sequence from American mathematician Byron Leon McAllister (1929-2017) who attributed the invention of the sequence to a graduate student by the name of Doudna (first name Paul?) in the mid-1950's at the University of Wisconsin. - Amiram Eldar, Jun 17 2021
From David James Sycamore, Sep 23 2022: (Start)
Alternative (recursive) definition: If n is a power of 2 then a(n)=n. Otherwise, if 2^j is the greatest power of 2 not exceeding n, and if k = n - 2^j, then a(n) is the least m*a(k) that has not occurred previously, where m is an odd prime.
Example: Use recursion with n = 77 = 2^6 + 13. a(13) = 25 and since 11 is the smallest odd prime m such that m*a(13) has not already occurred (see a(27), a(29),a(45)), then a(77) = 11*25 = 275. (End)
The odd bisection, when transformed by replacing all prime(k)^e in a(2*n - 1) with prime(k-1)^e, returns a(n), and thus gives the sequence back. - David James Sycamore, Sep 28 2022

			From _N. J. A. Sloane_, Aug 22 2022: (Start)
Let c_i = number of 1's in binary expansion of n-1 that have i 0's to their right, and let p(j) = j-th prime.  Then a(n) = Product_i p(i+1)^c_i.
If n=9, n-1 is 1000, c_3 = 1, a(9) = p(4)^1 = 7.
If n=10, n-1 = 1001, c_0 = 1, c_2 = 1, a(10) = p(1)*p(3) = 2*5 = 10.
If n=11, n-1 = 1010, c_1 = 1, c_2 = 1, a(11) = p(2)*p(3) = 15. (End)

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

Antti Karttunen, Table of n, a(n) for n = 1..8192 (terms 1..1024 from Reinhard Zumkeller)
Michael De Vlieger, 6 row Doudna Tree diagram as mentioned in Comments.
Michael De Vlieger, Annotated fan-style binary tree showing 10 levels, with a color function where 2^m is shown in medium blue in row m, k < 2^m is darker blue, and k > 2^m is brighter green, with records in each row shown in red.
Ronald E. Kutz, Two unusual sequences, Two-Year College Mathematics Journal, Vol. 12, No. 5 (1981), pp. 316-319.
Index entries for sequences that are permutations of the natural numbers

Cf. A103969. Inverse is A005941 (A156552).
Cf. A125106. [From Franklin T. Adams-Watters, Mar 06 2010]
Cf. A252737 (gives row sums), A252738 (row products), A332979 (largest on row).
Related permutations of positive integers: A163511 (via A054429), A243353 (via A006068), A244154, A253563 (via A122111), A253565, A332977, A334866 (via A225546).
A000120, A003602, A003961, A006519, A053645, A070939, A246278, A250246, A252753, A253552 are used in a formula defining this sequence.
Formulas for f(a(n)) are given for f = A000265, A003963, A007949, A055396, A056239.
Numbers that occur at notable sets of positions in the binary tree representation of the sequence: A000040, A000079, A002110, A070003, A070826, A102750.
Cf. also A000142, A001511, A002450, A112798, A252463, A252464, A252745, A252750, A324054, A324106, A323505, A323508.
Cf. A106737, A290077, A323915, A324052, A324054, A324055, A324056, A324057, A324058, A324114, A324335, A324340, A324348, A324349 for various number-theoretical sequences applied to (i.e., permuted by) this sequence.
k-adic valuation: A007814 (k=2), A337821 (k=3).
Positions of multiples of 3: A091067.
Primorial deflation: A337376 / A337377.
Sum of prime indices of a(n) is A161511, reverse version A359043.
A048793 lists binary indices, ranked by A019565.
A066099 lists standard comps, partial sums A358134 (ranked by A358170).
Cf. A001222, A029837, A059893, A241916, A242628, A253566, A359042.

a005940 n = f (n - 1) 1 1 where
   f 0 y _          = y
   f x y i | m == 0 = f x' y (i + 1)
           | m == 1 = f x' (y * a000040 i) i
           where (x',m) = divMod x 2
-- Reinhard Zumkeller, Oct 03 2012
(Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library)
(define (A005940 n) (A005940off0 (- n 1))) ;; The off=1 version, utilizing any one of three different offset-0 implementations:
(definec (A005940off0 n) (cond ((< n 2) (+ 1 n)) (else (* (A000040 (- (A070939 n) (- (A000120 n) 1))) (A005940off0 (A053645 n))))))
(definec (A005940off0 n) (cond ((<= n 2) (+ 1 n)) ((even? n) (A003961 (A005940off0 (/ n 2)))) (else (* 2 (A005940off0 (/ (- n 1) 2))))))
(define (A005940off0 n) (let loop ((n n) (i 1) (x 1)) (cond ((zero? n) x) ((even? n) (loop (/ n 2) (+ i 1) x)) (else (loop (/ (- n 1) 2) i (* x (A000040 i)))))))
;; Antti Karttunen, Jun 26 2014

f := proc(n,i,x) option remember ; if n = 0 then x; elif type(n,'even') then procname(n/2,i+1,x) ; else procname((n-1)/2,i,x*ithprime(i)) ; end if; end proc:
A005940 := proc(n) f(n-1,1,1) ; end proc: # R. J. Mathar, Mar 06 2010

f[n_] := Block[{p = Partition[ Split[ Join[ IntegerDigits[n - 1, 2], {2}]], 2]}, Times @@ Flatten[ Table[q = Take[p, -i]; Prime[ Count[ Flatten[q], 0] + 1]^q[[1, 1]], {i, Length[p]}] ]]; Table[ f[n], {n, 67}] (* Robert G. Wilson v, Feb 22 2005 *)
Table[Times@@Prime/@(Join@@Position[Reverse[IntegerDigits[n,2]],1]-Range[DigitCount[n,2,1]]+1),{n,0,100}] (* Gus Wiseman, Dec 28 2022 *)

A005940(n) = { my(p=2, t=1); n--; until(!n\=2, n%2 && (t*=p) || p=nextprime(p+1)); t } \\ M. F. Hasler, Mar 07 2010; update Aug 29 2014

a(n)=my(p=2, t=1); for(i=0,exponent(n), if(bittest(n,i), t*=p, p=nextprime(p+1))); t \\ Charles R Greathouse IV, Nov 11 2021

from sympy import prime
import math
def A(n): return n - 2**int(math.floor(math.log(n, 2)))
def b(n): return n + 1 if n<2 else prime(1 + (len(bin(n)[2:]) - bin(n)[2:].count("1"))) * b(A(n))
print([b(n - 1) for n in range(1, 101)]) # Indranil Ghosh, Apr 10 2017

from math import prod
from itertools import accumulate
from collections import Counter
from sympy import prime
def A005940(n): return prod(prime(len(a)+1)**b for a, b in Counter(accumulate(bin(n-1)[2:].split('1')[:0:-1])).items()) # Chai Wah Wu, Mar 10 2023

From Reinhard Zumkeller, Aug 23 2006, R. J. Mathar, Mar 06 2010: (Start)
a(n) = f(n-1, 1, 1)
  where f(n, i, x) = x if n = 0,
                   = f(n/2, i+1, x) if n > 0 is even
                   = f((n-1)/2, i, x*prime(i)) otherwise. (End)
From Antti Karttunen, Jun 26 2014: (Start)
Define a starting-offset 0 version of this sequence as:
  b(0)=1, b(1)=2, [base cases]
and then compute the rest either with recurrence:
  b(n) = A000040(1+(A070939(n)-A000120(n))) * b(A053645(n)).
or
  b(2n) = A003961(b(n)), b(2n+1) = 2 * b(n). [Compare this to the similar recurrence given for A163511.]
Then define a(n) = b(n-1), where a(n) gives this sequence A005940 with the starting offset 1.
Can be also defined as a composition of related permutations:
a(n+1) = A243353(A006068(n)).
a(n+1) = A163511(A054429(n)). [Compare the scatter plots of this sequence and A163511 to each other.]
This permutation also maps between the partitions as enumerated in the lists A125106 and A112798, providing identities between:
A161511(n) = A056239(a(n+1)). [The corresponding sums ...]
A243499(n) = A003963(a(n+1)). [... and the products of parts of those partitions.]
(End)
From Antti Karttunen, Dec 21 2014  - Jan 04 2015: (Start)
A002110(n) =  a(1+A002450(n)). [Primorials occur at (4^n - 1)/3 in the offset-0 version of the sequence.]
a(n) = A250246(A252753(n-1)).
a(n) = A122111(A253563(n-1)).
For n >= 1, A055396(a(n+1)) = A001511(n).
For n >= 2, a(n) = A246278(1+A253552(n)).
(End)
From Peter Munn, Oct 04 2020: (Start)
A000265(a(n)) = a(A000265(n)) = A003961(a(A003602(n))).
A006519(a(n)) = a(A006519(n)) = A006519(n).
a(n) = A003961(a(A003602(n))) * A006519(n).
A007814(a(n)) = A007814(n).
A007949(a(n)) = A337821(n) = A007814(A003602(n)).
a(n) = A225546(A334866(n-1)).
(End)
a(2n) = 2*a(n), or generally a(2^k*n) = 2^k*a(n). - Amiram Eldar, Oct 03 2022
If n-1 = Sum_{i} 2^(q_i-1), then a(n) = Product_{i} prime(q_i-i+1). These are the Heinz numbers of the rows of A125106. If the offset is changed to 0, the inverse is A156552. - Gus Wiseman, Dec 28 2022

More terms from Robert G. Wilson v, Feb 22 2005
Sign in a formula switched and Maple program added by R. J. Mathar, Mar 06 2010
Binary tree illustration and keyword tabf added by Antti Karttunen, Dec 21 2014

A010052 Characteristic function of squares: a(n) = 1 if n is a square, otherwise 0.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane

Also parity of the divisor function A000005 if n >= 1. - Omar E. Pol, Jan 14 2012
This sequence can be considered as k=1 analog of A025426 (k=2), A025427 (k=3), A025428 (k=4); see also A000161. - M. F. Hasler, Jan 25 2013
Also, the decimal expansion of Sum_{n >= 0} 1/(10^n)^n. -  Eric Desbiaux, Mar 15 2009, rephrased and simplified by M. F. Hasler, Jan 26 2013
Run lengths of zeros gives A005843, the nonnegative even numbers. - Jeremy Gardiner, Jan 14 2018
Inverse Möbius transform of Liouville's lambda function (A008836), n >= 1. - Wesley Ivan Hurt, Jun 22 2024

			G.f. = 1 + x + x^4 + x^9 + x^16 + x^25 + x^36 + x^49 + x^64 + x^81 + ...

Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 3-4, also p. 166, Ex. 5.5.1.
Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, Problem 20.
Richard Bellman, A Brief Introduction to Theta Functions, Dover, 2013 (11.14).
Michael D. Hirschhorn, The Power of q, Springer, 2017. See phi(q) page 8.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002, p. 55.

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
David Christopher and Tamil Nadu, Partitions with Fixed Number of Sizes, Journal of Integer Sequences, 15 (2015), Article 15.11.5.
Robert Price, Comments on A010052 concerning Elementary Cellular Automata, Jan 29 2016.
Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), Article 01.2.1.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton.
Eric Weisstein's World of Mathematics, Jacobi Theta Functions.
Stephen Wolfram, A New Kind of Science.
Index entries for characteristic functions
Index to Elementary Cellular Automata.
Index entries for sequences computed from exponents in factorization of n.
Index entries for sequences related to cellular automata.

Column k=1 of A243148, A337165, A341040 (for n>0).
Cf. A000005, A000122, A005369, A007913, A008836 (Mobius transf.), A037011, A063524, A258998, A271102 (Dirichlet inv), A046951 (inv. Mobius trans.).
First differences of A000196.

a010052 n = fromEnum $ a000196 n ^ 2 == n
-- Reinhard Zumkeller, Jan 26 2012, Feb 20 2011
a010052_list = concat (iterate (\xs -> xs ++ [0,0]) [1])
-- Reinhard Zumkeller, Apr 27 2012

readlib(issqr): f := i->if issqr(i) then 1 else 0; fi; [ seq(f(i),i=0..100) ];

lst = {}; Do[AppendTo[lst, 2*Sum[Floor[n/k] - Floor[(n - 1)/k], {k, Floor[Sqrt[n]]}] - DivisorSigma[0, n]], {n, 93}]; Prepend[lst, 1] (* Eric Desbiaux, Jan 29 2012 *)
Table[If[IntegerQ[Sqrt[n]],1,0],{n,0,100}] (* Harvey P. Dale, Jul 19 2014 *)
a[n_] := SeriesCoefficient[1/(1 - q)* QHypergeometricPFQ[{-q, -q}, {-(q^2)}, -q, -q], {q, 0, Abs@n}] (* Mats Granvik, Jan 01 2016 *)
Range[0, 120] /. {n_ /; IntegerQ@ Sqrt@ n -> 1, n_ /; n != 1 -> 0} (* Michael De Vlieger, Jan 02 2016 *)
a[n_] := Sum[If[Mod[n, k] == 0, Re[Sqrt[LiouvilleLambda[k]]*Sqrt[LiouvilleLambda[n/k]]], 0], {k, 1, n}] (* Mats Granvik, Aug 10 2018 *)

PARI
```
{a(n) = issquare(n)};
```

a(n)=if(n<1,1,sumdiv(n,d,(-1)^bigomega(d))) \\ Benoit Cloitre, Oct 25 2009

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

def A010052(n): return int(math.isqrt(n)**2==n) ##  appears to be faster than sympy.ntheory.primetest.is_square, up to 10^8 at least.
# M. F. Hasler, Mar 21 2022

(define (A010052 n) (if (zero? n) 1 (- (A000196 n) (A000196 (- n 1))))) ;; (For the definition of A000196, see under that entry). - Antti Karttunen, Nov 03 2017

a(n) = floor(sqrt(n)) - floor(sqrt(n-1)), for n > 0.
a(n) = A000005(n) mod 2, n > 0. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 19 2001
G.f. A(x) satisfies: 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = (u-w)^2 - (v-w)*(v+w-1) - Michael Somos, Jul 19 2004
Dirichlet g.f.: zeta(2s). - Franklin T. Adams-Watters, Sep 11 2005
G.f.: (theta_3(0,x) + 1)/2, where theta_3 is a Jacobi theta function. - Franklin T. Adams-Watters, Jun 19 2006 [See A000122 for theta_3.]
a(n) = f(n,0) with f(x,y) = f(x-2*y-1,y+1) if x > 0, otherwise 0^(-x). - Reinhard Zumkeller, Sep 26 2008
a(n) = Sum_{d|n} (-1)^bigomega(d), for n >= 1. - Benoit Cloitre, Oct 25 2009
a(n) <= A093709(n). - Reinhard Zumkeller, Nov 14 2009
a(A000290(n)) = 1; a(A000037(n)) = 0. - Reinhard Zumkeller, Jun 20 2011
a(n) = 0 ^ A053186(n). - Reinhard Zumkeller, Feb 12 2012
a(n) = A063524(A007913(n)), for n > 0. - Reinhard Zumkeller, Jul 09 2014
a(n) = -(-1)^n * A258998(n) unless n = 0. 2 * a(n) = A000122(n) unless n = 0. - Michael Somos, Jun 16 2015
a(n) = A037011(A156552(n)), provided that A037011(n) = A000035(A106737(n)). [See A037011.] - Antti Karttunen, Nov 03 2017
a(n*m) = a(n/gcd(n,m))*a(m/gcd(n,m)) for all n and m > 0 (conjectured). - Velin Yanev, Feb 13 2019 [Proof from Michael B. Porter, Feb 16 2019: If nm is a square, nm = product_i (p_i^2), where p_i are prime, not necessarily distinct. Each p_i either appears twice in n, twice in m, or one time in each and therefore in the gcd. So n/gcd(n,m) and m/gcd(n,m) are both squares. If nm is not a square, there is a q_j that appears in one of n or m but not in the gcd. So either n/gcd(n,m) or m/gcd(n,m) is not a square.]
a(n) = Sum_{d|n} A008836(d), n >= 1, a(0) = 1. - Jinyuan Wang, Apr 20 2019
G.f.: A(q) = Sum_{n >= 0}  q^(2*n)*Product_{k >= 2*n+1} 1 - (-q)^k. - Peter Bala, Feb 22 2021
Multiplicative with a(p^e) = 1 if e is even, and 0 otherwise. - Amiram Eldar, Dec 29 2022
a(n) = Sum_{d|n} mobius(core(n)), where core(n) = A007913(n). - Peter Bala, Jan 24 2024

More terms from Franklin T. Adams-Watters, Jun 19 2006

A156552 Unary-encoded compressed factorization of natural numbers.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 8, 7, 6, 9, 16, 11, 32, 17, 10, 15, 64, 13, 128, 19, 18, 33, 256, 23, 12, 65, 14, 35, 512, 21, 1024, 31, 34, 129, 20, 27, 2048, 257, 66, 39, 4096, 37, 8192, 67, 22, 513, 16384, 47, 24, 25, 130, 131, 32768, 29, 36, 71, 258, 1025, 65536, 43, 131072, 2049, 38, 63, 68, 69, 262144

Offset: 1

Leonid Broukhis, Feb 09 2009

The primes become the powers of 2 (2 -> 1, 3 -> 2, 5 -> 4, 7 -> 8); the composite numbers are formed by taking the values for the factors in the increasing order, multiplying them by the consecutive powers of 2, and summing. See the Example section.
From Antti Karttunen, Jun 27 2014: (Start)
The odd bisection (containing even terms) halved gives A244153.
The even bisection (containing odd terms), when one is subtracted from each and halved, gives this sequence back.
(End)
Question: Are there any other solutions that would satisfy the recurrence r(1) = 0; and for n > 1, r(n) = Sum_{d|n, d>1} 2^A033265(r(d)), apart from simple variants 2^k * A156552(n)? See also A297112, A297113. - Antti Karttunen, Dec 30 2017

			For 84 = 2*2*3*7 -> 1*1 + 1*2 + 2*4 + 8*8 =  75.
For 105 = 3*5*7 -> 2*1 + 4*2 + 8*4 = 42.
For 137 = p_33 -> 2^32 = 4294967296.
For 420 = 2*2*3*5*7 -> 1*1 + 1*2 + 2*4 + 4*8 + 8*16 = 171.
For 147 = 3*7*7 = p_2 * p_4 * p_4 -> 2*1 + 8*2 + 8*4 = 50.

David A. Corneth, Table of n, a(n) for n = 1..10000 (first 1024 terms from Antti Karttunen)
Hans Havermann, Factorization of the first 10000 terms, in format [[primes], [exponents]]
A puzzle by Sergey Orlov (in Russian)
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers
Index entries for sequences computed from indices in prime factorization

One less than A005941.
Inverse permutation: A005940 with starting offset 0 instead of 1.
Cf. A000079, A000120, A001222, A052126, A054429, A061395, A064216, A064989, A003188, A243071, A243065-A243066, A244153, A243354, A112798, A125106, A056239, A161511.
Cf. also A297106, A297112 (Möbius transform), A297113, A153013, A290308, A300827, A323243, A323244, A323247, A324201, A324812 (n for which a(n) is a square), A324813, A324822, A324823, A324398, A324713, A324815, A324819, A324865, A324866, A324867.
Other related permutations: A253551, A253792, A253564, A253791, A277195, A297163, A297164, A297165, A297166, A302023, A305418, A322863, A322864.

Table[Floor@ Total@ Flatten@ MapIndexed[#1 2^(#2 - 1) &, Flatten[ Table[2^(PrimePi@ #1 - 1), {#2}] & @@@ FactorInteger@ n]], {n, 67}] (* Michael De Vlieger, Sep 08 2016 *)

a(n) = {my(f = factor(n), p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res}; \\ David A. Corneth, Mar 08 2019

A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A156552(n) = if(1==n, 0, if(!(n%2), 1+(2*A156552(n/2)), 2*A156552(A064989(n)))); \\ (based on the given recurrence) - Antti Karttunen, Mar 08 2019

# Program corrected per instructions from Leonid Broukhis. - Antti Karttunen, Jun 26 2014
# However, it gives correct answers only up to n=136, before corruption by a wrap-around effect.
# Note that the correct answer for n=137 is A156552(137) = 4294967296.
$max = $ARGV[0];
$pow = 0;
foreach $i (2..$max) {
@a = split(/ /, `factor $i`);
shift @a;
$shift = 0;
$cur = 0;
while ($n = int shift @a) {
$prime{$n} = 1 << $pow++ if !defined($prime{$n});
$cur |= $prime{$n} << $shift++;
}
print "$cur, ";
}
print "\n";
(Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library, two different implementations)
(definec (A156552 n) (cond ((= n 1) 0) (else (+ (A000079 (+ -2 (A001222 n) (A061395 n))) (A156552 (A052126 n))))))
(definec (A156552 n) (cond ((= 1 n) (- n 1)) ((even? n) (+ 1 (* 2 (A156552 (/ n 2))))) (else (* 2 (A156552 (A064989 n))))))
;; Antti Karttunen, Jun 26 2014

from sympy import primepi, factorint
def A156552(n): return sum((1<Chai Wah Wu, Mar 10 2023

From Antti Karttunen, Jun 26 2014: (Start)
a(1) = 0, a(n) = A000079(A001222(n)+A061395(n)-2) + a(A052126(n)).
a(1) = 0, a(2n) = 1+2*a(n), a(2n+1) = 2*a(A064989(2n+1)). [Compare to the entanglement recurrence A243071].
For n >= 0, a(2n+1) = 2*A244153(n+1). [Follows from the latter clause of the above formula.]
a(n) = A005941(n) - 1.
As a composition of related permutations:
a(n) = A003188(A243354(n)).
a(n) = A054429(A243071(n)).
For all n >= 1, A005940(1+a(n)) = n and for all n >= 0, a(A005940(n+1)) = n. [The offset-0 version of A005940 works as an inverse for this permutation.]
This permutations also maps between the partition-lists A112798 and A125106:
A056239(n) = A161511(a(n)). [The sums of parts of each partition (the total sizes).]
A003963(n) = A243499(a(n)). [And also the products of those parts.]
(End)
From Antti Karttunen, Oct 09 2016: (Start)
A161511(a(n)) = A056239(n).
A029837(1+a(n)) = A252464(n). [Binary width of terms.]
A080791(a(n)) = A252735(n). [Number of nonleading 0-bits.]
A000120(a(n)) = A001222(n). [Binary weight.]
For all n >= 2, A001511(a(n)) = A055396(n).
For all n >= 2, A000120(a(n))-1 = A252736(n). [Binary weight minus one.]
A252750(a(n)) = A252748(n).
a(A250246(n)) = A252754(n).
a(A005117(n)) = A277010(n). [Maps squarefree numbers to a permutation of A003714, fibbinary numbers.]
A085357(a(n)) = A008966(n). [Ditto for their characteristic functions.]
For all n >= 0:
a(A276076(n)) = A277012(n).
a(A276086(n)) = A277022(n).
a(A260443(n)) = A277020(n).
(End)
From Antti Karttunen, Dec 30 2017: (Start)
For n > 1, a(n) = Sum_{d|n, d>1} 2^A033265(a(d)). [See comments.]
More linking formulas:
A106737(a(n)) = A000005(n).
A290077(a(n)) = A000010(n).
A069010(a(n)) = A001221(n).
A136277(a(n)) = A181591(n).
A132971(a(n)) = A008683(n).
A106400(a(n)) = A008836(n).
A268411(a(n)) = A092248(n).
A037011(a(n)) = A010052(n) [conjectured, depends on the exact definition of A037011].
A278161(a(n)) = A046951(n).
A001316(a(n)) = A061142(n).
A277561(a(n)) = A034444(n).
A286575(a(n)) = A037445(n).
A246029(a(n)) = A181819(n).
A278159(a(n)) = A124859(n).
A246660(a(n)) = A112624(n).
A246596(a(n)) = A069739(n).
A295896(a(n)) = A053866(n).
A295875(a(n)) = A295297(n).
A284569(a(n)) = A072411(n).
A286574(a(n)) = A064547(n).
A048735(a(n)) = A292380(n).
A292272(a(n)) = A292382(n).
A244154(a(n)) = A048673(n), a(A064216(n)) = A244153(n).
A279344(a(n)) = A279339(n), a(A279338(n)) = A279343(n).
a(A277324(n)) = A277189(n).
A037800(a(n)) = A297155(n).
For n > 1, A033265(a(n)) = 1+A297113(n).
(End)
From Antti Karttunen, Mar 08 2019: (Start)
a(n) = A048675(n) + A323905(n).
a(A324201(n)) = A000396(n), provided there are no odd perfect numbers.
The following sequences are derived from or related to the base-2 expansion of a(n):
A000265(a(n)) = A322993(n).
A002487(a(n)) = A323902(n).
A005187(a(n)) = A323247(n).
A324288(a(n)) = A324116(n).
A323505(a(n)) = A323508(n).
A079559(a(n)) = A323512(n).
A085405(a(n)) = A323239(n).
The following sequences are obtained by applying to a(n) a function that depends on the prime factorization of its argument, which goes "against the grain" because a(n) is the binary code of the factorization of n, which in these cases is then factored again:
A000203(a(n)) = A323243(n).
A033879(a(n)) = A323244(n) = 2*a(n) - A323243(n),
A294898(a(n)) = A323248(n).
A000005(a(n)) = A324105(n).
A000010(a(n)) = A324104(n).
A083254(a(n)) = A324103(n).
A001227(a(n)) = A324117(n).
A000593(a(n)) = A324118(n).
A001221(a(n)) = A324119(n).
A009194(a(n)) = A324396(n).
A318458(a(n)) = A324398(n).
A192895(a(n)) = A324100(n).
A106315(a(n)) = A324051(n).
A010052(a(n)) = A324822(n).
A053866(a(n)) = A324823(n).
A001065(a(n)) = A324865(n) = A323243(n) - a(n),
A318456(a(n)) = A324866(n) = A324865(n) OR a(n),
A318457(a(n)) = A324867(n) = A324865(n) XOR a(n),
A318458(a(n)) = A324398(n) = A324865(n) AND a(n),
A318466(a(n)) = A324819(n) = A323243(n) OR 2*a(n),
A318467(a(n)) = A324713(n) = A323243(n) XOR 2*a(n),
A318468(a(n)) = A324815(n) = A323243(n) AND 2*a(n).
(End)

More terms from Antti Karttunen, Jun 28 2014

cp's OEIS Frontend

A324058 a(n) = A324121(A005940(1+n)) = gcd(A324054(n), A005940(1+n)*A106737(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A000005 d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Haskell

Julia

Magma

Maple

Mathematica

MuPAD

PARI

PARI

PARI

Python

Sage

Formula

Extensions

A005940 The Doudna sequence: write n-1 in binary; power of prime(k) in a(n) is # of 1's that are followed by k-1 0's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A010052 Characteristic function of squares: a(n) = 1 if n is a square, otherwise 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Scheme

Formula

Extensions

A156552 Unary-encoded compressed factorization of natural numbers.

Views

Author

Keywords

Comments

Examples

A252754 Inverse of "Tree of Eratosthenes" permutation: a(1) = 0, after which, a(2n) = 1 + 2a(n), a(2n+1) = 2 a(A268674(2n+1)).