A005245 conjecture

[Martin Fuller]

David's conjecture [3] and the UPINT conjecture are not true either. 
The smallest counterexamples to [3] are n = 353942783 and n =
516743639.  The first of these is a prime, so it is a counterexample to
the UPINT conjecture.

Program attached to calculate A005245 and check all these conjectures. 
I have run it up to 8*10^8 before running out of memory.  It also
identifies n=21080618 as the first counterexample to conjecture [2].

I'm planning to submit extensions to A005520 and A005421 next week when
I have extended the program to 10^10 or more.

Martin Fuller

--- Max Alekseyev <maxale at gmail.com> wrote:

> Well, it turns out that David's conjecture [2] is NOT true.
> 
> Namely, if we assume that [2] is true and will use formula [3] to
> compute terms of A005245 then we will come to a contradiction with
> [2]
> for n = 21080618:
> a(6) = 5
> a(n-6) = 49
> a(n-1) = 54
> and
> a(6) + a(n-6) = 54 < 55 = a(n-1) + 1.
> 
> The obtained contradiction disproves the conjecture [2].
> This counterexample was suggested by CD_Eater at Russian forum
> lib.mexmat.ru and verified by me.
> 
...
> On Jan 26, 2008 1:05 PM, Max Alekseyev <maxale at gmail.com> wrote:
> > Dear David,
> >
> > Richard Guy mentions this sequence in his UPINT book (section F26),
> in
> > particular, asking whether a(p) = a(p-1) + 1 for prime p.
> > Please note that this question will be immediately answered
> > affirmatively as soon as your conjecture is proved.
> > Therefore, your conjecture may be very hard to prove since
> Richard's
> > question remains open for a decade already (at least from the year
> > 1994 second edition to the year 2004 third edition of his book).
> >
> > Regards,
> > Max
> >
> >
> > On Jan 25, 2008 4:49 PM, David Wilson <davidwwilson at comcast.net>
> wrote:
> > > Let a(n) = A005245(n) = complexity of n = smallest number of 1's
> needed to
> > > produce n using operators + and *.
> > >
...
> > > [2]  MIN({a(x)+a(y): x + y = n, x <= y < n}) = 1+a(n-1)
> > >
> > > that is, the minimum is always attained when x = 1 and y = n-1. 
> If this is
> > > true, then the definition can be rewritten
> > >
> > > [3] a(n) =
> > >         1, if n = 1
> > >         min(1+a(n-1), MIN({a(x)+a(y): xy = n, x <= y < n})),
> otherwise.
...
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: A005245.c
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20080201/71166623/attachment-0001.c>