Re^2: 2 or 3 possibly new sequences from 1998

[Richard Mathar]

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



Neil wrote:

> Consider A001043:
> %I A001043 M3780 N0968
> %S A001043  
> 5,8,12,18,24,30,36,42,52,60,68,78,84,90,100,112,120,128,138,144,152,
> %T A001043  
> 162,172,186,198,204,210,216,222,240,258,268,276,288,300,308,320,330,
> %U A001043  
> 340,352,360,372,384,390,396,410,434,450,456,462,472,480,492,508,520
> %N A001043 Numbers that are the sum of 2 successive primes.
>
> The new sequence would be:
> Let m = A001043(n). Then a(n) = number of ways of writing
> m = A001043(i) + A001043(j) with i <= j < n.

Assuming I did this correctly, the number of ways is:

{0, 0, 0, 0, 1, 1, 2, 2, 0, 4, 1, 2, 2, 2, 0, 2, 6, 2, 2, 2, 4, 4, 2,  
2, 4, 5, 3, 4, 7, 9, 5, 1, 7, 6, 9, 2, 2, 5, 2, 4, 9, 6, 6, 5, 8, 2,  
1, 6, 4, 8, 6, 12, 10, 4, 1, 5, 9, 5, 6, 4, 12, 15, 9, 7, 7, 13, 5,  
10, 8, 11, 6, 8, 2, 6, 13, 4, 12, 6, 8, 11, 21, 15, 14, 8, 10, 8, 14,  
12, 17, 13, 0, 9, 7, 12, 16, 7, 9, 13, 6, 3, ...}

Richard Mathar:

> Next term in A134650, after 946, is larger than 20100000 if existent.

Another way to look at this is to graph the above number of ways:

http://chesswanks.com/num/double.jpg

To expect another solution (after 946) is to have some point drop to  
zero as the graph continues to the right.

I'm curious to find out why this graph develops as two distinct  
populations. If anyone would like to work on this, my x-axis values  
for the 204 points (from 9501 to 10000) that are less than 500 (from  
305 to 469) are:

{9502, 9503, 9504, 9507, 9508, 9509, 9512, 9514, 9516, 9521, 9528,  
9530, 9531, 9533, 9535, 9537, 9539, 9544, 9545, 9554, 9558, 9560,  
9561, 9562, 9564, 9567, 9569, 9571, 9573, 9576, 9577, 9579, 9581,  
9582, 9585, 9587, 9590, 9592, 9594, 9595, 9597, 9599, 9605, 9608,  
9609, 9610, 9613, 9614, 9622, 9626, 9627, 9628, 9634, 9642, 9649,  
9651, 9653, 9655, 9656, 9659, 9660, 9661, 9662, 9663, 9664, 9667,  
9668, 9670, 9671, 9672, 9674, 9675, 9676, 9677, 9678, 9680, 9689,  
9692, 9695, 9697, 9698, 9700, 9701, 9702, 9705, 9706, 9709, 9711,  
9715, 9717, 9718, 9719, 9726, 9727, 9729, 9734, 9736, 9737, 9739,  
9743, 9746, 9752, 9753, 9755, 9756, 9761, 9762, 9765, 9767, 9768,  
9771, 9775, 9781, 9783, 9786, 9790, 9795, 9797, 9800, 9804, 9807,  
9817, 9822, 9823, 9828, 9830, 9834, 9836, 9837, 9840, 9841, 9842,  
9843, 9844, 9846, 9853, 9854, 9855, 9856, 9857, 9863, 9864, 9865,  
9866, 9867, 9868, 9871, 9875, 9879, 9882, 9884, 9887, 9889, 9891,  
9895, 9896, 9898, 9901, 9902, 9904, 9905, 9906, 9907, 9908, 9912,  
9916, 9919, 9923, 9925, 9933, 9934, 9935, 9936, 9938, 9939, 9942,  
9943, 9944, 9946, 9948, 9949, 9950, 9952, 9953, 9955, 9958, 9960,  
9962, 9966, 9969, 9970, 9971, 9972, 9974, 9975, 9979, 9980, 9983,  
9988, 9990, 9995, 9997, 9998, 9999}

The other 296 points are greater than 500 (from 531 to 794).