Different upper and lower bound

From Polymath1Wiki
Jump to: navigation, search

If [math]N(a,b)[/math] is the maximum length of a [math]\pm 1[/math] sequence with the partial sums along its HAPs bounded below by [math]-a[/math] and above by [math]b[/math], then:

[math]N(a, b) = N(b, a)[/math]

[math]N(0, b) = b[/math] (everything must be [math]+1[/math])

[math]N(1, 1) = 11[/math] (there are [math]4[/math] such sequences: choose [math]x_1[/math], and use the constraints [math]x_n +x_{2n} = 0[/math] and [math]x_1 + \ldots + x_{2n} = 0[/math] to determine the entries up to [math]10[/math]; then choose [math]x_{11}[/math]) (alternatively: Our first placement can be arbitrary, so suppose 6 is +. This forces 12-, which forces 3- and 9+, which forces 2- and 4+, which forces 1+ and 8-, which forces 5- and 10+, which forces 7+, and a contradiction when d = 1 and k = 10. The sequence is thus: + – - + – + + – + + . -)

[math]N(1, 2) = 41[/math] (there are [math]4[/math] such sequences -- example below)

[math]N(1, 3) = 83[/math] (there are [math]216[/math] such sequences -- example below)

[math]N(1, 4) = 131[/math] (there are [math]87144[/math] such sequences -- example below)

[math]N(1,b)\lt\infty[/math] (On a conjecture of Erdős and Čudakov)

 Question: is [math]N(1,b)[/math] always prime? 

[math]N(2, 2) = 1160[/math] (e.g the first 1124-sequence)

For the zero-based problem, see this comment

Method

Here should be a short description of the way the sequences was found. (The code(s) used should be further down this page.)

Status

Is the data still relevant (e.g. longest know)? Is the method still relevant, or have we found a better method? Is the program still running on a computer somewhere?

The data

[math]N(1, 2) = 41[/math] (there are [math]4[/math] such sequences -- example below)

0 + - - + - + + - + + - - +
- + + - + - - - + - + + - -
+ + - + - + + - - - + - + +

[math]N(1, 3) = 83[/math] (there are [math]216[/math] such sequences -- example below)

0 - + - + - + + - + + - - +
- + + - - + - - + - + + - +
+ + - - - + + - + + - - + -
+ - - + + - - + - + + + - +
- - - + + - + - + - - + - +
+ - + + - - + - + - - - + +


[math]N(1, 4) = 131[/math] (there are [math]87144[/math] such sequences -- example below)

0 + - - + - + + - - + -
+ + - + + + + - - - + -
- + - + + - - + + + - -
- + + - + - + - - + + -
+ + - - + - - + - + + +
+ - - + - + - - + + + -
+ - - - - + + - - - + +
- - + + + + - - - - + +
- + - + + + + - - + + -
+ - - - + + - - - + - -
+ + + - + + - - + - - +

[math]N(2, 2) = 1160[/math]

--Alec 13:46, 9 January 2010 (UTC)


Relevant code

The code(s) (or a link to the code(s)) used to find this sequence should be posted here.