[seqfan] Re: Comment on A151750 [erratum]

[David Wilson]

As Max astutely noted, Lucas's Theorem provides a key link between the prime 
factorizations of binomial expressions and base representations.

(Aside: I have fun with digital problems, but I generally regard them 
generally as fluff. Lucas's theorem shows, however, that the digits of a 
number can have number theoretical significance).

Specifically, Lucas gives us

    p does not divide choose(2n, n)   <=>   n has all base-p digits < p/2.

So letting

    S(p) = {n : base p digits of n all <= p/2 }

we can recast Graham's prize conjectures as

    A0309797 is infinite  <=>  S(3) intersect S(5) intersect S(7) is 
infinite

and

    A151750 is finite  <=>  S(3) intersect S(5) intersect S(7) intersect 
S(11) is finite.

The base-representation characterization of S(p) allows us to conclude that 
there are ceil(p/2)^k elements of S(p) that are < p^k. This, in turn, allows 
us to formulate an estimate of the density of elements of S(p) around 
integer n. We can then use the product formula to estimate densities of the 
intersections of various S(p) (specfically, the intersections that define 
A030979 and A151750). If we integrate the resulting density estimates over N 
and obtain a finite (infinite) value, we can conjecture that the 
intersection is finite (infinite). I suspect such a density analysis will 
confirm Graham's conjectures.

A b-automatic set is a set of nonnegative integers whose base-b 
representations form a regular language (accepted by a finite automaton or 
represented by regular expression). There are many conjectures that can be 
formulated in terms of the finity of an intersection of b-automatic sets.

For example, a prize was once offered for a proof that every sufficiently 
large power of 2 includes the digit 7. This devolves to showing that the 
power of 2 (binary 10*, a 2-automatic set) and base-10 sevenless numbers 
(decimal 0 + [12345689][012345689]*, a 10-automatic set) have finite 
intersection.

In some cases b-automatic sets may possess fortuitous mathematical 
properties (for example, the powers of 2 (binary 10*, 2-automatic) and the 
powers of 3 (ternary 10*, 3-automatic) can be shown to have finite 
intersection based on parity considerations. At other times, the sets may be 
dense enough that they must have infinite intersection. However, in most 
instances, one or more of the sets in question lacks these properties. For 
example, the base-10 sevenless numbers have no known mathematical or density 
properties that we can leverage to show that the sevenless powers of 2 are 
finite in number. Not surprising, the problem is still open.

Graham's problems are yet another example of the same phenomenon. The S(p) 
are p-automatic sets that have no exploitable mathematical properties to 
help us establish the finity of their intersections. I proffer, then, that 
it is a waste of time to work on the problem, unless you are brilliant and 
wish to immerse yourself in the subject, in which case it is only almost 
certainly a huge waste of time. I judge these problems equivalent to Collatz 
conjecture in difficulty: mathematics is not ready for them.

----- Original Message ----- 
From: "Max Alekseyev" <maxale at gmail.com>
To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
Sent: Sunday, August 02, 2009 10:37 AM
Subject: [seqfan] Re: Comment on A151750 [erratum]


> On Sun, Aug 2, 2009 at 6:14 AM,
> peter.luschny<peter.luschny at googlemail.com> wrote:
>
>> The problems in my original posting are somewhat harder.
>> Ron Graham for example offers 1000$ for one of them.
>
> As far as I know, Ron offered $1000 for each of the following proofs:
> 1) infiniteness of A030979
> 2) finiteness of A151750
>
> btw, does anybody know how the bound 10^10000 was obtained in A151750 ?
>
> This bound is also mentioned in the reference:
> Mauldin, R. Daniel; Ulam, S. M.; Mathematical problems and games. Adv.
> in Appl. Math. 8 (1987), 281-344.
> http://www.math.unt.edu/~mauldin/papers/no62.pdf
> but there is no indication of who and how derived it.
>
> Regards,
> Max
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/