[seqfan] Re: An arithmetic conjecture
Martin Fuller
martin_n_fuller at btinternet.com
Thu Mar 19 20:08:01 CET 2009
> From: David Wilson <dwilson at gambitcomm.com>
> Subject: [seqfan] Re: An arithmetic conjecture
> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> Date: Tuesday, 17 March, 2009, 2:46 PM
[cut]
> I have a conjecture along these lines:
>
> If two bases a >= 2 and b >= 2 and two sets of
> integers A and B where
>
> a and b are not powers of the same integer (e.g, a = 4,
> b = 8 is
> unacceptable)
> A and B are infinite,
> A and B have limit density 0 over the integers,
> A is a-automatic (the base-a representations of the
> elements of A
> form a regular language) and B is b-automatic.
>
> Then A and B have finite intersection.
>
> Example:
>
> Let a = 2, b = 10, A = powers of 2, B = numbers with no 0
> in their
> base-10 numerals.
>
> This example easily conforms to the first three conditions.
> A is 2-automatic, with its base-2 numerals forming the
> regular language 10*.
> B is 10-automatic, with is base-10 numerals forming the
> regular language
> [123456789]+
>
> My conjecture implies that A and B have finite
> intersection, that is,
> there are a finite number of powers of 2 without zeroes in
> their base-10
> representations.
>
> My conjecture also implies your conjecture.
>
[cut]
Some counter-conjectures (using your reasoning from 7 March 2009):
A,B = numbers without a zero in base a,b
I conjecture that the intersection is infinite for any pair a,b >= 3
Example: a=3, b=4
The sequence starts 1, 2, 5, 7, 13, 14, 22, 23, 25, 26, 41, 43, 53, 121, 122, 125, 149, 151, 157, 158, 214, 215, 229, 230, 233, 238, 239, 365, 367, 373, 374, 377, 445, 446, 473, 475, 485, 607, 617, 619, 634, 635, 637, 638, 697, 698, 701, 725, 727 (not in OEIS)
The number of elements up to n should be O(n^k) with k = log(2)/log(3) + log(3)/log(4) - 1, approximately k = 0.42. Up to 10^13 the constant is around 3.
[
Further conjectures:
Numbers without a zero in all bases 3..10: infinite
Numbers without a zero in all bases 3..15: largest=17392214961514563152363
Numbers without a zero in all prime bases 3<=p<=10^10: infinite
Numbers without a zero in all prime bases 3<=p<=10^100: finite
The behaviour is controlled by the sign of:
k = 1-sum{bases b}(1-log(b-1)/log(b))
Any help estimating this function for odd primes?
]
A,B = palindromes in base a,b
Are palindromes k-automatic?
I conjecture that any pair of bases that are not powers of the same integer give rise to an infinite sequence. The distribution is O(log(n)) in each case.
Examples in OEIS: bases 2&10 A007632 (& see links), bases 2&3 A060792, bases 3&4 to 6&7 A097928 to A097931, bases 7&8 A099145, bases 8&9 A099146.
Have I missed something?
Martin Fuller
More information about the SeqFan
mailing list