GPNS

GPNS (grid path number sequence) is an esoteric number sequence invented by User:Hakerh400 in 2022.

Overview

Each number in the sequence represents the longest Von Neumann path that can exist in an $n\times n$ grid.

For $n=0$, the length of the longest path is $0$.

For $n=1$, the length of the longest path is $1$.

For $n=2$, here is the longest path:

##
.#

The # symbol represents path, while the . symbol represents void. The path starts at the top-left corner and ends at the bottom-right corner. The length of the path is $3$. Note that there are multiple longest paths. For example, this is also the longest path:

 ##
 #.

For $n=3$, here is the longest path:

 ###
 ..#
 ###

The length of the path is $7$.

For $n=4$, the maximal path length is $11$:

####
...#
#..#
####

So, the sequence begins with $0,1,3,7,11,\dots$

Properties

The author is not sure what the $5$th term of the sequence is (the naive implementation takes years to compute). The author also believes that there is no simple formula for the $n$-th term.

Implementation

Implementation in Haskell:

import Control.Monad

main :: IO ()
main = mapM_ (print . f) [0..3]

f :: Int -> Int
f n = maximum' # map (path_len n (mk_coords n) . mk_mat n) #
 replicateM (n ^ 2) [0, 1]

mk_mat :: Int -> [a] -> [[a]]
mk_mat n xs = ite (null xs) [] # take n xs : mk_mat n (drop n xs)

mk_range :: Int -> [Int]
mk_range n = [0 .. n - 1]

mk_coords :: Int -> [[(Int, Int)]]
mk_coords n = mk_mat n # do
 a <- mk_range n
 b <- mk_range n
 return (a, b)

maximum' :: [Int] -> Int
maximum' xs = ite (null xs) 0 (maximum xs)

has :: Int -> Int -> Int -> Bool
has n y x = y >= 0 && x >= 0 && y < n && x < n

get :: Int -> Int -> [[a]] -> a
get y x mat = mat !! y !! x

modify' :: Int -> (a -> a) -> [a] -> [a]
modify' 0 f (x:xs) = f x : xs
modify' n f (x:xs) = x : modify' (n - 1) f xs

modify :: Int -> Int -> Int -> (a -> a) -> [[a]] -> [[a]]
modify n y x f mat = ite (has n y x) (modify' y (modify' x f) mat) mat

set' :: Int -> a -> [a] -> [a]
set' 0 z (x:xs) = z : xs
set' n z (x:xs) = x : set' (n - 1) z xs

set :: Int -> Int -> Int -> a -> [[a]] -> [[a]]
set n y x z mat = ite (has n y x) (modify' y (set' x z) mat) mat

path_len :: Int -> [[(Int, Int)]] -> [[Int]] -> Int
path_len n cs mat = maximum' # map (calc_len n mat) #
 filter (\(y, x) -> get y x mat == 1) # concat cs

calc_len :: Int -> [[Int]] -> (Int, Int) -> Int
calc_len n mat (y, x) = iter (step n) # set n y x 2 mat

iter :: (Eq a) => (a -> a) -> a -> Int
iter f z = let z1 = f z in ite (z1 == z) 1 (1 + iter f z1)

step :: Int -> [[Int]] -> [[Int]]
step n mat = map_mat (modify_tile n mat) mat

modify_tile :: Int -> [[Int]] -> Int -> Int -> Int -> Int
modify_tile n mat k y x =
 ite (get y x mat == 1 && (any (\(y, x) -> get y x mat == 2) # adjs n y x)) 2 k

adjs' :: Int -> Int -> [(Int, Int)]
adjs' y x = [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]

adjs :: Int -> Int -> Int -> [(Int, Int)]
adjs n y x = filter (\(y, x) -> has n y x) # adjs' y x

map' :: (a -> Int -> a) -> [a] -> [a]
map' f xs = zipWith f xs [0..]

map_mat :: (a -> Int -> Int -> a) -> [[a]] -> [[a]]
map_mat f = map' # \row y -> map' (\k x -> f k y x) row

infixr 0 # -- Sorry, I don't like money
(#) = id

ite :: Bool -> a -> a -> a
ite True a b = a
ite False a b = b