A002088,A015614,A018805 errata

Mon Jun 14 02:05:19 CEST 1999

                                                                13 Jun 1999
This is errata about sequences A002088,A015614,A018805. The entries:

%C A002088 Ordered pairs of integers from [1,n] with no common factors 
%N A015614 Pairs of integers from [1,n] with no common factors:

are ambiguous. If we compare it to the sequence A018805 description:

%N A018805 Number of relatively prime pairs (x, y) with 1 <= x, y <= n.

we see they all seem to be describing the same sets. What is the meaning
of the terms "pair" and "ordered pair"? Here is what Eric Weisstein writes:

---------------------------------------------------------------------------
Ordered Pair

   A Pair of quantities (a, b) where ordering is significant, so (a, b)
   is considered distinct from (b, a) for $a\not=b$ .
---------------------------------------------------------------------------
Pair

   A Set of two numbers or objects linked in some way is said to be a
   pair. The pair a and b is usually denoted (a, b), and is generally
   considered to be ordered.
---------------------------------------------------------------------------

I distinguish Sets, Multisets, and Lists. For a set, neither order nor
multiplicity matter. For a multiset, multiplicity matters, order doesn't.
For a list, both order and multiplicity matter. There is no commonly used
term for a collection in which order matters, but multiplicity doesn't.
Another term for List is Vector. Terminology can be confusing at times.

So, Olivier in A015614 considered "pair" to mean "a set with 2 members".
Also, in A002088 he considered "ordered pair" to mean "a multiset of size 2".
However, these are not the common meanings. It would be very good to have
a uniform set of terminology to use for sequence entries.

In the meantime, I suggest the following consistent corrected entries:

---------------------------------------------------------------------------
%C A002088 Cardinality of {(x,y): 1<=x<=y<=n , 1=gcd(x,y)}.
%N A015614 Cardinality of {(x,y): 1<=x<y<=n , 1=gcd(x,y)}.
%N A018805 Cardinality of {(x,y): 1<=x,y<=n , 1=gcd(x,y)}.
---------------------------------------------------------------------------

The numerical work is as follows:

---------------------------------------------------------------------------
gp> for(n=1,21,print1(sum(y=1,n,sum(x=1,n,1==gcd(x,y)))","))
1,3,7,11,19,23,35,43,55,63,83,91,115,127,143,159,191,203,239,255,279,
gp> for(n=1,22,print1(sum(y=1,n,sum(x=1,y,1==gcd(x,y)))","))
1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,102,120,128,140,150,
gp> for(n=1,22,print1(sum(y=1,n,sum(x=1,y-1,1==gcd(x,y)))","))
0,1,3,5,9,11,17,21,27,31,41,45,57,63,71,79,95,101,119,127,139,149,
----------------------------------------------------------------------------

By the way, notice another inconsistency. The origin for A002088 is 0, but for
the other sequences it is 1. I don't know any reason for the difference.

Shalom, Michael
-- 
Michael Somos <somos at grail.cba.csuohio.edu>     Cleveland State University
http://grail.cba.csuohio.edu/~somos/            Cleveland, Ohio, USA 44115

==============================================================================
%I A002088 M1008 N0376
%S A002088 0,1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,102,120,128,140,150,
%T A002088 172,180,200,212,230,242,270,278,308,324,344,360,384,396,432,450,474,
%U A002088 490,530,542,584,604,628,650,696,712,754,774,806,830,882,900,940,964
%N A002088 Sum of totient function.
%C A002088 Ordered pairs of integers from [1,n] with no common factors - Olivier
           Gerard (ogerard at ext.jussieu.fr)
%D A002088 Sylvester, J. J., On the number of fractions contained in any Farey
           Series of which the Limiting Number is given", London, Edinburgh, and
           Dublin Philosophical Magazine (Fifth Series), vol. 15 (1883), p. 251
           = Collected Mathematical Papers, Vols. 1-4, Cambridge Univ. Press,
           1904-1912, Vol. 4, p. 103.
%D A002088 D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No.
           105, National Research Council, Washington, DC, 1941, pp. 7-10.
%D A002088 Beiler, A., Recreations in the Theory of Numbers, Dover, 1966, Chap.
           XVI.
%D A002088 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics.
           Addison-Wesley, Reading, MA, 1990, p. 138.
%D A002088 Handbook of Number Theory, D. S. Mitrinovic et al., Kluwer, Section
           I.21.
%H A002088 More information
%Y A002088 Cf. A000010, A015614.
%O A002088 0,3
%A A002088 njas
%K A002088 nonn,easy,nice
%F A002088 Sum phi(k), k=1..n.
%F A002088 a(n) approximates (3n^2)/(pi^2) - Len Smiley (smiley at saturn.math.uaa
           .alaska.edu).
%E A002088 Additional comments from Leonard Smiley (smiley at math.uaa.alaska.edu).
==============================================================================

==============================================================================
%I A018805
%S A018805 1,3,7,11,19,23,35,43,55,63,83,91,115,127,143,159,191,203,239,255,279,
%T A018805 299,343,359,399,423,459,483,539,555,615,647,687,719,767,791,863,899,
           947,
%U A018805 979,1059,1083,1167,1207,1255,1299,1391,1423,1507,1547,1611,1659,1763
%N A018805 Number of relatively prime pairs (x, y) with 1 <= x, y <= n.
%O A018805 1,2
%K A018805 nonn
%F A018805 a(n) = 2 ( Sum phi(j), j=1..n ) - 1; a(n) = n^2 - Sum a([n/j]),
           j=2..n.
%A A018805 David W. Wilson (wilson at ctron.com)
%E A018805 Mma Program 08/97 (oprg).
%t A018805 FoldList[Plus, 1,2 Array[EulerPhi,60,2]]
==============================================================================

==============================================================================
%I A015614
%S A015614 0,1,3,5,9,11,17,21,27,31,41,45,57,63,71,79,95,101,119,127,139,149,
%T A015614 171,179,199,211,229,241,269,277,307,323,343,359,383,395,431,449,473,
%U A015614 489,529,541,583,603,627,649,695,711,753,773,805,829,881,899,939,963
%N A015614 Pairs of integers from [1,n] with no common factors: number of
           fractions in (Haros)-Farey series of order n.
%Y A015614 = A002088[n] - 1.
%O A015614 1,3
%K A015614 nonn,dupe
%A A015614 Olivier Gerard (ogerard at ext.jussieu.fr)
==============================================================================