Closures and Complements

[Franklin T. Adams-Watters]

Don Reble <djr at nk.ca> wrote:

>> The next sequence that caught my attention is the closure of {2} under
>> ab and ab+1. This produces a sequence whose complement is finite. The
>> complete complement is below:
>> 
>> 1 3 6 7 8...
>> This was calculated by hand, so it may contain errors.
>
>Indeed, "8" is in the closure. I get
>
>1 3 6 7 12 13 14 15 24 27 28 29 30 31 48 49 54 57 58 59 60 61 62 63 97
>98 108 109 114 117 118 119 120 123 124 127 194 197 217 218 219 228 229
>237 238 239 240 241 246 247 248 249 389 394 434 439 457 458 479 482 492
>493 497 498 499 788 789 878 879 917 959 984 985 986 994 997 998 1579
>1757 1758 1759 1968 1971 1988 1994 1997 3514 3517 3518 3989 7028 7034
>7037 7978 14074 28148
>
>And this time, finiteness is proven easily.

Oops.  The extra 8 was just a transcription error; it's in the closure on my piece of paper.  On the other hand, I'm missing 23, which is a very early and embarassing mistake.  (And, of course, it leads to other errors later on.)

The thing that impresses me with this is how large a value we get with such a simple rule.

Finiteness for a fixed n (for the problem with {n} as the starting value, closed under ab+k, for 0<=k<n) is going to be just a matter of computation: once you get all values between some value m and n*m, you're done.  Proving it in general is going to take some insights into factorization that I, at least, don't have.  My guess is that it is a hard problem.
-- 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645


__________________________________________________________________
Introducing the New Netscape Internet Service. 
Only $9.95 a month -- Sign up today at http://isp.netscape.com/register

Netscape. Just the Net You Need. 

New! Netscape Toolbar for Internet Explorer
Search from anywhere on the Web and block those annoying pop-ups.
Download now at http://channels.netscape.com/ns/search/install.jsp