Conference rusure::math

Seems fairly straightforward, although I have glossed over some simple 
assumptions.

To show that any composite number N is in either of your 2 sets:

If N = 2^e0 then it is obviously in set 1

If not, then assume its decomposition is

	N = 2^e0 * p1^e1 * p2^e2... (p1 < p2 ...)

To show that it is in set 2 then we just have to be able to solve

	N = uv - u(u-1)/2 with u <= v

	[ v = N/u + (u-1)/2 ]

which we can do by treating the various cases as follows:

If		then choose	which is good, since

e0 even		u = p1		N >= p1^2 (don't forget it's composite),
				so v >= p1+(p1-1)/2 > u
e0 = 1,N = 6	u = 3		v=3, so v=u
e0 = 1,N > 6	u = 4		N >= 10, so v >= 4

Duplicates in set 2 doesn't seem to be at issue, for example:

N = 60 = 3*21 - c(3,2) = 5*14 - c(5,2)

Dick

Not quite complete. I showed that sets 1 and 2 include all the composites. I 
should also show that they don't include any primes.

2^n is never prime (accepting the problem's implicit definition of prime)

If u = 2k   then uv-u(u-1)/2 = 2kv-k(2k-1)     which is divisible by k
If u = 2k+1 then uv-u(u-1)/2 = (2k+1)v-(2k+1)k which is divisible by 2k+1

Dick, I haven't understood all of .1:

> If		then choose	which is good, since
>
> e0 even	u = p1		N >= p1^2 (don't forget it's composite),
>				so v >= p1+(p1-1)/2 > u
> e0 = 1,N = 6	u = 3		v=3, so v=u
> e0 = 1,N > 6	u = 4		N >= 10, so v >= 4

Q1. (e0 even) N is composite, but it might not have other divisor than 2
and p1, so how do you deduce that N >= p1^2 ?

Q2. What about the case  e0 odd, e0 > 1 ?

Mihai.

Yes, that was a bit hasty, wasn't it. Here's a better (and simpler) version:

To show that any composite number N is in either of your 2 sets:

If N = 2^e0 then it is obviously in set 1

If not, then assume its decomposition is

        N = 2^e0 * p1^e1 * p2^e2... (p1 < p2 ...)    (I)
                                    (e1 > 0)

To show that it is in set 2 then we just have to be able to solve

        N = uv - u(u-1)/2 with u <= v

        ie find integral v = N/u + (u-1)/2 with v >=u (II)

which we can do by choosing u = min(p1,2^(e0+1))

This works since we have N >= 2^e0 * p1 (from I) and

  if p1 < 2^(e0+1) (ie we choose u = p1)
  then N > p1^2/2 = u^2/2
  and v = integer + even/2 so is integral

  if p1 > 2^(eo+1) (ie we choose u = 2^(eo+1))
  then N > 2^(2*e0+1) = u^2/2
  and v = odd/2 + odd/2 so is integral 
 
  and, either way, v is integral and > u/2 + (u-1)/2 (using II)
                                     >= u

Finally, set 1 obviously generates composites only
and set 2 generates composites only since:

If u = 2k (k >= 2)   then uv-u(u-1)/2 = 2kv-k(k-1)      so k    is a factor
If u = 2k+1 (k >= 1) then uv-u(u-1)/2 = (2k+1)v-(2k+1)k so 2k+1 is a factor

So sets 1/2 generate all the composites and only composites.

Duplicates in set 2 seem to be allowed, for example:

N = 60 = 3*21 - c(3,2) = 5*14 - c(5,2)

Out of interest, does this constitute an "inferior" definition of a set?

Dick

And your solution is pretty short, also!

What do you mean by <"inferior" definition of a set> ?
(interesting question).

Mihai.

An inferior definition of a set? Obviously, an inductive
definition, which works towards it from underneath.

Hank

No, I wasn't even being witty, just philosophical and not being au fait with 
the fundamentals of set theory. I was just bothered by the fact that the set 
definition predicate "generated duplicates". I suppose I should have been 
thinking round the other way, not in terms of generators but that an object 
is in a set if it satisfies the predicate. This makes duplication a non-issue 
since we don't care if it satisfies the predicate in more than one way. I 
think this has already been addressed somewhere in this notesfile.

Isn't this why the Relational Database theorists had to use "Bags" rather 
than Sets, for example to count the identical looking records got by carrying 
out, for example, a projection?