# [seqfan] Re: Comment on A151750 [erratum]

David Wilson davidwwilson at comcast.net
Sun Aug 2 20:03:19 CEST 2009

```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 + *, 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/

```