|
>...S(n) is the set of rationals a/b, with 1 <= a,b <= n, and a and b
>relatively prime, ...
The ordered series of elements of S(n) for which a<b is called the Farey
series F(n). S(n) as defined also contains the reciprocals of the terms of
the Farey series. Thus the number of terms in S(n) is 1 (for 1/1) plus
twice as many terms as there are in F(n). The number of terms in F(n) is
sum(k=2,n) [phi(k)]
where phi(k) is the number of integers less than k and relatively prime to
k; this sum increases fairly rapidly with n, but not as rapidly as n**2.
Example: the number of terms in S(7) is
1 + 2*terms(F(7)) = phi(2)+...+phi(7) = 1+2*(1+2+2+4+2+6=17)
= 35
The actual terms are:
1/7,1/6,1/5,1/4,2/7,1/3,2/5,3/7,1/2,4/7,3/5,2/3,5/7,3/4,4/5,5/6,6/7,
1,
and the reciprocals of the first line.
Now it is clear that 1/1...1/n are useful members of the set of n+1 numbers
for T. The problem is in finding an n+1st member for the set... clearly we
want to avoid terms which might produce either a numerator or denominator
of the form p*q>n. But if we add ONE fraction with numerator =q then we must
delete ALL those with denominators > n/q. So it can't be done.
|
| >It seems clear to me that 1/1...1/n are *not* useful as members of the set,
>since if they are all in the set, then the n+1st member of the set will
>violate the rule that x/y is a member of S(n).
My point is that NO choice of n+1 elements will work, and that choosing
1/1..1/n as a basis for an n+1-set shows the impossibility most clearly.
The point is that you don't want T's whose numerators and denominators
multiply to > n, so I chose numerators = 1 to eliminate that. (I could
equally have chosen 1/1..n/1).
Suppose, for example, n = 7 and 2/3 is in T. That eliminates all other
elements with numerator > 7/3 = 2 and denominator > 7/2=3, which leaves
only 1/1,1/2,1/3,2/1 as candidates.
|
| It's simple to find n element solutions, including some that are non-trivial.
For example, n=7 has the 7 element set:
1/3, 2/3, 1/1, 4/3, 5/3, 2/1, 7/3
However, I didn't find any n+1 element sets, for n <= 10.
My computer program is embarrassingly slow (because I expected to find some
solutions). A faster program would result by pre-computing the boolean
matrix x[i,j], which is true iff s[i]/s[j] is in S(n), where s[k] is
the kth element of S(n).
|
| I found no solutions through n=19. There should be some simple pigeon-hole
principle that applies to prevent an n+1 element solution, because there are
so many n element solutions.
The Bliss program, for what it's worth, follows below.
I noticed a curious thing about |S(n)|, the number of elements in S(n).
For n=1,2,3,6,7,or 8, |S(n)| is one less than a power of two. This is
more than I would expect by chance. Could someone explain it?
module sr (main=main, addressing_mode(external=general)) =
begin
library 'sys$library:starlet';
literal
false = 0,
true = 1;
external routine
util$output; ! An interface to SYS$FAO and LIB$PUT_OUTPUT.
own scnt,
sptr;
routine gcd (a,b) = if .a eql 0 then .b else gcd (.b mod .a, .a);
macro
fract_(a,b) = ((a)^16+(b)) %,
num_(f) = .(f)<16,16,0> %,
den_(f) = .(f)< 0,16,0> %;
literal
max_set = 256;
routine dump (t: ref bitvector) : novalue =
begin
local
s: ref vector[max_set];
util$output (%ascid'-/-');
s = .sptr;
decr i from .scnt-1 to 0 do
begin
if .t[.i] then util$output (%ascid'!UL/!UL', num_(s[.i]), den_(s[.i]));
end;
end;
routine choose (z, pool, t: ref bitvector, c: ref vector) : novalue =
begin
local
u: bitvector[max_set];
ch$move (%allocation(u), t[0], u[0]);
if .z eql 0 then (dump (t[0]); return);
decr i from .pool-1 to 0 do
begin
if .u[.i] then
begin
local
d: ref bitvector;
d = c[.i*(max_set/%bpval)];
decr i from max_set/%bpval-1 to 0 do
begin
map
d: ref vector,
u: vector;
u[.i] = .u[.i] and not .d[.i];
end;
choose (.z-1, .i, u[0], c[0]);
ch$move (%allocation(u), t[0], u[0]);
end;
end;
end;
routine main =
begin
incr n from 2 to 100 do
begin
local
s: vector[max_set],
c: vector[max_set*(max_set/%bpval)],
t: bitvector[max_set];
scnt = 0;
incr i from 1 to .n do
incr j from 1 to .n do
begin
local k,f;
k = gcd(.i,.j);
f = fract_( .i/.k, .j/.k );
if (decr k from .scnt-1 to 0 do
if .f eql .s[.k] then exitloop false)
then
begin
s[.scnt] = .f;
scnt = .scnt + 1;
end;
end;
! Now determine which combinations are compatible.
!
ch$fill (not 0, %allocation(c), c[0]);
decr i from .scnt-1 to 0 do
begin
local
d: ref bitvector;
d = c[.i*(max_set/%bpval)];
decr j from .scnt-1 to 0 do
begin
local num, den, k;
num = num_(s[.i]) * den_(s[.j]);
den = den_(s[.i]) * num_(s[.j]);
k = gcd(.num,.den);
num = .num/.k;
den = .den/.k;
if .num leq .n and .den leq .n then d[.j] = false;
end;
end;
! Now choose.
!
ch$fill (0, %allocation(t), t[0]);
decr i from .scnt-1 to 0 do t[.i] = true;
sptr = s[0];
util$output (%ascid'N = !UL, S(n) contains !UL elements', .n, .scnt);
!!! dump (t[0]);
choose (.n+1, .scnt, t[0], c[0]);
! choose (.n , .scnt, t[0], c[0]); ! To look for n-element sets
end;
return ss$_normal;
end;
end
eludom
|
| >I noticed a curious thing about |S(n)|, the number of elements in S(n).
>For n=1,2,3,6,7,or 8, |S(n)| is one less than a power of two. This is
>more than I would expect by chance. Could someone explain it?
I don't think you are counting them correctly. |S(7)| = 35 (Cf note .1);
perhaps you are counting 2/2, 6/3, and other reducible fractions?
|