Re: How to count rational numbers

In article <1194078222.715308.99940@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
kunzmilan <kunzmilan@xxxxxxxx> wrote:

On 1 Lis, 00:30, Gerry Myerson <ge...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
In article <1193837271.152718.276...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,



kunzmilan <kunzmi...@xxxxxxxx> wrote:
I already discredited myself by my miscarried attempt to count sums of
prime numbers. Nevertheless, I try it again.
In the rational matrix R, r(i,j) = j/i
1) n(n - 1)/2 elements are lesser than 1 in the matrix T,
2) n elements are equal to 1, and
3) n(n - 1)/2 elements are greater than 1.
The value 1/2 repeats in every even row, thus this fraction repeats n/
2 times, supposing that n is even. We must subtract [(n/2) - 1] from
the value of T to eliminated these repeated values 1/2. We will call
these orrective elements as c(i).
The values 1/3 and 2/3 repeat in every third row, thus these 2
rational numbers repeat 2n/3 times in the matrix T. We must subtract
[(2n/3) - 2] from the value of T to eliminated repeated values 1/3 and
2/3, again supposing that n is divisible by 3.
1/4, 2/4, 3/4 repeat in every 4. row, but 2/4 was already counted as
1/2. This leaves 2 uncounted elements in every 4. row. We must
subtract [(n/2) - 2] from the value of T to eliminated repeated values
1/4 and 3/4.
The prime 5 gives repeatings as 4n/5, and the term [(4n/5) - 4],
generally [({p - 1}n/p) - p + 1].
From j/6, 3/6 corresponds to 1/3, and 2/6 and 4/6 to 1/3 and 2/3,
respectively. This leaves fractions 1/6 and 5/6 to be counted.
Carefully continuing, and finding ways to eliminate possible rounding
errors, it were possible to find the counting function for any n.
It can be conjectured, that for none n
T - \sum c(i) is not equal to n.
kunzmilan

I think you're trying to count the number of fractions a / b
with 0 < a < n + 1, 0 < b < n + 1, and gcd(a, b) = 1.
This is twice the sum of phi(m), m from 1 to n,
where phi(m) is the number of positive integers relatively
prime to m and not exceeding m.
It is well-known that the sum is asymptotic to
(3 / pi^2) n^2.

--
Gerry Myerson (ge...@xxxxxxxxxxxxxxx) (i -> u for email)

Thanks for your answer.
I wanted to accept it but I have some doubts.
(3 / pi^2) n^2 approximately n^2/3 compared with (n^2 -n)/2 seems to
be too low estimation of repeated entries.

What do you mean, "seems to be too low"?
Have you tried counting for, say, n = 1000?

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: How to count rational numbers
    ... kunzmilan wrote: ... In the rational matrix R, r= j/i ... The value 1/2 repeats in every even row, ... Gerry Myerson ...
    (sci.math)
  • Re: How to count rational numbers
    ... kunzmilan wrote: ... In the rational matrix R, r= j/i ... The value 1/2 repeats in every even row, ... Gerry Myerson ...
    (sci.math)
  • Re: How to count rational numbers
    ... kunzmilan wrote: ... In the rational matrix R, r= j/i ... The value 1/2 repeats in every even row, ... its decadic logarithm shows that it were necessary to have ...
    (sci.math)
  • Re: How to count rational numbers
    ... kunzmilan wrote: ... In the rational matrix R, r= j/i ... The value 1/2 repeats in every even row, ... be too low estimation of repeated entries. ...
    (sci.math)
  • Re: How to count rational numbers
    ... kunzmilan wrote: ... In the rational matrix R, r= j/i ... The value 1/2 repeats in every even row, ... This is twice the sum of phi, m from 1 to n, ...
    (sci.math)