A143327 -id:A143327 - cp's OEIS frontend

A085945 Number of subsets of {1,2,...,n} with relatively prime elements.

1, 2, 5, 11, 26, 53, 116, 236, 488, 983, 2006, 4016, 8111, 16238, 32603, 65243, 130778, 261566, 523709, 1047479, 2095988, 4192115, 8386418, 16772858, 33550058, 67100393, 134209001, 268418531, 536853986, 1073707991, 2147449814, 4294900694, 8589866963

Offset: 1

Vladeta Jovovic, Aug 17 2003

nonn

			For n=4 there are 11 such subsets: {1}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}.

Alois P. Heinz, Table of n, a(n) for n = 1..3321 (first 300 terms from T. D. Noe)
Mohamed Ayad and Omar Kihel, The number of relatively prime subsets of {1,2,...,n}, Integers 9, No. 2, Article A14, 163-166 (2009).
M. Ayad, V. Coia and O. Kihel, The Number of Relatively Prime Subsets of a Finite Union of Sets of Consecutive Integers, J. Int. Seq. 17 (2014) # 14.3.7, Theorem 1.
Mohamed El Bachraoui and Florian Luca, On a Diophantine equation of Ayad and Kihel, Quaestiones Mathematicae, Volume 35, Issue 2, pages 235-243, 2012; DOI:10.2989/16073606.2012.697265. - _N. J. A. Sloane_, Nov 29 2012
Adrian Łydka, On some properties of the function of the number of relatively prime subsets of {1,2,...,n}, arXiv:1910.02418 [math.NT], 2019.
Melvyn B. Nathanson, Affine Invariants, Relatively Prime Sets and a Phi Function for Subsets of {1, 2, ..., n}, INTEGERS: Electronic Journal of Combinatorial Number Theory, 7 (2007), #A1.
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.
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.

Cf. A000740, A109511.
Row sums of A143446.
Column k=2 of A143327.

b:= n-> add(`if`(d=n, 2^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..35);  # Alois P. Heinz, Oct 05 2018

Table[Sum[MoebiusMu[k] (2^Floor[n/k] - 1), {k, 1, n}], {n, 1, 31}]  (* Geoffrey Critzer, Jan 03 2012 *)

a(n)=sum(k=1,n,moebius(k)*(2^floor(n/k)-1)) \\ Charles R Greathouse IV, Feb 04 2013

Partial sums of A000740. G.f.: 1/(1-x)* Sum_{k>0} mu(k)*x^k/(1-2*x^k).
a(n) = 2^n - A109511(n) - 1. - Reinhard Zumkeller, Jul 01 2005
a(n) = Sum_{k=1..n} mu(k)*(2^floor(n/k)-1). - Geoffrey Critzer, Jan 03 2012

A143326 Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words with length less than or equal to n (n,k >= 1).

Original entry on oeis.org

1, 2, 1, 3, 4, 1, 4, 9, 10, 1, 5, 16, 33, 22, 1, 6, 25, 76, 105, 52, 1, 7, 36, 145, 316, 345, 106, 1, 8, 49, 246, 745, 1336, 1041, 232, 1, 9, 64, 385, 1506, 3865, 5356, 3225, 472, 1, 10, 81, 568, 2737, 9276, 19345, 21736, 9705, 976, 1, 11, 100, 801, 4600, 19537, 55686

Offset: 1

Alois P. Heinz, Aug 07 2008

The coefficients of the polynomial of row n are given by the n-th row of triangle A134541; for example row 4 has polynomial -k+k^3+k^4.

			T(2,3) = 9, because there are 9 primitive words of length less than or equal to 2 over 3-letter alphabet {a,b,c}: a, b, c, ab, ac, ba, bc, ca, cb; note that the non-primitive words aa, bb and cc don't belong to the list; secondly note that the words in the list need not be Lyndon words, for example ba can be derived from ab by a cyclic rotation of the positions.
Table begins:
  1,   2,    3,     4,      5,       6,       7,        8, ...
  1,   4,    9,    16,     25,      36,      49,       64, ...
  1,  10,   33,    76,    145,     246,     385,      568, ...
  1,  22,  105,   316,    745,    1506,    2737,     4600, ...
  1,  52,  345,  1336,   3865,    9276,   19537,    37360, ...
  1, 106, 1041,  5356,  19345,   55686,  136801,   298936, ...
  1, 232, 3225, 21736,  97465,  335616,  960337,  2396080, ...
  1, 472, 9705, 87016, 487465, 2013936, 6722737, 19169200, ...
  ...
From _Wolfdieter Lang_, Feb 01 2014: (Start)
The triangle Tri(n,m) := T(m,n-(m-1)) begins:
n\m  1   2    3     4     5      6      7     8    9  10 ...
1:   1
2:   2   1
3:   3   4    1
4:   4   9   10     1
5:   5  16   33    22     1
6:   6  25   76   105    52      1
7:   7  36  145   316   345    106      1
8:   8  49  246   745  1336   1041    232     1
9:   9  64  385  1506  3865   5356   3225   472    1
10: 10  81  568  2737  9276  19345  21736  9705  976   1
...
For the columns see A000027, A000290, A081437, ... (End)

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to Lyndon words

Column 1: A000012. Rows 1-3: A000027, A000290, A081437 and A085490. See also A143324, A143327, A134541, A008683.

with(numtheory):
f0:= proc(n) option remember;
       unapply(k^n-add(f0(d)(k), d=divisors(n) minus {n}), k)
     end:
g0:= proc(n) option remember; unapply(add(f0(j)(x), j=1..n), x) end:
T:= (n, k)-> g0(n)(k):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

f0[n_] := f0[n] = Function[k, k^n-Sum[f0[d][k], {d, Divisors[n] // Most}]]; g0[n_] := g0[n] = Function[x, Sum[f0[j][x], {j, 1, n}]]; T[n_, k_] := g0[n][k]; Table[T[n, 1+d-n], {d, 1, 12}, {n, 1, d}]//Flatten (* Jean-François Alcover, Feb 12 2014, translated from Maple *)

T(n,k) = Sum_{1<=j<=n} Sum_{d|j} k^d * mu(j/d).
T(n,k) = Sum_{1<=j<=n} A143324(j,k).
T(n,k) = A143327(n,k) * k.

A320087 Number of primitive (=aperiodic) ternary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 3, 11, 35, 115, 347, 1075, 3235, 9787, 29387, 88435, 265315, 796755, 2390347, 7173227, 21519947, 64566667, 193700035, 581120523, 1743362283, 5230145947, 15690440099, 47071499707, 141214499227, 423644035627, 1270932113627, 3812797935395, 11438393826035

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..2096

Column k=3 of A143327.
Partial sums of A034741.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 3^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

nmax = 20; Rest[CoefficientList[Series[1/(1-x) * Sum[MoebiusMu[k] * x^k / (1 - 3*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

a(n) = sum(j=1, n, sumdiv(j, d, 3^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 3^(d-1) * mu(j/d).
a(n) = A143327(n,3).
a(n) = Sum_{j=1..n} A143325(j,3).
a(n) = A143326(n,3) / 3.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 3*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320088 Number of primitive (=aperiodic) 4-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 4, 19, 79, 334, 1339, 5434, 21754, 87274, 349159, 1397734, 5590954, 22368169, 89472934, 357908119, 1431633559, 5726600854, 22906403494, 91625880229, 366503524969, 1466015148634, 5864060611159, 23456246655574, 93824986622614, 375299963333014, 1501199853398419

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1661

Column k=4 of A143327.
Partial sums of A295505.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 4^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

nmax = 20; Rest[CoefficientList[Series[1/(1-x) * Sum[MoebiusMu[k] * x^k / (1 - 4*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

a(n) = sum(j=1, n, sumdiv(j, d, 4^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 4^(d-1) * mu(j/d).
a(n) = A143327(n,4).
a(n) = Sum_{j=1..n} A143325(j,4).
a(n) = A143326(n,4) / 4.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 4*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320089 Number of primitive (=aperiodic) 5-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 5, 29, 149, 773, 3869, 19493, 97493, 488093, 2440589, 12206213, 61031093, 305171717, 1525859213, 7629374189, 38146874189, 190734764813, 953673824213, 4768371089837, 23841855464717, 119209287089693, 596046435527189, 2980232226542813, 14901161132714813

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1431

Column k=5 of A143327.
Partial sums of A295506.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 5^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

nmax = 20; Rest[CoefficientList[Series[1/(1-x) * Sum[MoebiusMu[k] * x^k / (1 - 5*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

a(n) = sum(j=1, n, sumdiv(j, d, 5^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 5^(d-1) * mu(j/d).
a(n) = A143327(n,5).
a(n) = Sum_{j=1..n} A143325(j,5).
a(n) = A143326(n,5) / 5.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 5*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320090 Number of primitive (=aperiodic) 6-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 6, 41, 251, 1546, 9281, 55936, 335656, 2015236, 12091631, 72557806, 435346876, 2612129211, 15672776566, 94036939331, 564221643971, 3385331551426, 20311989308806, 121871945977221, 731231675909811, 4387390115926096, 26324340695837771, 157946044538104906

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1285

Column k=6 of A143327.
Partial sums of A320071.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 6^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

nmax = 20; Rest[CoefficientList[Series[1/(1-x) * Sum[MoebiusMu[k] * x^k / (1 - 6*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

a(n) = sum(j=1, n, sumdiv(j, d, 6^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 6^(d-1) * mu(j/d).
a(n) = A143327(n,6).
a(n) = Sum_{j=1..n} A143325(j,6).
a(n) = A143326(n,6) / 6.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 6*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320091 Number of primitive (=aperiodic) 7-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 7, 55, 391, 2791, 19543, 137191, 960391, 6725143, 47076343, 329551591, 2306861191, 16148148391, 113037041143, 791260111543, 5538820797943, 38771751367543, 271402259573191, 1899815857483639, 13298711002502839, 93090977299997143, 651636841100805895

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1184

Column k=7 of A143327.
Partial sums of A320072.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 7^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

a(n) = sum(j=1, n, sumdiv(j, d, 7^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 7^(d-1) * mu(j/d).
a(n) = A143327(n,7).
a(n) = Sum_{j=1..n} A143325(j,7).
a(n) = A143326(n,7) / 7.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 7*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320092 Number of primitive (=aperiodic) 8-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 8, 71, 575, 4670, 37367, 299510, 2396150, 19173302, 153386927, 1227128750, 9817030070, 78536506805, 628292058542, 5026338565487, 40210708557167, 321685685267822, 2573485482143150, 20587883991625133, 164703071933262773, 1317624576539847542

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1108

Column k=8 of A143327.
Partial sums of A320073.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 8^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

a(n) = sum(j=1, n, sumdiv(j, d, 8^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 8^(d-1) * mu(j/d).
a(n) = A143327(n,8).
a(n) = Sum_{j=1..n} A143325(j,8).
a(n) = A143326(n,8) / 8.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 8*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320093 Number of primitive (=aperiodic) 9-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 9, 89, 809, 7369, 66329, 597769, 5380009, 48426649, 435840569, 3922624969, 35303624809, 317733161289, 2859598458169, 25736390906489, 231627518218169, 2084647707070009, 18761829363630889, 168856464660630009, 1519708181946200889, 13677373641002598169

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1048

Column k=9 of A143327.
Partial sums of A320074.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 9^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

a(n) = sum(j=1, n, sumdiv(j, d, 9^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 9^(d-1) * mu(j/d).
a(n) = A143327(n,9).
a(n) = Sum_{j=1..n} A143325(j,9).
a(n) = A143326(n,9) / 9.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 9*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320094 Number of primitive (=aperiodic) 10-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 10, 109, 1099, 11098, 110989, 1110988, 11109988, 111109888, 1111099879, 11111099878, 111110998888, 1111110998887, 11111109998878, 111111109988779, 1111111099988779, 11111111099988778, 111111110999888878, 1111111110999888877, 11111111109999887887

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Column k=10 of A143327.
Partial sums of A320075.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 10^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

a(n) = sum(j=1, n, sumdiv(j, d, 10^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 10^(d-1) * mu(j/d).
a(n) = A143327(n,10).
a(n) = Sum_{j=1..n} A143325(j,10).
a(n) = A143326(n,10) / 10.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 10*x^k). - Ilya Gutkovskiy, Dec 11 2020

cp's OEIS Frontend

A085945 Number of subsets of {1,2,...,n} with relatively prime elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A143326 Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words with length less than or equal to n (n,k >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320087 Number of primitive (=aperiodic) ternary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A320088 Number of primitive (=aperiodic) 4-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A320089 Number of primitive (=aperiodic) 5-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A320090 Number of primitive (=aperiodic) 6-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A320091 Number of primitive (=aperiodic) 7-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A320092 Number of primitive (=aperiodic) 8-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.