StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is an observation for when N is divisible by 3... Probably not useful, but I feel like writing it down.</p> <p>Let <code>w</code> (complex) be a primitive cube root of 1; that is, <code>w^3 = 1</code> and <code>1 + w + w^2 = 0</code>. For example, <code>w = cos(2pi/3) + i*sin(2pi/3)</code>.</p> <p>Consider the sum <code>x_0 + x_1*w + x_2*w^2 + x_3 + x_4*w + x_5*w^2 + ...</code>. That is, multiply each element of the sequence by consecutive powers of <code>w</code> and add them all up.</p> <p>Something moderately interesting happens to this sum on each step.</p> <p>Consider three consecutive numbers <code>[a, -b, c]</code> from the sequence, with b positive. Suppose these elements line up with the powers of <code>w</code> such that these three numbers contribute <code>a - b*w + c*w^2</code> to the sum.</p> <p>Now perform the step on the middle element.</p> <p>After the step, these numbers contribute <code>(a-b) + b*w + (c-b)*w^2</code> to the sum.</p> <p>But since <code>1 + w + w^2 = 0</code>, <code>b + b*w + b*w^2 = 0</code> too. So we can add this to the previous expression to get <code>a + 2*b*w + c</code>. Which is very similar to what we had before the step.</p> <p>In other words, the step merely added <code>3*b*w</code> to the sum.</p> <p>If the three consecutive numbers had lined up with powers of <code>w</code> to contribute (say) <code>a*w - b*w^2 + c</code>, it turns out that the step will add <code>3*b*w^2</code>.</p> <p>In other words, no matter how the powers of <code>w</code> line up with the three numbers, the step increases the sum by <code>3*b</code>, <code>3*b*w</code>, or <code>3*b*w^2</code>.</p> <p>Unfortunately, since <code>w^2 = -(w+1)</code>, this does not actually yield a steadily increasing function. So, as I said, probably not useful. But it still seems like a reasonable strategy is to seek a "signature" for each position that changes monotonically with each step...</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload