A005245 conjecture

[Max Alekseyev]

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.

Some comments:

1) While the conjecture [2] is disproved, the conjecture [3] may still
hold. The counterexample above does not disprove [3] since the value
of a(n) as computed by formula [3] is smaller than a(6) + a(n-6).

2) The true values of A005245(n-1) and A005245(n-6) may be different
from the listed above since the latter were computed using unproved
and possibly incorrect formula [3].

3) I've verified that [2] (and [3]) holds for n<=800000. The minimum
counterexample to [2] is still unknown. But it is not greater than
21080618.

Regards,
Max

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 *.
> >
> > We can work out
> >
> > [1] a(n) =
> >         1, if n = 1
> >         min(MIN({a(x)+a(y): x + y = n, x <= y < n}), MIN({a(x)+a(y): xy = n,
> > x <= y < n})), otherwise.
> >
> > Well, I did some experimenting, and it looks like
> >
> > [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.
> >
> > You gotta admit this is much easier to compute than the [1].
> >
> > I did a stupid implementation of [3] that ran surprisingly quickly.
> >
> > Conjecture [2] would be nice to prove, but I've had no luck.
> >
> >
>