[seqfan] Re: Four grid-based sequences
Jean-Luc Manguin
jean-luc.manguin at unicaen.fr
Fri Jun 19 09:37:11 CEST 2020
Hello Ali,
Your problem is (IMO) a variation of the problem of polyominoes ; the differences are :
- the nodes are labelled with numbers.
- corner connections are allowed
So the model to use in this case is graph-based, with labelled nodes.
The labels make things a bit more complicated, but as you also consider symmetry or not, it can be solved by a backtracking algorithm (transfer matrix algo is much faster but symmetry is difficult to take in account, maybe impossible...)
If I had to solve it, I would consider the problem without labels and make an implementation of the algorithm. After that you could add the constraints with the labels.
Best regards,
JLM
----- Mail original -----
De: "seqfan" <seqfan at list.seqfan.eu>
À: "seqfan" <seqfan at list.seqfan.eu>
Cc: "Ali Sada" <pemd70 at yahoo.com>
Envoyé: Vendredi 19 Juin 2020 04:10:01
Objet: [seqfan] Four grid-based sequences
Hi Everyone,
Please see the 4 sequences below. I need help with their definitions and with finding more terms. Sorry in advance if the terminology I am using is not proper.
1. In the corner of a 2D grid, we put 1. Now, we put the other numbers such that n is connected to n-1. Symmetry is not allowed.
We start with a(1) = 1.
Now, 2 has 2 potential squares: (1,2) and (2,2). So, a(2) = 2.
Based on the places of 2, 3 will have 8 potential squares.
4 will have 38 potential squares, and 5 will have 196, and so on.
1 ,2 , 8, 38, 196,
These shapes might explain the idea in a better way:
https://justpaste.it/6qxc0
2. The same idea of the first sequence except that n could be connected to any number already on the grid. Symmetry is not allowed.
The sequence here will be 1, 2, 8, 53, 463,
These are the shapes generated by this algorithm
https://justpaste.it/6qju4
3. The same idea of the first sequence but the grid here has no edges. We put 1 in any square on the grid and we continue. n should be connected to n-1, and symmetry is not allowed.
The sequence here is
1, 2, 8, 47, 295,
These are the shapes generated by this algorithm
https://justpaste.it/4l3p4
4. In this version, the grid here also has no edges, n could be connected to any number already on the grid, and symmetry is not allowed.
The sequence here is
1, 2, 13, 154, 2419,
These are the shapes generated by this algorithm
https://justpaste.it/2b92w
(I know it seems like self-serving, but I really like the shapes of this version!)
I found the terms of the sequences above “by hand”, so the possibility of a mistake is there, as usual.
I also need help with two more sequences. The same ideas of sequences 2 and 4, but with one symbol (e.g. “*”) instead of numbers.
Best,
Ali
--
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list