A015614 -id:A015614 - cp's OEIS frontend

A343659 Number of maximal pairwise coprime subsets of {1..n}.

1, 1, 1, 2, 2, 3, 3, 4, 7, 9, 9, 10, 10, 12, 16, 19, 19, 20, 20, 22, 28, 32, 32, 33, 54, 61, 77, 84, 84, 85, 85, 94, 112, 123, 158, 161, 161, 176, 206, 212, 212, 214, 214, 229, 241, 260, 260, 263, 417, 428, 490, 521, 521, 526, 655, 674, 764, 818, 818, 820, 820, 874, 918, 975, 1182, 1189, 1189

Offset: 1

Gus Wiseman, Apr 26 2021

nonn

For this sequence, it does not matter whether singletons are considered pairwise coprime.
For n > 2, also the number of maximal pairwise coprime subsets of {2..n}.
For each prime p <= n, p divides exactly one element of each maximal subset. - Bert Dobbelaere, May 04 2021

			The a(1) = 1 through a(9) = 7 subsets:
  {1}  {12}  {123}  {123}  {1235}  {156}   {1567}   {1567}   {1567}
                    {134}  {1345}  {1235}  {12357}  {12357}  {12357}
                                   {1345}  {13457}  {13457}  {12579}
                                                    {13578}  {13457}
                                                             {13578}
                                                             {14579}
                                                             {15789}

Bert Dobbelaere, Table of n, a(n) for n = 1..500
Bert Dobbelaere, Python program

The case of pairs is A015614.
The case of triples is A015617.
The non-maximal version counting empty sets and singletons is A084422.
The non-maximal version counting singletons is A187106.
The non-maximal version is A320426(n) = A276187(n) + 1.
The version for indivisibility instead of coprimality is A326077.
The version for sets of divisors is A343652.
The version for sets of divisors > 1 is A343660.
A018892 counts coprime unordered pairs of divisors.
A051026 counts pairwise indivisible subsets of {1..n}.
A100565 counts pairwise coprime unordered triples of divisors.
Cf. A007360, A067824, A087087, A225520, A324837, A325683, A325859, A326358, A326496, A326675, A333227, A343653, A343655.

fasmax[y_]:=Complement[y,Union@@Most@*Subsets/@y];
Table[Length[fasmax[Select[Subsets[Range[n]],CoprimeQ@@#&]]],{n,15}]

More terms from Bert Dobbelaere, May 04 2021

A320436 Irregular triangle read by rows where T(n,k) is the number of pairwise coprime k-subsets of {1,...,n}, 1 <= k <= A036234(n), where a single number is not considered to be pairwise coprime unless it is equal to 1.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 2, 1, 9, 7, 2, 1, 11, 8, 2, 1, 17, 19, 10, 2, 1, 21, 25, 14, 3, 1, 27, 37, 24, 6, 1, 31, 42, 26, 6, 1, 41, 73, 68, 32, 6, 1, 45, 79, 72, 33, 6, 1, 57, 124, 151, 105, 39, 6, 1, 63, 138, 167, 114, 41, 6, 1, 71, 159, 192, 128, 44, 6, 1, 79

Offset: 1

Gus Wiseman, Jan 08 2019

			Triangle begins:
   1
   1   1
   1   3   1
   1   5   2
   1   9   7   2
   1  11   8   2
   1  17  19  10   2
   1  21  25  14   3
   1  27  37  24   6
   1  31  42  26   6
   1  41  73  68  32   6
   1  45  79  72  33   6
   1  57 124 151 105  39   6
   1  63 138 167 114  41   6
   1  71 159 192 128  44   6
   1  79 183 228 157  56   8

Except for the k = 1 column, same as A186974.
Row sums are A320426.
Second column is A015614.
Cf. A051424, A084422, A085945, A187106, A276187, A320423, A320430, A320435.

Table[Length[Select[Subsets[Range[n],{k}],CoprimeQ@@#&]],{n,16},{k,PrimePi[n]+1}]

A214803 Frobenius numbers of numerators and denominators of rational numbers in order of their canonical enumeration.

Original entry on oeis.org

-1, -1, 1, -1, 5, -1, 3, 7, 11, -1, 19, -1, 5, 11, 17, 23, 29, -1, 13, 27, 41, -1, 7, 23, 31, 47, 55, -1, 17, 53, 71, -1, 9, 19, 29, 39, 49, 59, 69, 79, 89, -1, 43, 65, 109, -1, 11, 23, 35, 47, 59, 71, 83, 95, 107, 119, 131, -1, 25, 51, 103, 129, 155, -1, 13

Offset: 1

Reinhard Zumkeller, Jul 29 2012

sign

a(n) = A020652(n) * A038567(n) - A020652(n) - A038567(n);
for n > 1: a(A015614(n)) = A165900(n-1);
a(A002088(n)) = -1.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Frobenius Number.
Wikipedia, Coin problem

a214803 n = a214803_list !! (n-1)
a214803_list = [x * y - x - y | y <- [1..], x <- [1..y-1], gcd x y == 1]

A092824 Farey-factorial numerators.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 16, 18, 24, 30, 40, 48, 60, 72, 80, 90, 96, 120, 144, 180, 240, 288, 360, 432, 480, 540, 576, 600, 720, 840, 1008, 1260, 1440, 1680, 2016, 2160, 2520, 2880, 3024, 3360, 3600, 3780, 4032, 4200, 4320, 5040, 5760, 6720, 8064, 10080

Offset: 1

Clark Kimberling, Mar 06 2004

nonn

The last number in the n-th segment is n!. Let f(n) be the first number in segment n; except for initial terms, f is A001048 and A059171. Let g(n) be the second number in segment n; except for initial terms, g is A052747. Except for the initial terms, the number of numbers in segment n is given by A015614.

			The sequence begins with these segments:
  1
  2
  3 4 6
  8 12 16 18 24
For the next segment, start with these Farey fractions of order 5:
  1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/5.
Multiply these by 5! to get
  30 40 48 60 72 80 90 96 120.

Cf. A000142, A001048, A015614, A059171, A052747.

f[n_] := n! * Table[a/b, {b, 1, n}, {a, 1, b}] // Flatten // Union // Rest; Flatten[Table[f[n], {n, 1, 8}] /. {} -> {1}][[1 ;; 51]] (* Jean-François Alcover, May 18 2011 *)

Let S(n) be the set of integers an!/b, where a/b ranges through the positive Farey fractions of order n. A092824 is the increasing sequence of integers in the union of the sets S(n), for n>=1.

A078334 Primes in A005728, which counts the terms in the Farey sequence of order n.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 19, 23, 29, 43, 47, 59, 73, 97, 103, 151, 173, 181, 271, 397, 433, 491, 883, 941, 1087, 1103, 1163, 1193, 1229, 1427, 1471, 1697, 2143, 2273, 2657, 2903, 3533, 3677, 4073, 4129, 4201, 4259, 4637, 5023, 5107, 5953, 6163, 6599, 7177, 7237

Offset: 1

Cino Hilliard, Nov 21 2002

Guy, in his Example 8, citing Leo Moser as his source, noted that the first 9 values of A005728(n) = 1 + Sum_{i=1..n} phi(i) = 1 + Sum_{i=1..n} A000010(i) are all primes, but that the pattern breaks down at A005728(10) = 33 = 3*11. As Guy warns, in several paraphrases of the same law, "Capricious coincidences cause careless conjectures." That is, for 1 <= n <= 9 we have A005728(n) = A078334(n), but for n > 9 we sometimes (n = {11, 12, 13, 15, 17, 18, 22, ...}) have A005728(n) prime, but other times (n = {10, 14, 16, 19, 20, 21, ...}) have A005728(n) composite. [Jonathan Vos Post, Sep 06 2010]

			The Farey sequence of order 6 is {0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1}, which has 13 terms, so 13 is in the sequence.

H. Rademacher, Lectures on Elementary Number Theory, 1964. pp. 5-11.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Richard K. Guy, The Strong Law of Small Numbers, Amer. Math. Monthly 95 (1988), no. 8, 697-712.
Eric Weisstein's World of Mathematics, Farey Sequence.

Cf. A000010, A015614, A067282, A078334. [Jonathan Vos Post, Sep 06 2010]

fc[n_] := 1+Sum[EulerPhi[k], {k, 1, n}]; Select[fc/@Range[200], PrimeQ]

Offset corrected by Amiram Eldar, Mar 01 2020

A117992 Number of distinct rational numbers less than 1 that can be written as fractions of the first n composite numbers.

Original entry on oeis.org

0, 1, 3, 5, 9, 11, 17, 20, 26, 29, 33, 38, 50, 54, 65, 80, 89, 98, 102, 113, 123, 144, 158, 166, 190, 203, 215, 222, 236, 247, 277, 287, 314, 328, 346, 364, 375, 400, 417, 438, 478, 487, 529, 548, 573, 604, 617, 641, 667, 683, 698, 749, 769, 796, 836, 851, 873

Offset: 1

Reinhard Zumkeller, Apr 08 2006

nonn

a(n) = (A117991(n) - 1)/2.

			n=4, the first 4 composite numbers are 4,6, 8 and 9:
a(3)=#{4/6,4/8,4/9,6/8,6/9,8/9}=#{4/9,1/2,2/3,3/4,8/9}=5.

Robert Israel, Table of n, a(n) for n = 1..6000

Cf. A015614, A117991.

N:= 1000: # to use composites up to N
comps:= remove(isprime, [$4..100]):
nc:= nops(comps):
S:= {}: A[1]:= 0:
for n from 2 to nc do
S:= S union {seq(comps[j]/comps[n],j=1..n-1)};
  A[n]:= nops(S);
od:
seq(A[i],i=1..nc); # Robert Israel, Jan 30 2018

M = 100; (* to use composites up to M *)
comps = Select[Range[4, M], CompositeQ];
nc = Length[comps]; S = {}; A[1] = 0;
For[n = 2, n <= nc, n++, S = S ~Union~ Table[comps[[j]]/comps[[n]], {j, 1, n - 1}]; A[n] = Length[S]];
Array[A, nc] (* Jean-François Alcover, Mar 10 2019, after Robert Israel *)

A320435 Regular triangle read by rows where T(n,k) is the number of relatively prime k-subsets of {1,...,n}, 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 4, 1, 1, 9, 10, 5, 1, 1, 11, 19, 15, 6, 1, 1, 17, 34, 35, 21, 7, 1, 1, 21, 52, 69, 56, 28, 8, 1, 1, 27, 79, 125, 126, 84, 36, 9, 1, 1, 31, 109, 205, 251, 210, 120, 45, 10, 1, 1, 41, 154, 325, 461, 462, 330, 165, 55, 11, 1, 1, 45, 196

Offset: 1

Gus Wiseman, Jan 08 2019

Two or more numbers are relatively prime if they have no common divisor > 1. A single number is not considered to be relatively prime unless it is equal to 1.

			Triangle begins:
    1
    1    1
    1    3    1
    1    5    4    1
    1    9   10    5    1
    1   11   19   15    6    1
    1   17   34   35   21    7    1
    1   21   52   69   56   28    8    1
    1   27   79  125  126   84   36    9    1
    1   31  109  205  251  210  120   45   10    1
    1   41  154  325  461  462  330  165   55   11    1
    1   45  196  479  786  923  792  495  220   66   12    1
    1   57  262  699 1281 1715 1716 1287  715  286   78   13    1
The T(6,2) = 11 sets are: {1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,3}, {2,5}, {3,4}, {3,5}, {4,5}, {5,6}. Missing from this list are: {2,4}, {2,6}, {3,6}, {4,6}.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Row sums are A085945.
Second column is A015614.
Cf. A000837, A186974, A187106, A289508,  A289509, A300486, A303139, A320424, A320436.

Table[Length[Select[Subsets[Range[n],{k}],GCD@@#==1&]],{n,10},{k,n}]

T(n,k) = sum(d=1, n\k, moebius(d)*binomial(n\d, k)) \\ Andrew Howroyd, Jan 19 2023

T(n,k) = Sum_{d=1..floor(n/k)} mu(d)*binomial(floor(n/d), k). - Andrew Howroyd, Jan 19 2023

A339026 Number of pairs (x,y): 1 <= x < y <= nn, such that xy is a square.

Original entry on oeis.org

0, 1, 4, 8, 16, 27, 40, 58, 80, 105, 128, 158, 198, 237, 278, 336, 382, 435, 502, 574, 632, 699, 798, 868, 968, 1063, 1176, 1262, 1362, 1505, 1590, 1732, 1880, 2007, 2150, 2272, 2434, 2567, 2746, 2930, 3062, 3265, 3444, 3654, 3832, 4035, 4284, 4454, 4668, 4875, 5142, 5364, 5590, 5889, 6078, 6336, 6614, 6881, 7166

Offset: 1

Edward Krogius, Nov 19 2020

nonn

			For n = 3, we have the following solutions: (1,4), (1,9), (2,8), (4,9), therefore a(3) = 4.
For n = 4, we have the following solutions: (1,4), (1,9), (1,16), (2,8), (3,12), (4,9), (4,16), (9,16), therefore a(4) = 8.

Edward Krogius, Table of n, a(n) for n = 1..1000
Edward Krogius, Illustration of 105 solutions in 100x100 grid

Cf. A000010, A015614, A018805, A132188, A132189, A132345, A338894.

Array[Sum[EulerPhi[j] Floor[(#^2)/(j^2)], {j, 2, #}] &, 59] (* Michael De Vlieger, Dec 11 2020 *)

A339026(n) = sum(i=2,n,floor(n^2/i^2)*eulerphi(i)); \\ Antti Karttunen, Nov 23 2020

a(n) = Sum_{j=2..n} phi(j) * floor(n^2/j^2).
a(n) = (A338894(n) - n^2)/2.
a(n) = A132189(n^2)/2. - Antti Karttunen, Nov 23 2020

A278049 a(n) = 3*(Sum_{k=1..n} phi(k)) - 1, where phi = A000010.

Original entry on oeis.org

2, 5, 11, 17, 29, 35, 53, 65, 83, 95, 125, 137, 173, 191, 215, 239, 287, 305, 359, 383, 419, 449, 515, 539, 599, 635, 689, 725, 809, 833, 923, 971, 1031, 1079, 1151, 1187, 1295, 1349, 1421, 1469, 1589, 1625, 1751, 1811, 1883, 1949, 2087, 2135, 2261, 2321, 2417, 2489, 2645, 2699, 2819, 2891, 2999

Offset: 1

N. J. A. Sloane, Nov 22 2016

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..10000
J. Lehner and M. Newman, Sums involving Farey fractions, Acta Arithmetica 15.2 (1969): 181-187. See Eq. (19).

Cf. A000010, A002088.

Cf. m*(Sum_{k=1..n} phi(k)) - 1: A015614 (m=1), A018805 (m=2), this sequence (m=3).

with(numtheory);
f:=n->3*add(phi(r),r=1..n)-1;
[seq(f(r),r=1..50)];

Table[3 Sum[EulerPhi@ k, {k, n}] - 1, {n, 57}] (* Michael De Vlieger, Dec 16 2016 *)

from functools import lru_cache
@lru_cache(maxsize=None)
def A278049(n): # based on second formula in A018805
    if n == 0:
        return -1
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A278049(k1)-1)//3
        j, k1 = j2, n//j2
    return 3*(n*(n-1)-c+j)//2 - 1 # Chai Wah Wu, Mar 25 2021

G.f.: (1/(1 - x)) * (-x + 3 * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^2). - Ilya Gutkovskiy, Feb 14 2020

A278148 Triangle T(n, m) giving in row n the numerators of the fractions for the Farey dissection of order n.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 3, 1, 2, 2, 3, 5, 4, 1, 2, 2, 3, 3, 4, 5, 5, 7, 5, 1, 2, 2, 2, 3, 3, 4, 5, 5, 7, 9, 6, 1, 2, 2, 2, 3, 3, 3, 5, 4, 5, 7, 5, 7, 8, 7, 9, 11, 7, 1, 2, 2, 2, 2, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 7, 8, 7, 9, 11, 13, 8, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 7, 5, 6, 9, 7, 8, 7, 7, 8, 10, 11, 9, 11, 13, 15, 9

Offset: 1

Wolfdieter Lang, Nov 22 2016

For the denominators see A278149.
The length of row n is A002088(n) = A005728(n) - 1.
In the Hardy reference one finds from the Farey fractions of order n >= 2 (see A006842/A006843) a dissection of the interval [1/(n+1), n/(n+1)] into A015614(n) = A005728(n) - 2  intervals J(n,j) = [l(n,j), r(n,j)], j = 1..A015614(n). They are obtained from three consecutive Farey fractions of order n: p(n,j-1)/q(n,j-1), p(n,j)/q(n,j), p(n,j+1)/q(n,j+1) by l(n,j) = p(n,j)/q(n,j) - 1/(q(n,j)*(q(n,j) + q(n,j-1))) = (p(n,j) + p(n,j-1))/(q(n,j) + q(n,j-1)) and r(n,j) = p(n,j)/q(n,j) + 1/(q(n,j)*(q(n,j) + q(n,j+1))) = (p(n,j) + p(n,j+1))/(q(n,j) + q(n,j+1)). (Hardy uses N for n, p/q - Chi_{p,q}'' for l (left) and p/q + Chi_{p,q}' for r (right)). For the second equations in l(n,j) and r(n,j) see the identities in Hardy-Wright, p. 23, Theorem 28.
Due to r(n,j) = l(n,j+1), for n >= 2 and j=1..A015614(n), it is sufficient to give for this Farey dissection of order n >= 2 only the two endpoints of the interval [1/(n+1), n/(n+1)] and the A015614(n) - 1 = A002088 - 2 = A005728(n) - 3 inner boundary points. The present table gives the numerators of these fractions. See the example section. For n = 1 we add the row 1/2 in accordance with A002088(1) = 1.

			The triangle T(n, m) begins:
n\m 1 2 3 4 5 6 7 8 9 10 11 12 ...
1:  1
2:  1 2
3:  1 2 3 3
4:  1 2 2 3 5 4
5:  1 2 2 3 3 4 5 5 7  5
6:  1 2 2 2 3 3 4 5 5  7  9  6
...
n = 7:  1 2 2 2 3 3 3 5 4 5 7 5 7 8 7 9 11 7,
n = 8:  1 2 2 2 2 3 3 4 5 5 4 5 7 8 7 7 8 7 9 11 13 8,
n = 9:  1 2 2 2 2 3 3 3 3 4 5 5 7 5 6 9 7 8 7 7 8 10 11 9 11 13 15 9,
n = 10: 1 2 2 2 2 2 3 3 3 5 4 4 5 5 7 5 6 9 7 8 7 9 12 8 10 11 9 11 13 15 17 10.
.............................................
The fractions T(n,m)/A278149(n, m) begin:
n\m 1    2   3   4   5   6   7   8   9  10
1: 1/2
2: 1/3  2/3
3: 1/4  2/5 3/5 3/4
4: 1/5  2/7 2/5 3/5 5/7 4/5
5: 1/6  2/9 2/7 3/8 3/7 4/7 5/8 5/7 7/9 5/6
...
n = 6: 1/7 2/11 2/9 2/7 3/8 3/7 4/7 5/8 5/7 7/9 9/11 6/7,
n = 7: 1/8 2/13 2/11 2/9 3/11 3/10 3/8 5/12 4/9 5/9 7/12 5/8 7/10 8/11 7/9 9/11 11/13 7/8,
n = 8: 1/9 2/15 2/13 2/11 2/9 3/11 3/10 4/11 5/13 5/12 4/9 5/9 7/12 8/13 7/11 7/10 8/11 7/9 9/11 11/13 13/15 8/9,
n = 9: 1/10 2/17 2/15 2/13 2/11 3/14 3/13 3/11 3/10 4/11 5/13 5/12 7/16 5/11 6/11 9/16 7/12 8/13 7/11 7/10 8/11 10/13 11/14 9/11 11/13 13/15 15/17 9/10,
n = 10: 1/11 2/19 2/17 2/15 2/13 2/11 3/14 3/13 3/11 5/17 4/13 4/11 5/13 5/12 7/16 5/11 6/11 9/16 7/12 8/13 7/11 9/13 12/17 8/11 10/13 11/14 9/11 11/13 13/15 15/17 17/19 10/11.
.............................................
For n = 5 the actual intervals J(5,j), j= 1..9 are then:
[1/6, 2/9], [2/9, 2/7], [2/7, 3/8], [3/8, 3/7], [3/7, 4/7], [4/7, 5/8], [5/8, 5/7], [5/7, 7/9], [7/9, 5/6].

G. H. Hardy, Ramanujan, AMS Chelsea Publ., Providence, RI, 2002, p. 121.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 5th ed., Clarendon Press, Oxford, 2003, pp. 23, 29 - 31.

Cf. A002088, A005728, A006842/A006843, A015614, A278149.

T(1, 1) = 1 and for n>= 2: T(n, 1) = 1, T(n, A002088(n)) = n and for m = 2..(A002088(n) - 1): T(n, m) = numerator(l(n,m)) = numerator( p(n,m)/q(n,m) - 1/(q(n,m)*(q(n,m) + q(n,m-1)))).

cp's OEIS Frontend

A343659 Number of maximal pairwise coprime subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A320436 Irregular triangle read by rows where T(n,k) is the number of pairwise coprime k-subsets of {1,...,n}, 1 <= k <= A036234(n), where a single number is not considered to be pairwise coprime unless it is equal to 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A214803 Frobenius numbers of numerators and denominators of rational numbers in order of their canonical enumeration.

Views

Author

Keywords

Comments

Links

Programs

Haskell

A092824 Farey-factorial numerators.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A078334 Primes in A005728, which counts the terms in the Farey sequence of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A117992 Number of distinct rational numbers less than 1 that can be written as fractions of the first n composite numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A320435 Regular triangle read by rows where T(n,k) is the number of relatively prime k-subsets of {1,...,n}, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A339026 Number of pairs (x,y): 1 <= x < y <= n*n, such that x*y is a square.

Views

Author

Keywords

Examples

Links

Crossrefs

A339026 Number of pairs (x,y): 1 <= x < y <= nn, such that xy is a square.