[math-fun] New proof of Euclid's Theorem

[Don Reble]

Mathfunners, Seqfans:

> ... Let f(x) = x^2 + x, let g[0] be a positive integer,
> and for n = 1, 2, 3, ..., let g[n] = f(g[n-1]). ...
>
> The case of g[0] = 1 ...
> which primes appear as factors in the sequence of g[n] ...
> 2, 3, 7, 13, 43, 73, 139, 181, 547, 607, 1033, 1171, ...

    It is, of course, Sloane's A007996... I mean A096263...
    Augggh! yet another duplicate.

    It's an easy exercise to prove those sequences are identical.
    Good luck, reader.

-- 
Don Reble  djr at nk.ca


-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.





The fact that every natural number can be written as a partition 
into distinct parts containing only Catalan numbers and powers
of 3 is intuitively not surprising.

Indeed, this amounts to the fact that the formal power-series
(1+x) (1+x^2) (1+x^5) (1+x^14) .... (1+x^3) (1+x^9) (1+x^27) ...
has all coefficients >0.

Since Catalan numbers grow roughly like powers of 4,
the sum of coefficients when considering only 
factors of degree <N is roughly e^(log(N)*(1/log(4)+1/log(3)))
and the result should intuitively follow from the fact that
(1/log(4)+1/log(3))~1/63 is larger that 1/log(2)~1.44.

Here is however a sketch for a rigorous proof (which can be made
effective be someone not as lazy as me):

Consider the set D of all points (x,y) with  $1/3<=x<=1, 1/4<y<=1$.
check that there exists natural numbers $A,B$ such that 
for every element S of D one can find a polynomial P_S of degree <=A
with coefficients in  {0,1} and a polynomial Q_S of degree <=B
with coefficients in  {0,1}

This implies then the result, up to a finite verification
N=x C_s=y 3^t, with $(x,y)$ in D, C_s then s-th Catalan number
and 3^t a power of 3. The above polynomial corresponding to 
(x,y) yields then a recipy for a smaller counterexample,
provided N is huge enough.

(All this can be made rigorous, after introduction of some small epsilon
which can be computed when analysing the map D->(P,Q). Stirlings
formula, together with epsilon, can then be used to compute
the minimal value of N for which the proof starts working.
Checking up to this minimal value ends the proof.)

This method of proof can of course be applied to similar cases.

By the way, perhaps more interesting are
partitions of integers with distinct parts 
in two sets among {Catalans}, {central binomial coeffs}, 
{powers of 4}.


In these cases there could perhaps exist an infinite set
of integers with no such partition. (The intuitive argument using logs
above yields then equality and fails). An anwser to one of 
the three associated problems would then probably be 
non-trivial (the idea of proof sketched above is no longer applicable).

Best whishes,   Roland Bacher 





On Sat, Jan 27, 2007 at 06:27:32PM +0100, wouter meeussen wrote:
> Any number can be so partitioned in at least one way. (true?)
> the following numbers can be so partitioned in one way only:
> 1,2,4,7,13,21,40,63,121,195,364,624,1093,1353,1794,2054,3280,3540,3981,4241,
> 4710,5486,5955,6215
> 
> 1
> 2
> 1+3
> 2+5
> 1+3+9
> 2+5+14
> 1+3+9+27
> 2+5+14+42
> 1+3+9+27+81
> ...
> but watch out for the strong law of small numbers: it doesn't continue like
> that; after a while, the cat's and powers of 3 mix:
> r[1],
> q[2],
> r[1] r[3],
> q[2] q[5],
> r[1] r[3] r[9],
> q[2] q[5] q[14],
> r[1] r[3] r[9] r[27],
> q[2] q[5] q[14] q[42],
> r[1] r[3] r[9] r[27] r[81],
> q[2] q[5] q[14] q[42] q[132],
> r[1] r[3] r[9] r[27] r[81] r[243],
> q[2] q[5] q[14] q[42] q[132] q[429],
> r[1] r[3] r[9] r[27] r[81] r[243] r[729],
> q[2] q[5] q[14] q[42] q[132] q[429] r[729],
> r[1] q[1430] r[3] r[9] r[27] r[81] r[243],
> q[2] q[5] q[14] q[42] q[132] q[429] q[1430],
> r[1] r[3] r[9] r[27] r[81] r[243] r[729] r[2187],
> q[2] q[5] q[14] q[42] q[132] q[429] r[729] r[2187],
> r[1] q[1430] r[3] r[9] r[27] r[81] r[243] r[2187],
> q[2] q[5] q[14] q[42] q[132] q[429] q[1430] r[2187],
> r[1] q[1430] r[3] r[9] r[27] r[81] r[243] r[729] r[2187],
> q[2] q[5] q[14] q[42] q[132] q[429] q[4862],
> r[1] q[4862] r[3] r[9] r[27] r[81] r[243] r[729],
> q[2] q[5] q[14] q[42] q[132] q[429] q[4862] r[729]
> 
> Not yet OEIS-ready, and not so evident, I think.
> Maybe more in the leage of Christian Bower or Vladeta Jovovic ?
> 
> Wouter.
>