The Grid Arithmetic Problem

[Alex Violette]

Hello SeqFans,

I have invented this problem I cannot seem to solve for a(4) or in other words, it's unknown if it's finite or infinite at this time to me though the latter appears more plausible.

Let a(n) be the largest amount of positive integers that can be placed on a two-dimensional grid where they are all connected(meaning 1 is touching 2 via one of four sides, 2 is touching 3 the same way, and so on) and they do not have an arithmetic progression of n terms on the grid. This progression can have spaces between the terms and it can be angled(a(3) would be infinite if spaces weren't allowed to be counted for it).

Here are examples for what's not allowed for the n=4 case, with arithmetic progressions of four terms displayed in red:

1

2

3

4

-

1		7	8	9
2		6		10		14
3	4	5		11	12	13

-

1	2	3
		4	5	6
				7	8	9
						10

As for the terms of this sequence:

a(1)=0 since even having a 1 down on the grid would make for a 1 term arithmetic progression which is not allowed here.
a(2)=1

a(3)=8

1	4	5	8
2	3	6	7

However, for a(4) it seems to just keep growing and I do not know if it stops or not. This is my current attempt at it and if it is finite and this is correct then a(4)>100:

					57	58	59								101
					56	55	60	61	64	65		85	86	87	100	99
			47	48	49	54	53	62	63	67		84	83	88		98	97
	42	43	46	1	50	51	52			68	69	70	82	89	90	95	96
40	41	44	45	2	3	6	7	10	11		72	71	81	80	91	94
39	38	27	26	25	4	5	8	9	12	13	73	76	77	79	92	93
	37	28	29	24	23	20	19	16	15	14	74	75	78
	36	35	30	31	22	21	18	17
		34	33	32

Can someone help show what happens for a(4) and/or for other terms? What happens for an d-dimensional grid where d>2? Note that for d=1, a(n)=n-1.

Best,
Alex Violette

[Brendan]

Nice problem, Alex.  Regarding the definition, is it that a 4-term ap can't appear in a straight line, or is it only forbidden if they have equal distance between them like in your three examples?

Brendan.

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAAQNUoQX84h00UNb4A8%3Dd804T0PQqt9pNVM76N8zJyMfFKCLUA%40mail.gmail.com.

[Joshua Searle]

In the a(4) example you gave, 66 is missing and there appears no way to connect it to 65 and 67. There is also a diagonal connection between 78 and 79. Variants where diagonal connections are allowed may be interesting to look at also, I expect it would tend to increase the values of a(n) compared to the original as there are more possible moves. That would probably end up being harder to solve as a result. Another variant I thought of was where a new number can be added anywhere, as long as it is connected to the rest in some fashion. That would likely be harder still.

This reminds me of van der waerden numbers which are pretty tricky to calculate but are nonetheless finite, but whether that holds into 2-D I'm not sure.

I was thinking of what constructions may or may not work and one idea is for the numbers to be constricted to an (n-1) row grid as in your n=3 example. I do vaguely remember seeing something along these lines before but I can't remember how relevant it really is, other than it was unable to avoid repeats after about ~1000 terms. Even if such a thing is finite here, it doesn't necessarily imply that it is finite over the whole plane.

Another idea is to construct a spiral designed such that you avoid 4 of anything being in sequence. While this may be possible, it isn't clear to me how you'd avoid ap across many spiral arms.

Joshua.

[Alex Violette]

Hey Joshua,

     thanks for letting me know about the errors. I didn't look it over too much which was why I said the "and this is correct" part earlier for the lower bound. Diagonal connections are something I did consider but I didn't look into it that much yet. I was wondering if such a sequence had been computed in the past but given how I only knew about 3 terms(0,1,8) and how many sequences started with that in the OEIS, I figured I'd be out of luck there at least for now.  
    About your construction idea, I actually looked at that (n-1) grid thing like for the a(3) example and I found for those constructions that the largest number that can be done is 2*(n-1)^2 for when n is odd and (n-1)^2+(n-2)/2 for when n is even. Down below are the constructions like the a(3) example which shows the most you can go before an n-term arithmetic progression shows up for n=4, n=5, and n=6 respectively:

1	6	7
2	5	8	11
3	4	9	10

-

1	8	9	16	17	24	25	32	33
2	7	10	15	18	23	26	31
3	6	11	14	19	22	27	30
4	5	12	13	20	21	28	29

-

1	10	11	20	21
2	9	12	19	22
3	8	13	18	23	28
4	7	14	17	24	27
5	6	15	16	25	26

Another interesting question is if a(4) or some larger term is infinite then is it possible to fill the entire grid or would holes have to be made? If holes have to be made, what would their density be compared to the whole plane?
-Alex V.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/5949885e-6bbf-40b3-994f-9c155a225b4cn%40googlegroups.com.

[Joshua Searle]

I was thinking of more irregular patterns (with holes) that still fit in the (n-1) rows, doing some doodles for a(4) I stopped after I got to 25 with no clear end. I strongly suspect this version is finite, but I can't say whether its of any use in determining whether that is true when not restricted. It does seem that the unbounded version will go on longer despite needing to keep track of all the oblique ap. It's an interesting problem, sadly my coding skills are not up to par for something like this so I'm interested to see what others can find.

Joshua.

[David Cleaver]

I wrote a python program to generate grids for the up/down/left/right (udlr) version of this Grid Arithmetic Problem (gap).
I stopped the a(4) run after it reached 100,000 terms, which took about 5 hours.
The program did a depth first search, and chose directions in an up/right/down/left (ie, clock-wise) order.
This ended up generating a grid that on the large scale looks like a line with a slope of about 2.48.
I have attached a picture showing what the first 437 terms look like, with the last point in the picture at x,y coordinates 83,217.

I think one of the biggest time saving strategies for this search was to realize that,
if you know that your current grid is free from ap4's (arithmetic progressions of length 4) (or any apN, really),
then when adding the next point, you only have to check whether the new point is part of an ap4.
You don't have to re-check the whole grid for ap4's.

My first version was recursive and quickly ran into python's recursion limit of about 1000.
I converted it to an iterative version and was able to get up to 100,000 terms.

I also tried the variant with diagonals included.
I let the search for a(3) of this version get up to 100,000 terms before stopping the program.
The diagonal version produced a grid that, overall, looks like a line with a slope of about 1.19.

I also tried the variant where each next term was a knight's move, or L-move (2 over 1 across), away.
I let the search for a(3) of this version get up to 100,000 terms before stopping the program.
The knight's move version produced a grid that, overall, looks like a line with a slope of about 0.56.
I have attached a picture showing what the first 204 terms look like (instead of the L shape, each line segment is the "2x1" diagonal).
The last point in this picture is at x,y coordinates 253,164.

I don't know for sure, but it seems like the unbounded grid version of these 3 variants,
udlr/udlr+diagonals/L-moves will grow indefinitely for a(4), a(3), and a(3), respectively.

I like the version that Alex suggested asking if any variation can completely fill the grid,
and if not, how dense can each one fill the grid.  It'll be a while before I can look at this,
but I'd be interested to hear if anyone else tackles this question.

I have also attached my python program, and a zip file with the 100k terms for each of the 3 variants.  The zip files are a list of the [x,y] coordinates of each term in that grid.

-David C.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/abbb79bb-9c5c-4504-8a61-953f04adc2f8n%40googlegroups.com.