[seqfan] Re: An arithmetic conjecture

[Robert Gerbicz]

2009/3/19 Martin Fuller <martin_n_fuller at btinternet.com>

>
> > 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/
>

Shaper conjectures: numbers without a zero in base 3..11 is infinite, while
numbers without a zero in base 3..12 is finite, the largest is:
n=427922513144616928563377118135455168876424464499338572676793288647\
285774997681548911927198976183171758716653258459859842567522215343
There is no larger example up to 10^1000.

Up to n there should be about n^0.01828582017280296455473737868
numbers without a zero in all bases 3..11

To compute this I used the bases 3,5,6,7,10,11 and the above formula ( if in
base 3 there is no zero, then in base 9 there is also no zero).
To compute the probability for base=4,8 is somewhat harder: if we know n in
base 64 then we can easily write the base 4 and 8 represantation, because
4^3=8^2=64, and there are 27 numbers in [0..63] that has no zero in base 4
and 8. This means that we have to add log(27/64)/log(64) to the previous
sum. In PARI-Gp for "independent bases" (no pair of them is the power of the
same number):
find(x)=L=length(x);return(sum(i=1,L,log(1-1/x[i])/log(x[i])))+1 gives the
exponent. So
find([3,5,6,7,10,11])+log(27/64)/log(64)=0.01828582017280296455473737868
find([3,5,6,7,10,11,12])+log(27/64)/log(64)=-0.01673013384585328458714961507