Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question concerns the sequence of integers which form the solution to a particular computational problem. See the bottom for the full formulation; basically, for some value n, $G(n)$ is the number of 2-D lattice locations that are connected given a particular constraint on $n$ and the lattice coordinates $x$ and $y$. The question is: assuming the function is a continuous piecewise integer-valued polynomial, is there is a closed form solution that can be determined from a finite number of samples? I have found a solution just on a small subset of the data.

The cost of computing the function by brute force increases quickly, so the number of easily available samples is limited. The sequence begins with these values: 1, 5, 13, 25, 41, 61, 85, 113, 145, 505, 1121, 2025, 3245, 4805, 6725, 9021, 11705, 14785, 47905, 102485, 181533, 287881, 424129, 592597, 795285, 1033841, 1309537, 4216357, 9006221, 15961125, 25353625, 37441397, 52462177, 70629201, 92127245, 117109345, 377329873, 807129569, 1432989909.

These exhibit an interesting periodicity in the log plot of $G(n)$:

Gridwalk values

The first 9 values in this sequence match OEIS A001844 ($G_{0,8}(n)=2n(n+1)+1$), but then they diverge. Since the first segment is polynomial, I guessed that the second might be as well, and sure enough, polynomial regression shows a perfect quartic fit on [8,17] for $G_{8,17}(n)=-1/6 n^4+35/3 n^3-635/6 n^2+115/3 n+1321$, although its roots aren't friendly like the quadratic.

Gridwalk polynomial overlay

Then I hit a wall. The next segments look similar, but polynomial fit on the third and later segments is lousy for degree up to 10. Can anyone determine the form of these (and subsequent, unsampled) pieces of the function?

Other questions:

  1. Can the cofficients of $G_{8,17}$ be logically inferred from $G_{0,8}$?
  2. Is there a simple factorization of the quartic?
  3. Why is the period of the oscillation equal to 9? (c.f. $G(n+1)/G(n)$ below) Presumably the decimal base is implicated because digits are being summed in the constraint function.

G(n+1)/G(n)

Here's the original function description from the CodeEval Gridwalk Challenge:

There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

share|improve this question
    
Integer valued polynomials sounds a bit restrictive? –  copper.hat Dec 11 '12 at 21:04
    
Any ideas what they might be instead? –  Adam Thomason Dec 11 '12 at 21:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.