### Random Post

### Recent Posts

### Recent Comments

Jim Randell on Puzzle #52: Bus change | |

Jim Randell on Enigma 967: Prime cubes | |

GeoffR on Enigma 1707: Making progr… | |

Jim Randell on Enigma 1707: Making progr… | |

Jim Randell on Tantalizer 409: Fe, Fi, Fo,… |

### Archives

### Categories

- article (11)
- enigma (1,364)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (47)
- site news (58)
- tantalizer (92)
- teaser (7)

### Site Stats

- 231,899 hits

I didn’t solve this one purely programatically, as the problem space initially seems too large to explore in a reasonable amount of time. A bit of analysis shows what the “best” solution might be, this can then be attacked manually to yield the solution, or using the SymPy symbolic maths package. This Python program uses SymPy and runs in 394ms.

Solution:The best sequence is: –7, 12, –7, –7, 12, –7, –7, 12, –7, 12, –7, –7, 12, –7, –7, 12, –7.Nicely done, Jim — it looks daunting at first. Your rectangular grid was an inspiration!

Yes. I was quite pleased with that solution (although it’s not really a programmatic one), before I hit on the grid idea I wasn’t really getting anywhere.

Although when you see the solution it looks like you should be able to extend it further (unless you look really closely), but the next term would need to be ≥12 to make a subsequence of length 8 with a positive sum, and also ≤–7 to make a subsequence of length 11 with a negative sum, so it really is not possible to extend it further.

So a sequence containing sequential sub-sequences of length P with minimum positive sums and sequential sub-sequences of length N with minimum negative sums has a maximum length of P + N – 2?

The grid argument can be generalised to show that a sequence of length

P + N – 1is never possible. So the maximal possible length of sequence is indeedP + N – 2, but it’s not always possible to solve the set of equations wherepand_{i}= 1n(although that doesn’t necessarily preclude other solutions of length_{i}= –1P + N – 2).I modified my program to take

PandNas command line parameters and you can generate solutions like this:but not all

P, Ngive solutions (e.g.P=8, N=12).I suspect my program is only finding solutions when

PandNare co-prime.