Finding which side of a Ulam spiral certain numbers are on

Help and Feedback Scripting Support
,
#1

This topic is leading on from one I made back last decade - which can be found here.

In that topic I was able to calculate the adjacent sides of only one diagonal however not the rest of the spiral then due to time pressure I had to implement a less mathematical way however I am now able to revisit this topic.

My use for finding the adjacent squares is to create a land purchasing system, similar to how @Defaultio did in Lumber Tycoon 2. The basics are that when you purchase a block of land all the blocks surrounding it become available to purchase, this can be done either manually inputting the adjacent squares for each block and removing the squares in use or can be done by using a Ulam spiral with some equations and removing the squares already bought.

Current Progress:

We have four equations at our disposal to find out the four diagonals as shown in the image below.

However by slightly changing the equation we are able to have an equation for EVERY number.

So with this we can create a table with all numbers and a corresponding equation. So it would look something like this:


local n -- Needed later

local actualEquations -- Needed later

local equations = {
	eq1 = {17,35}, -- 4n^2 - 2n + 5
	eq2 = {16,34}, -- 4n^2 - 2n + 4
	eq3 = {5,15,33}, -- 4n^2 - 2n + 3
	eq4 = {4,14,32}, -- 4n^2 - 2n + 2
	eq5 = {1,3,13,31}, -- 4n^2 - 2n + 1
	eq6 = {2,12,30}, -- 4n^2 - 2n
	----
	eq7 = {6,8,24,48}, -- 4n^2 - 4n
	eq8 = {1,9,25,49}, -- 4n^2 - 4n + 1
	eq9 = {2,10,26}, -- 4n^2 - 4n + 2
	eq10 = {3,11,27}, -- 4n^2 - 4n + 3
	eq11 = {12,28}, -- 4n^2 - 4n + 4
	eq12 = {13,29}, -- 4n^2 - 4n + 5
	----
	eq13 = {4,6,20,42}, -- 4n^2 + 2n
	eq14 = {1,7,21,43}, -- 4n^2 + 2n + 1
	eq15 = {2, 8, 22, 44}, -- 4n^2 + 2n + 2
	eq16 = {9,23,45}, -- 4n^2 + 2n + 3
	eq17 = {10,24,46}, -- 4n^2 + 2n + 4
	eq18 = {25,47}, -- 4n^2 + 2n + 5
	----
	eq19 = {2,4,16,36}, -- 4n^2
	eq20 = {1,5,17,37}, -- 4n^2 + 1
	eq21 = {6,18,38}, -- 4n^2 + 2
	eq22 = {7,19,39}, -- 4n^2 + 3
	eq23 = {20,40}, -- 4n^2 + 4
	eq24 = {21, 41} -- 4n^2 + 5
}

The next thing is a function which will calculate an answer based on n. Because actualEquations is defined outside of the function, everything in the script is able to access the answers


local function calculate(n)
	 actualEquations = {
		eq1 = {4*n^2 - 2*n + 5},
		eq2 = {4*n^2 - 2*n + 4},
		eq3 = {4*n^2 - 2*n + 3},
		eq4 = {4*n^2 - 2*n + 2},
		eq5 = {4*n^2 - 2*n + 1},
		eq6 = {4*n^2 - 2*n},
		----
		eq7 = {4*n^2 - 4*n},
		eq8 = {4*n^2 - 4*n + 1},
		eq9 = {4*n^2 - 4*n + 2},
		eq10 = {4*n^2 - 4*n + 3},
		eq11 = {4*n^2 - 4*n + 4},
		eq12 = {4*n^2 - 4*n + 5},
		----
		eq13 = {4*n^2 + 2*n},
		eq14 = {4*n^2 + 2*n + 1},
		eq15 = {4*n^2 + 2*n + 2},
		eq16 = {4*n^2 + 2*n + 3},
		eq17 = {4*n^2 + 2*n + 4},
		eq18 = {4*n^2 + 2*n + 5},
		----
		eq19 = {4*n^2},
		eq20 = {4*n^2 + 1},
		eq21 = {4*n^2 + 2},
		eq22 = {4*n^2 + 3},
		eq23 = {4*n^2 + 4},
		eq24 = {4*n^2 + 5},
	}
end

The next thing we are going to need to find is which layer a number is on so we know what to substitute. We can simply find this by finding the largest number on each layer and if it is bigger than the previous layer but smaller of the same as the biggest on that layer it is on that layer. This equation is 4n^2-4n+1


local function findLayer(number)
	for n = 0,5 do
		local max = 4*n^2-4*n+1
		n = n-1
		local min = 4*n^2-4*n+1
		if min < number and max >= number then
			return n
		end
	end
end

Next, we need to find which equation the number uses, this is using the table named equations we made earlier.


local function findEquation(toFind)
	for i, eq in pairs(equations) do
		for _, number in pairs(equations[i]) do
			if toFind == number then
				return i
			end
		end
		
	end
	
end

Now we just need a function to return the perpendicular adjacent numbers.

local function adjacentSquares(number)
	
	local adjacent = {}
	table.insert(adjacent, #adjacent+1, number+1) -- Appends the + and - 1 adjacent squares
	table.insert(adjacent, #adjacent+1, number-1)
	
	n = findLayer(number) -- Finds the current layer
	local eq = findEquation(number) -- Finds the equation to use
	print(eq)
	
	
	local plusOne = calculate(n+1)
	plusOne = actualEquations[eq]
	table.insert(adjacent, #adjacent+1, plusOne[1]+1)
	
	local minusOne = calculate(n-1)
	minusOne = actualEquations[eq]
	table.insert(adjacent, #adjacent+1, minusOne[1]-1)
	
	
	return adjacent
end

Exception:

You can not find the numbers on the diagonals through 1: Including the numbers: 1,3,13,31,7,21,43,9,25,49,5,17,37

There are three ways to find them:

Method 1:

Hard code them

Method 2:

± the number then use the equation where n = n+1 and ± that result

Method 3:

Use the equation where n = n+1 and n = n-1 then ± both the results to find the adjacent perpendicular

My Question

With the current system of finding the perpendicular numbers along two sides of the Ulam spiral, you need to add to plusOne and on the other two subtract from plusOne the same goes for minusOne. So the big question is how do I, without hard coding find the side of the Ulam spiral that any number is on. - Basicaly I am looking for an equation to find which side of a Ulam spiral any number is on.

2 Likes
#2

Would you have perhaps done a search and found this?
https://en.wikipedia.org/wiki/Module:Ulam_spiral

#3

I don’t wish to generate a Ulam sprial, I need to know which side if the spiral a certain number is on.

#4

To be clear, you’re trying to create an O(1) formula to find the nth cell in your spiral?

#5

Basically a formula to find which side of the spiral a number is relative to another number e.g. 2 from there I would know weather to add or subtract from the diagonals.

So if I input 28 it should output 2 or if I input 46 it would output 8. I hope this makes sense.

#6

Is this an x-y problem? What are you trying to accomplish with this formula?

This seems very different from what you’re asking.

#7

The question, detecting which side of the Ulam spiral relative to another number is part of my solution to find which plots of land are available to be purchased - Sorry if I was not clear.

I think I explain it slightly better here:

Sorry for any confusion :slight_smile:

#8

What I’m saying is that you’ve trapped yourself in thinking that you need this specific formula for this specific solution. You should back up and reconsider another method because there are certainly easier ways. I’ll give a crack at it if I get the time.

1 Like
#9

Yes, there may be other methods and I would be perfectly happy to use them, this is just the one that I was having the most success with until this point.

1 Like
#10

Ok, not a maths expert but a coder for some time so here is my go.
You have supplied some data and a few functions but I cannot find the code that uses them.
Could you point that out to me please or supply if you agree its not supplied.

#11

All I do is fire the adjacentSquares function with any number. You then get a table with the adjacent squares if the side is correct, I need to know which side it is on to be able to get the adjacent squares for all 4 sides of the spiral.

local AS = adjacentSquares(4)

You can then print the adjacent squares like this:

print(unpack(AS))

#12

Ok thanks.
For 4 I got just 5317-1
was that expected?

#13

No, this is the problem the output should be 5, 3, 15, 1. You can see where it goes wrong where it adds instead of subtracting from 2 and 16. However it works on a number on a different side e.g. 11 it will work for. I need to know which side of the spiral it is on to know if I should add or subtract from the diagonal numbers.

#14

I handled a similar problem in my game. I ended up using Cantor pairing to encode an x and y coordinate into a label. Cantor pairing only works for naturals, so we can only accept integers and to accept all integers (negatives included) we need to map the integers to naturals by doing n = 2*n for naturals and n = -n * 2 - 1 for negative integers.

In the end you get this:

function getPairingId(x, y)
    x = x >= 0 and x * 2 or -x * 2 - 1
    y = y >= 0 and y * 2 or -y * 2 - 1
    return 0.5 * (x + y) * (x + y + 1) + y
end

And to go from a label back to a coordinate pair we can do the inverse:

function undoPairingId(id)
    local w = math.floor(((8 * id + 1)^.5 - 1) / 2)
    local t = (w^2 + w) / 2
    local y = id - t
    local x = w - y

    x = x%2>0 and (x + 1) / -2 or x / 2
    y = y%2>0 and (y + 1) / -2 or y / 2

    return x, y
end

Now you can go back and forth between x,y coordinates and ids. For example to get the neighbours you can do the following.

local x, y = undoPairingId(center)
local top = getPairingId(x, y + 1)
local right = getPairingId(x + 1, y)
local bottomRight = getPairingId(x + 1, y - 1)
...etc

While it doesn’t answer your question, I hope this gives you fresh idea on how this could be approached.

2 Likes
#15

Ok, had a go at trying to see why it returned based on 11 being a good run and 4 being a bad.
calculate does not return anything. Is it supposed to?

#16

No, calculate does not need to return anything because actualEquations is defined outside of the functions, every function in the script can see it, it just changes what eqx is.

#17

so these lines of code are supposed to do nothing then

	local plusOne = calculate(n+1)

	local minusOne = calculate(n-1)

I will continue my efforts.

#18

Hi! To be honest, I did not fully understand your question. But I wrote this quick script for you, it’s not great or optimized, but maybe it can help:

local function getCycleEnd(cycleNumber)
	return math.pow((2*(cycleNumber-1) + 1),2)
end

local function getUlamCoordinates(x)
	local roundNumber = math.ceil((math.sqrt(x)+1)/2)
	
	local cycleStart = getCycleEnd(roundNumber-1)+1
	if x==1 then return Vector2.new() end
	local cycleEnd = getCycleEnd(roundNumber)
	
	local difference = cycleEnd-cycleStart+1
	local sideLength = math.max(difference/4, 1)
	local position = (x-cycleStart) % sideLength
	local sideDirection = math.ceil((x-cycleStart+1) / sideLength)
	if sideDirection == 1 then
		return Vector2.new(roundNumber-1, position - math.floor(sideLength/2)+1)
	elseif sideDirection == 2 then
		return Vector2.new(math.floor(sideLength/2) - position -1, roundNumber-1)
	elseif sideDirection == 3 then
		return Vector2.new(-1*(roundNumber-1), math.floor(sideLength/2) - position-1)
	elseif sideDirection == 4 then
		return Vector2.new(position - math.floor(sideLength/2)+1, -1*(roundNumber-1))
	end
	
end

for x=1, 26 do
	print(getUlamCoordinates(x))
end

Basically I assign the first number (1) to coordinates [0,0]. Then 2 goes to [1,0], then 3 goes to [1,1], 4 goes to [0,1], etc.

We can calculate which ‘round’ a number X is in (0 to 1, 2 to 9, 10 to 25, etc) by noting that the next round always starts at (2n-1)^2

Then we calculate in which side of that round the number X is in, and which position in that side it has. I simply did an if-else statement on the side, to get the coordinates.

So maybe that answers your question, to know the side for a particular X you determine when the round that X is in started, ends, and how far into that round you are.

In case you were looking for the neighbours of numbers in the Ulam spiral, I would use a similar approach and convert the (neighbouring) coordinates back into numbers.

Hope this helps!
Kind regards,
Nonaz_jr

2 Likes