[seqfan] Re: An arithmetic conjecture

[David Wilson]

No, I think you're right.

I was mistaken that the number of nth base-b zeroless number was 
approximately exponential in n (c^n), when it is actually polynomial in 
n (n^c). That makes all the difference.

I redid the math, and your k value dropped out of it.

So I rescind my conjecture about k-automatic sequences in deferences to 
your work. You really should publish.

I'll take a look at palindromes when I can.

Martin Fuller wrote:
>> 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
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
>