Since the discussion has again rolled around to the perennial chestnut of whether there are a finite number of zeroless powers of 2, I thought I would again state my perennial umbrella conjecture. To start, if we are given two arbitrary integer sequences each exhibiting exponential growth, a probabilistic argument says that we should expect the sequences to share only a finite number of elements. There are cases where we can prove the number of shared elements is finite (e.g, {2^n} and {3^n}) and others where we know the number of shared elements is infinite (e.g, {Fib(n)} and {Fib(2n)}), but in the absence of evidence either way, the safer assumption is a finite intersection. A b-automatic (b >= 2) set is a set of nonnegative integers whose base-b representations form a regular language, that is, are accepted by a finite automaton and representable by a regular expression. For example, the powers of 2 form a 2-automatic set with the regular expression 10*. Similarly, the zeroless numbers form a 10-automatic set with regular expression (1+2+3+4+5+6+7+8+9)(1+2+3+4+5+6+7+8+9)*. Call two bases b and c compatible if b and c share a common power > 1. Thus binary, octal and hexadecimal are compatible bases because 2, 8 and 16 have the common power 4096. If b and c are compatible, then the b-automatic and c-automatic sets coincide. If b and c are incompatible, the sets that are both b-automatic and c-automatic sets include precisely the finite sets and sets whose first differences are eventually periodic (Cobham 1964). ---------------------------------------------------------- Let B be a b-automatic set with density 0 over the integers. It can be proved that B is either finite or exhibits exponential growth (as a sorted sequence). Let B be a zero-density b-automatic set and C a zero-density c-automatic set. If b and c are compatible, it is easy enough to find B and C having either finite or infinite intersection. For finite intersection, let B = C = S = {1,2,3} (or any other finite set). By virtue of its finiteness, B = C = S is both b-automatic and c-automatic, as well as zero-density, and the intersection of B and C is S, which is finite. For infinite intersection, let B = C = S = {b^n}. B = C = S is zero-density over the positive integers. B is b-automatic, having base-b regular expression 10*. Because c is compatible with b, C = B is also c-automatic. The intersection of B and C is S, which is infinite. If b and c are incompatible, it is easy enough to find B and C with finite intersection. For example, b = 2 and c = 3 are incompatible. Let B = {2^n} and C = {3^n}. B and C are 2-automatic and 3-automatic respectively, having regular expression 10* in their respective bases, and their intersection is {1}, which is finite. On the other hand, I have not been able to find such a B and C with infinite intersection, which leads to the conjecture: Wilson's Conjecture: If b and c are incompatible bases, then zero-density b-automatic set B and zero-density c-automatic set C have finite intersection. (I adopt this conjecture because I have not seen it elsewhere). Since B and C are zero-density automatic sets, they are either finite or exhibit exponential growth. If either is finite, their intersection is cleary so. If both have exponential growth, applying our statistical argument above, we would expect them to have finite intersection. So what Wilson's conjecture really says is that the incompatibility of bases b and c can be taken as evidence that B and C are "relatively random" enough to obey the probabilistic argument that indicate finite intersection. ---------------------------------------------------------- Admittedly, Wilson's conjecture is a yet another generalization of certain problems that are themselves notoriously difficult to prove. However, I think that it is a useful generalization in that (1) it tells us what to expect in a large number of similar problems, and (2) it has number theoretical implications beyond mere digit twiddling. The finity of the zeroless powers of 2 is a straightforward consequence of Wilson's conjecture. The generalization is easy enough to show: Let b and c be incompatible bases, and let d be a base-c digit (0 <= d < c). The powers of b form a zero-density b-automatic set B, while the base-c numbers without digit d form a zero-density c-automatic set C. Wilson's conjecture then implies the intersection of B and C is finite, that is, there are finitely many base-c powers of b witout digit d. Letting b = 2 and c = 10 are incompatible, and we get a finite number of zeroless base-10 powers of 2. If instead of powers of 2, we had chosen a sequence S to be a random sequence of base-10 numbers such that S(n) has the same number of digits as 2^n, S would have had a finite number of zeroless elements with probability 1. So in this case, Wilson's conjecture tells us that in one respect the powers of 2 act like similarly sized random numbers with respect to base 10. More generally, Wilson's theorem says something about the "relative randomness" of incompatible bases in certain contexts. Anyone who has programmed arbitrary precision arithmetic knows that converting between compatible bases is computationally easy while converting between incompatible bases is difficult. To convert between compatible octal and hexadecimal bases, one can simply start at the right, converting each block of 4 octal digits to an equivalent block of 3 hexadecimal digits, and O(n) process. Converting between incompatible binary and decimal is much harder. Changing a single base-2 digit potentially affects arbitrarily many base-10 digits. I'm not even sure that a sub-O(n^2) algorithm exists for binary-to-decimal conversion. This is one aspect of the "relative randomness" of incompatible bases. I am taxed to remember the details of a certain prize problem concerning the divisibility of choice numbers by 4 and 9 (any help finding this problem would be appreciated). The problem asked whether there were a finite number of choice numbers with a certain property, and the conjectured solution was implied by Wilson's theorem. So here was an instance of an independent number theoretical (as opposed to digit twiddling) problem where Wilson's theorem gave the expected result. Another purely number theoretical implication of Wilson's theorem is that for incompatible b and c, |b^x - c^y| <= d has a finite number of solutions. This result, whether true or false, probably has a goodly amount of number theoretical background, which might be reversed engineered to shed light on Wilson's theorem. -- No virus found in this outgoing message. Checked by AVG Anti-Virus. Version: 7.0.300 / Virus Database: 266.4.0 - Release Date: 2/22/2005