Although I am quite slow in responding I have analysed this problem and developed a HP 17BII+ Solver solution that works for any number greater than 3.

Solution
Select N

Lower square value L = IntegerPart(SQuareRT(N)+0.0001)

The solution will be given for N > 3. The ^ or 'hat' symbol means 'to the power of' and '_' is used as a line continuation symbol.

A number of cases exist leading to different solutions to obtain the adjacent numbers to N

1. N = L^2 (at the square value)
2. N = L^2 + 1 (at the first corner after the lower square value)
3. L^2 + 1 < N < L^2 + L + 1 (between the first corner and the next)
4. N = L^2 + L + 1 (at the next corner)
5. N > L^2 + L + 1 (greater than the next corner)

Let A and C be the vertical results and B and D the horizontal results then for each case

1. A = (L – 2)^2 + 1, B = N +1, C = (L+ 2)^2 – 1, D = N – 1

2. A = N + 1, B = (L + 2)^2 + 2, C = (L + 2)^2, D = N - 1

3. A = N + 1,B = (L + 2)^2 + (N – L^2) + 1, C = N – 1, D = (L - 2)^2 + (N – L^2) – 1

4. A = (L + 2)^2 + (N – L^2) + 3, B = (L + 2)^2 + (N – L^2) + 1, C = N – 1, D = N + 1

5. A = (L + 2)^2 + (N – L^2) + 3, B = N – 1, C = (L - 2)^2 + (N – L^2) + 3, D = N + 1

I have written a HP 17bII+ Solve program to output the results.

ULAM = IF(N<4:0:(L(L:IP(SQRT(N)+0.0001))+L(L2:LxL)+ _

IF(N=L2:L(A:(L-2)x(L-2)+1)+L(B:N+1)+L(C:(L+2)x(L+2)-1) +L(D:N-1):0)+ _

IF(N=L2+1:L(A:N+1)+L(B:(L+2)x(L+2)+2)+L(C:B-2) +L(D:N-1):0)+ _

IF(N>L2+1 AND N<L2+L+1:L(A:N+1)+L(B:(L+2)x(L+2)+N-L2+1)+ _
L(C:N-1)+L(D:(L-2)x(L-2)+N-L2-1):0)+ _

IF(N=L2+L+1:L(A:(L+2)x(L+2)+N-L2+3)+L(B:A-2)+ L(C:N-1) +L(D:N+1):0)+ _

IF(N>L2+L+1:L(A:(L+2)x(L+2)+(N-L2)+3)+L(B:N-1)+ _
L(C:(L-2)x(L-2)+N-L2-3)+L(D:N+1):0))x0+A+B+C+D)

It is important to check that the brackets match as this may lead to a compile problem or spurious results.

On the menu bar input N and press ULAM. To see the results RCL A, RCL B, RCL C and RCL D.

I hope this may be of passing interest and gives another example of HP 17bII+ programming.