Re Value a(6) in doubt for A101877
N. J. A. Sloane
njas at research.att.com
Thu Jan 31 06:46:05 CET 2008
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.
More information about the SeqFan
mailing list