Automatic Sets, was: Re: Question on Sequence A046907 from Sloane's Database

[Antti Karttunen]

> Antti Karttunen wrote:
> > 
> > David W. Wilson wrote:
> > >
> > > "James A. Sellers" wrote:...
> > > > I have a question on sequence A046907, which gives the values of n for which binomial(2n-1, n) is squarefree.   The
> > sequence is 1,2,3,4,6,9,10,12,36.  I have
> > > >
> > > > James A. Sellers
> > > > Associate Professor, Mathematics
> > > > Cedarville College
> > > >
> > > > sellersj at cedarville.edu
> > > > http://www.cedarville.edu/dept/sm/jas_www.htm
> > >
> > > This is one a broad set of problems which devolve to a unsolved general
> > > problem.  The general problem is:
> > >
> > > Is the intersection of a given a-automatic and b-automatic set finite?
> > >
> > > A k-automatic set is a set of integers whose base-k representations form
> > > a regular language, that is, a language accepted by a finite automaton
> > > or state machine.
> > >
> > > If bases a and b are incompatible (do not have a common power), and if
> > > an a-automatic set Sa and b-automatic set Sb are both of density 0
> > > over the integers, it is believed that Sa intersect Sb is finite
> > > (or something along this line).
> > >
> > > The current problem is whether f(n) = (2n-1 choose n) is squarefree for
> > > a finite number of n.  It turns out that f(n) is divisible by 4 unless
> > > n belongs to a 2-automatic set S2 (which happens to be the set of
> > > numbers
> > > whose binary representations contain at most two 1's).  Similarly, f(n)
> > > is divisibly by 9 unless n belongs to a 3-automatic set S3 (much harder
> > > to describe).
> > I submitted the former set/sequence into Encyclopedia in
> > July: A048645 1,2,3,4,5,6,8,9,10,12,16,17,18,20,24
> > for which a reasonably nice formula exists:
> > a(n) = 2^A003056[n]+2^A002262[n-1] (after n=1).
> 
> 
> Though this particular 2-automatic set has a simple arithmetic
> expression, this is not the case for general k-automatic sets. 
> 
> > So how much harder is this latter, 3-automatic set to
> > describe? Has it its own sequence in the Encyclopedia yet?
> 
> If the representation of 2n in base 3 consists entirely of
> 0's and 2's, except possibly for a pair of adjacent 1's,
> then n is in S3, and (2n-1 choose n) is not divisible by 9.

> The initial elements of S3 are:
> 
> 1 2 3 4 6 7 9 10 11 12 13 18 19 21 22 27 28 29 30 31 33 34 36 37 38 39
> 40 54 55 57 58 63 64 66 67 81 82 83 84 85 87 88 90 91 92 93 94 99 100
> 102 103 108 109 110 111 112 114 115 117 118 119 120 121 162 163 165 166

"I am sorry, but the terms 1 2 3 4 6 7 9 10 11 12 13 18 19 21 22 
do not match anything in the table."
Neil, would you like add this one too?
(The authority here is Dave, not me.)

%N Axxxxxx Base-3 expansion of 2n matches ((0|2)11)*(0|2)*)*
%Y Axxxxxx C.f. A046097
%e Axxxxxx The base 3-representations of 2n are
           2 11 20 22 110 112 200 202 211 220 222 1100 1102 1120
           1122 2000 2002 2011 2020 2022 2110 2112 2200, etc.

%Y A046097 Intersection of A048645 and Axxxxxx (and what else?)

> You might add the following comment:
> %C A048645 4 does not divide (2n-1 choose n).

Hmm, this might be better:
%C A048645 4 does not divide C(2a(n)-1,a(n)) = A001700[a(n)]
(where a(n) means nth term of A048645 and C(r,n) means binomial
coefficient, i.e. TeX's "choose").
%Y A048645 C.f. A046097
%Y A001700 C.f. A046097

And now I show how I ended to the same result that 
"f(n) = (2n-1 choose n) is divisible by 4 unless n belongs
to the set of numbers whose binary representations contain
at most two 1's." (In case anybody wants to find more related
truths.)

By using the well-known formula
  Sum [n/p^i], i=1..infinity or [logp(n)] (depending whether
you prefer elegance or sensible running time) we get the highest
power of p dividing n! Here [x] means floor(x).
With p=2 we get
  Sum [n/2^i], i=1..inf for above, and
  Sum [n/2^i], i=0..inf for the highest power of 2 dividing (2n)!

Now the highest power of 2 dividing C(2n,n) is
  (Sum [n/2^i], i=0..) - 2(Sum [n/2^i], i=1..)
= n - Sum [n/2^i], i=1..

As C(2n-1,n) = C(2n,n)/2
we see that we still have to subtract 1.
Thus the highest power of 2 dividing C(2n-1,n) is
 n - 1 - Sum [n/2^i], i=1.. 
And thus, that the sum of n's repeated shiftings to the right
where at least (n-2), its binary expansion can contain at
most two 1's.
 
Now, for the highest power of 3 dividing C(2n-1,n)
I guess we start with the same formula, but offhand at 23:50 pm
I don't immediately see how you ended with that pattern
for base-3 representation...

Yours,

Antti Karttunen
E-mail: Antti.Karttunen at iki.fi -> karttu at megabaud.fi

> 
> > BTW. What is the exact definition of "density 0 over the
> > integers" ?
> > lim count_of_terms_of_set_below(n)/n -> 0 as n -> infinity?
> 
> Yes.
>  
> > >  If f(n) is squarefree, therefore, n must belong to
> > > S = S2 intersect S3.  It is very probable that S is finite, but no
> > > proof is known.
> > Is this just a necessary condition, or alone sufficient?
> > (I.e. I guess that infinitely many other k^2 could divide
> > f(n) than just 2^2=4, 3^2=9, ((2*3)^2)=36 and so on?)
> 
> Obviously, larger squares can divide f(n).  But by eliminating
> 4 and 9 alone, the only valid n <= 2^64 = 18446744073709551616
> are the following:
> 
> 1 2 3 4 6 9 10 12 18 33 34 36 40 64 66 192 256 264 272 513 514 516 576
> 768 1026 1056 2304 16392 65664 81920 532480 545259520
> 
> One might easily conjecture that the complete set is finite, or
> even that the above set is complete.  However, there is little
> hope of a proof.
> 
> At any rate, it certainly cuts down on the work necessary to
> compute A046097 (not A046907) up to 2^64.
> 
> > Is there any reference to the topic, on the Net or in the
> > journals?
> 
> Can't tell you.  You might want to consult Jeff Shallit.
> 
> > Yours,
> > 
> > Antti Karttunen
>