A020921 -id:A020921 - cp's OEIS frontend

A038199 Row sums of triangle T(m,n) = number of solutions to 1 <= a(1) < a(2) < ... < a(m) <= n, where gcd(a(1), a(2), ..., a(m), n) = 1, in A020921.

1, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730, 65280, 131070, 261576, 524286, 1047540, 2097018, 4192254, 8388606, 16772880, 33554400, 67100670, 134217216, 268419060, 536870910, 1073708010, 2147483646

Offset: 1

Temba Shonhiwa (Temba(AT)maths.uz.ac.zw)

The function T(m,n) described above has an inverse: see A038200.

Also, Moebius transform of 2^n - 1 = A000225. Also, number of rationals in [0, 1) whose binary expansions consist just of repeating bits of (least) period exactly n (i.e., there's no preperiodic part), where 0 = 0.000... is considered to have period 1. - Brad Chalfan (brad(AT)chalfan.net), May 29 2006

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Henk Bruin, Carlo Carminati, and Charlene Kalle, Matching for generalised beta-transformations, arXiv preprint arXiv:1610.01872 [math.DS], 2016.
Henk Bruin, Carlo Carminati, and Charlene Kalle, Matching for generalised beta-transformations, Indagationes Mathematicae 28 (2017), 55-73.
Jason D. Chadwick, Mariesa H. Teo, Joshua Viszlai, Willers Yang, and Frederic T. Chong, Erasure Minesweeper: exploring hybrid-erasure surface code architectures for efficient quantum error correction, arXiv:2505.00066 [quant-ph], 2025. See p. 14.
Melvyn B. Nathanson, Primitive sets and Euler phi function for subsets of {1,2,...,n}, arXiv:math/0608150 [math.NT], 2006-2007.
Prapanpong Pongsriiam, Relatively Prime Sets, Divisor Sums, and Partial Sums, arXiv:1306.4891 [math.NT], 2013 and J. Int. Seq. 16 (2013) #13.9.1.
Prapanpong Pongsriiam, A remark on relatively prime sets, Integers 13 (2013), A49.
Temba Shonhiwa, A Generalization of the Euler and Jordan Totient Functions, Fib. Quart., 37 (1999), 67-76.
Wikipedia, Lambert series.

A027375, A038199 and A056267 are all essentially the same sequence with different initial terms.
Cf. A000225, A008683, A020921, A023995, A027750, A038200, A130887.
Cf. A059966 (a(n)/n).

a038199 n = sum [a008683 (n `div` d) * (a000225 d)| d <- a027750_row n]
-- Reinhard Zumkeller, Feb 17 2013

Table[Plus@@((2^Divisors[n]-1)MoebiusMu[n/Divisors[n]]),{n,1,31}] (* Brad Chalfan (brad(AT)chalfan.net), May 29 2006 *)

a(n) = sumdiv(n, d, moebius(n/d)*(2^d-1)); \\ Michel Marcus, Jun 28 2017

from sympy import mobius, divisors
def a(n): return sum(mobius(n//d) * (2**d - 1) for d in divisors(n))
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d | n} mu(n/d)*(2^d-1). - Paul Barry, Mar 20 2005
Lambert g.f.: Sum_{n>=1} a(n)*x^n/(1 - x^n) = x/((1 - x)*(1 - 2*x)). - Ilya Gutkovskiy, Apr 25 2017
O.g.f.: Sum_{d >= 1} mu(d)*x^d/((1 - x^d)*(1 - 2*x^d)). - Petros Hadjicostas, Jun 18 2019

Better description from Michael Somos
More terms from Naohiro Nomoto, Sep 10 2001
More terms from Brad Chalfan (brad(AT)chalfan.net), May 29 2006

A038200 Row sums of triangle K(m, n), inverse to triangle T(m,n) in A020921.

Original entry on oeis.org

1, 0, -1, 3, -8, 21, -54, 134, -318, 720, -1560, 3259, -6641, 13391, -27107, 55657, -116244, 245823, -521738, 1101566, -2299215, 4730990, -9601095, 19273729, -38446742, 76598275, -153119606, 308061214, -624460449, 1274268038, -2611866713, 5362888620, -11003127203, 22516189988

Offset: 1

Temba Shonhiwa (Temba(AT)maths.uz.ac.zw)

sign

The triangle K is A126713.

Temba Shonhiwa, A Generalization of the Euler and Jordan Totient Functions, Fib. Quart., 37 (1999), 67-76.
N. J. A. Sloane, Transforms

Cf. A126713, A020921.

Inverse binomial transform of tau(n) = A000005(n): Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*A000005(k). - Vladeta Jovovic, Oct 29 2002

E.g.f.: exp(-x)*Sum_{k>=1} d(k)*x^k/k!. - Ilya Gutkovskiy, Nov 26 2017

Better description from Michael Somos

A027375 Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.

Original entry on oeis.org

0, 2, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730, 65280, 131070, 261576, 524286, 1047540, 2097018, 4192254, 8388606, 16772880, 33554400, 67100670, 134217216, 268419060, 536870910, 1073708010, 2147483646, 4294901760

Offset: 0

N. J. A. Sloane

A sequence S is aperiodic if it is not of the form S = T^k with k>1. - N. J. A. Sloane, Oct 26 2012
Equivalently, number of output sequences with primitive period n from a simple cycling shift register. - Frank Ruskey, Jan 17 2000
Also, the number of nonempty subsets A of the set of the integers 1 to n such that gcd(A) is relatively prime to n (for n>1). - R. J. Mathar, Aug 13 2006; range corrected by Geoffrey Critzer, Dec 07 2014
Without the first term, this sequence is the Moebius transform of 2^n (n>0). For n > 0, a(n) is also the number of periodic points of period n of the transform associated to the Kolakoski sequence A000002. This 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 2 periodic points of period 2. A001037(n) = a(n)/n gives the number of orbits of size n. - Jean-Christophe Hervé, Oct 25 2014
From Bernard Schott, Jun 19 2019: (Start)
There are 2^n strings of length n that can be formed from the symbols 0 and 1; in the example below with a(3) = 6, the last two strings that are not aperiodic binary strings are { 000, 111 }, corresponding to 0^3 and 1^3, using the notation of the first comment.
Two properties mentioned by Krusemeyer et al. are:
1) For any n > 2, a(n) is divisible by 6.
2) Lim_{n->oo} a(n+1)/a(n) = 2. (End)

			a(3) = 6 = |{ 001, 010, 011, 100, 101, 110 }|. - corrected by _Geoffrey Critzer_, Dec 07 2014

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 13. - From N. J. A. Sloane, Oct 26 2012
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
Blanchet-Sadri, Francine. Algorithmic combinatorics on partial words. Chapman & Hall/CRC, Boca Raton, FL, 2008. ii+385 pp. ISBN: 978-1-4200-6092-8; 1-4200-6092-9 MR2384993 (2009f:68142). See p. 164.
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967.
Mark I. Krusemeyer, George T. Gilbert, Loren C. Larson, A Mathematical Orchard, Problems and Solutions, MAA, 2012, Problem 128, pp. 225-227.

T. D. Noe, Table of n, a(n) for n = 0..300
J.-P. Allouche, Note on the transcendence of a generating function. In A. Laurincikas and E. Manstavicius, editors, Proceedings of the Palanga Conference for the 75th birthday of Prof. Kubilius, New trends in Probab. and Statist., Vol. 4, pages 461-465, 1997.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], Dec 25 2012.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
John D. Cook, Counting primitive bit strings (2014).
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 85.
Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit and Taylor J. Smith, Periodicity in rectangular arrays, arXiv:1602.06915 [cs.DM], 2016; Information Processing Letters 118 (2017) 58-63. See Table 1.
O. Georgiou, C. P. Dettmann and E. G. Altmann, Faster than expected escape for a class of fully chaotic maps, arXiv preprint arXiv:1207.7000 [nlin.CD], 2012. - From _N. J. A. Sloane_, Dec 23 2012
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
David W. Lyons, Cristina Mullican, Adam Rilatt, and Jack D. Putnam, Werner states from diagrams, arXiv:2302.05572 [quant-ph], 2023.
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
M. B. Nathanson, Primitive sets and Euler phi function for subsets of {1,2,...,n}, arXiv:math/0608150 [math.NT], 2006-2007.
P. Pongsriiam, Relatively Prime Sets, Divisor Sums, and Partial Sums, arXiv:1306.4891 [math.NT], 2013 and J. Int. Seq. 16 (2013) #13.9.1.
P. Pongsriiam, A remark on relative prime sets, arXiv:1306.2529 [math.NT], 2013.
P. Pongsriiam, A remark on relative prime sets, Integers 13 (2013), A49.
R. C. Read, Combinatorial problems in the theory of music, Disc. Math. 167/168 (1997) 543-551, sequence A(n).
M. Tang, Relatively Prime Sets and a Phi Function for Subsets of {1, 2, ... , n}, J. Int. Seq. 13 (2010) # 10.7.6.
László Tóth, Menon-type identities concerning subsets of the set {1,2,...,n}, arXiv:2109.06541 [math.NT], 2021.

A038199 and A056267 are essentially the same sequence with different initial terms.
Cf. A020921, A216953.
Column k=2 of A143324.

a027375 n = n * a001037 n  -- Reinhard Zumkeller, Feb 01 2013

with(numtheory): A027375 :=n->add( mobius(d)*2^(n/d), d = divisors(n)); # N. J. A. Sloane, Sep 25 2012

Table[ Apply[ Plus, MoebiusMu[ n / Divisors[n] ]*2^Divisors[n] ], {n, 1, 32} ]
a[0]=0; a[n_] := DivisorSum[n, MoebiusMu[n/#]*2^#&]; Array[a, 40, 0] (* Jean-François Alcover, Dec 01 2015 *)

PARI
```
a(n) = sumdiv(n,d,moebius(n\d)*2^d);
```

from sympy import mobius, divisors
def a(n): return sum(mobius(d)*2**(n//d) for d in divisors(n))
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d|n} mu(d)*2^(n/d).
a(n) = 2*A000740(n).
a(n) = n*A001037(n).
Sum_{d|n} a(n) = 2^n.
a(p) = 2^p - 2 for p prime. - R. J. Mathar, Aug 13 2006
a(n) = 2^n - O(2^(n/2)). - Charles R Greathouse IV, Apr 28 2016
a(n) = 2^n - A152061(n). - Bernard Schott, Jun 20 2019
G.f.: 2 * Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Nov 11 2019

A102309 a(n) = Sum_{d divides n} moebius(d) * binomial(n/d,2).

Original entry on oeis.org

0, 0, 1, 3, 5, 10, 11, 21, 22, 33, 34, 55, 46, 78, 69, 92, 92, 136, 105, 171, 140, 186, 175, 253, 188, 290, 246, 315, 282, 406, 284, 465, 376, 470, 424, 564, 426, 666, 531, 660, 568, 820, 570, 903, 710, 852, 781, 1081, 760, 1155, 890, 1136, 996, 1378, 963, 1420, 1140, 1422, 1246

Offset: 0

Ralf Stephan, Jan 03 2005

nonn

Zero followed by the Moebius transform of A000217. - R. J. Mathar, Jan 19 2009
Apparently, a(n-1) is the number of periodic complex Horadam orbits with period n, for n>2. - Nathaniel Johnston, Oct 04 2013
Also apparently, the first differences of A100448 (checked up to n=2000).

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Dorin Andrica and Ovidiu Bagdasar, Recurrent Sequences: Key Results, Applications, and Problems, Springer (2020), p. 159.
Ovidiu Bagdasar, On certain computational and geometric properties of complex Horadam orbits, poster, ANTS 2014.
Ovidiu D. Bagdasar and Peter J. Larcombe, On the characterization of periodic complex Horadam sequences, Fib. Quart. 51 (1) (2013) 28-37.
Ovidiu D. Bagdasar and Peter J. Larcombe, On the Number of Complex Horadam Sequences with a Fixed Period, Fib. Q., 51 (2013), 339-347.
Ovidiu D. Bagdasar and Peter J. Larcombe, On the masked periodicity of Horadam sequences: a generator-based approach, Fib. Q., 55 (2017), 332-339.
Ovidiu Bagdasar and Ioan-Lucian Popa, On the geometry of certain periodic non-homogeneous Horadam sequences, Electronic Notes in Discrete Mathematics 56 (2016) 7-13.

Second column of triangle A020921.

Cf. A002117, A008683, A100448, A326419.

with(numtheory):
a:= n-> add(mobius(d)*binomial(n/d, 2), d=divisors(n)):
seq(a(n), n=0..60);  # Alois P. Heinz, Feb 18 2013

a[n_] := Sum[MoebiusMu[d] Binomial[n/d, 2], {d, Divisors[n]}];
a /@ Range[0, 60] (* Jean-François Alcover, Feb 04 2020 *)

a(n) = sumdiv(n, d, moebius(d) * binomial(n/d,2) ); /* Joerg Arndt, Feb 18 2013 */

my(N=66, x='x+O('x^N)); concat([0, 0], Vec(sum(k=1, N, moebius(k)*x^(2*k)/(1-x^k)^3))) \\ Seiichi Manyama, May 24 2021

from math import comb
from sympy import mobius, divisors
def A102309(n): return sum(mobius(d)*comb(n//d,2) for d in divisors(n,generator=True)) # Chai Wah Wu, May 09 2025

G.f.: Sum_{k>=1} mu(k) * x^(2*k)/(1 - x^k)^3. - Seiichi Manyama, May 24 2021

Sum_{k=1..n} a(k) ~ n^3 / (6*zeta(3)). - Amiram Eldar, Jun 08 2025

A126713 The triangle K referred to in A038200, read along rows.

Original entry on oeis.org

1, -1, 1, 1, -3, 1, -1, 7, -4, 1, 1, -15, 10, -5, 1, -1, 31, -19, 15, -6, 1, 1, -63, 28, -35, 21, -7, 1, -1, 127, -28, 71, -56, 28, -8, 1, 1, -255, 1, -135, 126, -84, 36, -9, 1, -1, 511, 80, 255, -251, 210, -120, 45, -10, 1, 1, -1023, -242, -495, 451, -462, 330, -165, 55, -11, 1, -1, 2047, 485, 991, -726, 925, -792, 495, -220

Offset: 0

R. J. Mathar, Feb 12 2007

This means the description of A038200 is slightly incorrect and ought be: "Row sums of triangle K(m,n), inverse to a triangle obtained from A020921 after eliminating the leftmost column."

			If the leftmost column of the triangle in A020921 is deleted we get
1
1 1
2 3 1
2 5 4 1
4 10 10 5 1
2 11 19 15 6 1
6 21 35 35 21 7 1
4 22 52 69 56 28 8 1
6 33 83 126 126 84 36 9 1
The present triangle is the inverse of this, namely
1
-1 1
1 -3 1
-1 7 -4 1
1 -15 10 -5 1
-1 31 -19 15 -6 1
1 -63 28 -35 21 -7 1
-1 127 -28 71 -56 28 -8 1
with row sums 1,0,-1,3,-8,21,-54,134,-318,720 of A038200.

Cf. A039912.

A020921 := proc(n,k) option remember; local divs; if n <= 0 then 1; elif k > n then 0; else divs := numtheory[divisors](n); add(numtheory[mobius](op(i,divs))*binomial(n/op(i,divs),k),i=1..nops(divs)); fi; end: A020921t := proc(n,k) option remember; A020921(n+1,k+1); end: TriLInv := proc(nmax) local a,row,col; a := array(0..nmax,0..nmax); for row from 0 to nmax do for col from row+1 to nmax do a[row,col] := 0; od; od; for row from 0 to nmax do for col from row to 0 by -1 do if row <> col then a[row,col] := -add(a[row,c]*A020921t(c,col),c=col+1..row)/A020921t(col,col); else a[row,col] := (1-add(a[row,c]*A020921t(c,col),c=col+1..row))/A020921t(col,col); fi; od; od; RETURN(a); end: nmax := 12 : a := TriLInv(nmax) : for row from 0 to nmax do for col from 0 to row do printf("%d, ",a[row,col]); od; od:

f[n_] := (1/(1+x))*Sum[x^(k-1)/((1+x)^k-y*x^k), {k, 1, n+1}]; t[0, 0] = 1; t[n_, k_] := SeriesCoefficient[f[n], {x, 0, n}, {y, 0, k}]; Table[t[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 13 2013, after Vladeta Jovovic *)

G.f.: (1/(1+x))*Sum(x^(k-1)/((1+x)^k-y*x^k),k=1..infinity). - Vladeta Jovovic, Feb 26 2008

cp's OEIS Frontend

A038199 Row sums of triangle T(m,n) = number of solutions to 1 <= a(1) < a(2) < ... < a(m) <= n, where gcd(a(1), a(2), ..., a(m), n) = 1, in A020921.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

Extensions

A038200 Row sums of triangle K(m, n), inverse to triangle T(m,n) in A020921.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A027375 Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A102309 a(n) = Sum_{d divides n} moebius(d) * binomial(n/d,2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A126713 The triangle K referred to in A038200, read along rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A346760 a(n) = Sum_{d|n} mu(n/d) * binomial(d,3).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

A346761 a(n) = Sum_{d|n} mu(n/d) * binomial(d,4).

Views

Author

Keywords

Crossrefs

Programs