Re Value a(6) in doubt for A101877

[N. J. A. Sloane]

sequence that are spread out over several emails.
sentence saying that entry A****** needs the following correction.
 Best regards
 			 Neil
Return-Path: <hv at zen.crypt.org>
X-Ids: 166
Message-Id: <200801311050.m0VAoLhB029411 at zen.crypt.org>
To: "N. J. A. Sloane" <njas at research.att.com>
cc: seqfan at ext.jussieu.fr
Subject: Re: Re Value a(6) in doubt for A101877 
From: hv at crypt.org
In-Reply-To: <200801310546.m0V5k5Bq008605 at prim.research.att.com> 
Date: Thu, 31 Jan 2008 10:50:21 +0000
Sender: hv at zen.crypt.org
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.166]); Thu, 31 Jan 2008 11:53:39 +0100 (CET)
X-Virus-Scanned: ClamAV 0.92/5618/Wed Jan 30 22:52:31 2008 on shiva.jussieu.fr
X-Virus-Status: Clean
X-Miltered: at shiva.jussieu.fr with ID 47A1A8B3.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
Return-Path: <davidwwilson at comcast.net>
X-Ids: 164
X-Authority-Analysis: v=1.0 c=1 a=atZbUPtmawSEotQ7fuYA:9
 a=KimJskGsoVFPPCQl8oEA:7 a=-MdYssCF4IXGoK5ACLb_ulLaR2oA:4 a=si9q_4b84H0A:10
 a=4E1p6MsWW-gA:10
Message-ID: <00d401c86400$8298f8e0$6401a8c0 at yourxhtr8hvc4p>
From: "David Wilson" <davidwwilson at comcast.net>
To: "David Wilson" <davidwwilson at comcast.net>,
   "Sequence Fans" <seqfan at ext.jussieu.fr>
References: <002f01c85fb5$4d798cf0$6401a8c0 at yourxhtr8hvc4p>
Subject: Re: A005245 conjecture
Date: Thu, 31 Jan 2008 06:57:52 -0500
MIME-Version: 1.0
Content-Type: text/plain;
	format=flowed;
	charset="iso-8859-1";
	reply-type=response
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 6.00.2900.3138
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3198
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.164]); Thu, 31 Jan 2008 12:56:12 +0100 (CET)
X-Virus-Scanned: ClamAV 0.92/5621/Thu Jan 31 10:56:07 2008 on shiva.jussieu.fr
X-Virus-Status: Clean
X-Miltered: at shiva.jussieu.fr with ID 47A1B75B.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!

Again, for a = A005245, let

    pmin(n) = MIN({a(x)a(y): xy = n, > x <= y < n})
    smin(n) = MIN({a(x)+a(y): xy = n, > x <= y < n})

pmin(n) is defined only for composite n, smin(n) for n >= 2.

A recursive definition of a is then

    a(n) = {
        1; n = 1
        smin(n); n prime
        min(smin(n), pmin(n)); n composite
    }

Even though general smin(n) = 1+a(n-1) has failed us, one could still hope 
for [3] below, that is,

    a(n) = {
        1; n = 1
        1+a(n-1); n prime
        pmin(n); n composite
    }

This is true if

    smin(n) = 1+a(n-1); n prime (the UPINT conjecture)
    pmin(n) <= smin(n); n composite

So clearly UPINT was ahead of me on this subject. Maybe they already knew 
about n = 21080618.

----- Original Message ----- 
From: "David Wilson" <davidwwilson at comcast.net>
To: "Sequence Fans" <seqfan at ext.jussieu.fr>
Sent: Friday, January 25, 2008 7:49 PM
Subject: A005245 conjecture


> 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.