Mythic squares/rectangles - Page 2

Till · 2018-08-11, 18:44

A 7x7 with score 108 (random search result):

Code:

2 4 4 9 8 2 2
4 0 6 7 8 4 4
1 0 3 6 7 5 0
1 8 5 1 2 9 0
1 0 0 5 3 3 4
7 0 1 1 4 3 3
9 9 2 5 4 1 6

Dr Sardonicus · 2018-08-12, 14:49

Alas, I am no good at all at this sort of puzzle. About all that comes to mind is some generalities.

The thought did occur to me that, in order to maximize the chances of getting all possible k-digit strings, you want as many cells as possible surrounded by as many different digits as possible. There may be some "known" way of doing this.

Since each cell not on the perimeter has 8 adjacent cells, it might be that you can do significantly better with octal numbers, or even a smaller base.

Perhaps more is known about the binary case.

science_man_88 · 2018-08-12, 15:45

only 16 values per central value (including diagonals) so showing up in 18 times, in 2 digit numbers means each digit shows up twice under 100.

Till · 2018-08-12, 18:22

I improved my search algorithm and found a better 3x5 solution, a better 6x6 and added some more data.

The best non-trivial mythic rectangle solutions I know so far are:

Code:

2x6: score=21
[7, 1, 1, 4, 1, 8]
[0, 2, 6, 5, 3, 9]

2x7: score=32
[9, 2, 7, 5, 2, 1, 8]
[6, 1, 1, 3, 0, 2, 4]

2x8: score=37
[8, 2, 7, 3, 6, 1, 1, 0]
[9, 1, 5, 3, 4, 2, 2, 3]

2x9: score=43
[3, 6, 2, 2, 0, 4, 1, 5, 3]
[3, 8, 1, 1, 3, 9, 2, 7, 0]
 
3x4: score=26
[5, 1, 0, 7]
[4, 2, 1, 8]
[2, 3, 6, 9]
 
3x5: score=38
[3, 4, 7, 0, 3]
[5, 1, 2, 3, 1]
[9, 2, 6, 8, 1]

3x6: score=46
[0, 9, 1, 8, 7, 2]
[3, 0, 2, 1, 3, 2]
[6, 4, 4, 5, 6, 3]

3x7: score=54
[3, 3, 6, 2, 9, 3, 1]
[2, 5, 4, 1, 2, 4, 1]
[1, 0, 3, 7, 3, 8, 4]

3x8: score=65
[1, 1, 0, 3, 7, 4, 7, 3]
[0, 2, 6, 5, 1, 3, 4, 2]
[2, 4, 5, 9, 8, 3, 9, 8]

4x4: score=43
[3, 6, 2, 8]
[5, 9, 1, 3]
[2, 1, 0, 3]
[4, 2, 7, 4]

4x5: score=54
[5, 3, 3, 1, 4]
[2, 7, 1, 4, 5]
[2, 6, 4, 0, 2]
[1, 8, 3, 9, 1]
     
4x6: score=66
[1, 6, 5, 9, 8, 3]
[1, 6, 4, 7, 1, 9]
[2, 0, 3, 5, 2, 4]
[5, 2, 3, 5, 8, 4]

4x7: score=79
[1, 4, 9, 7, 5, 9, 3]
[4, 1, 2, 6, 8, 1, 5]
[7, 0, 6, 2, 3, 4, 7]
[5, 5, 2, 0, 6, 3, 7]

4x8: score=98
[7, 4, 4, 8, 9, 1, 7, 8]
[9, 2, 2, 3, 1, 6, 8, 7]
[0, 5, 3, 0, 5, 5, 4, 0]
[6, 6, 3, 7, 2, 1, 6, 2]

5x5: score=76
[6, 0, 6, 5, 1]
[7, 4, 5, 6, 2]
[0, 1, 4, 9, 2]
[2, 3, 1, 8, 3]
[4, 7, 5, 3, 6]

5x6: score=99
[1, 7, 9, 4, 4, 3]
[7, 1, 5, 7, 0, 3]
[8, 6, 3, 5, 2, 0]
[8, 9, 0, 2, 8, 6]
[3, 9, 9, 1, 4, 6]

5x7: score=102
[3, 0, 4, 4, 1, 9, 2]
[3, 8, 6, 0, 9, 2, 8]
[8, 6, 1, 0, 7, 4, 8]
[7, 1, 0, 5, 3, 1, 5]
[7, 1, 2, 2, 6, 9, 5]

6x6: score=101
[9, 1, 1, 7, 5, 6]
[3, 9, 9, 0, 6, 1]
[6, 1, 2, 8, 1, 0]
[4, 2, 5, 9, 3, 0]
[4, 7, 4, 3, 5, 2]
[7, 8, 8, 0, 7, 5]

6x7: score=105
[6, 7, 8, 2, 6, 5, 5]
[7, 5, 3, 2, 0, 1, 1]
[2, 4, 9, 1, 0, 0, 0]
[1, 0, 7, 9, 1, 4, 3]
[8, 7, 3, 9, 4, 8, 5]
[6, 3, 9, 6, 8, 6, 6]

7x7: score=108
[6, 9, 4, 5, 2, 4, 7]
[9, 6, 8, 2, 5, 9, 4]
[4, 5, 8, 8, 9, 3, 7]
[4, 7, 3, 1, 0, 7, 2]
[1, 0, 0, 5, 6, 1, 1]
[6, 0, 1, 0, 2, 1, 3]
[5, 0, 1, 1, 2, 6, 3]

Table of best scores found so far:

Code:

  x |  1  2  3  4   5   6   7  8  9 10  11  12  13
 ---+------------------------------------------------------
  1 |  1  2  3  4   5   6   7  8  9 10  12  14  16
  2 |  2  4  6  8  10  21  32 37 43
  3 |  3  6  9 26  38  46  54 65
  4 |  4  8 26 43  54  66  79 98
  5 |  5 10 38 54  76  99 102
  6 |  6 21 46 66  99 101 105
  7 |  7 32 54 79 102 105 108
  8 |  8 37 65 98
  9 |  9 43
 10 | 10
 11 | 12
 12 | 14
 13 | 16

EDIT: I think that the values for mxn-rectangles are quite safe for m+n<=8

Till · 2018-08-12, 19:07

Base 2 is quite easy, I believe all maximum scores here are settled.

Code:

  x |  1  2  3  4  5  6  7  8  9 10 11  
 ---+----------------------------------------
  1 |  1  2  3  4  4  6  7  8  8  8 14(!)
  2 |  2  3  5  6  8 10 15 16 16
  3 |  3  5  7 10 13 16 16 20
  4 |  4  6 10 15 18 20 22
  5 |  4  8 13 18 26 32
  6 |  6 10 16 20 32
  7 |  7 15 16 22
  8 |  8 16 20
  9 |  8 16
 10 |  8
 11 | 14(!)

Nothin' found in OEIS, not even the 1xn maximum score sequence 1 2 3 4 4 6 7 8 8 8 14...

Till · 2018-08-12, 20:22

Concerning base 2, I just noticed that there are some OEIS sequences matching the central terms 1, 3, 7, 15, 26. The most interesting ones seem to be A073817, A001648, A051054, A131076, A001649 and A074081.

I'll try to find more reliable data tomorrow.

Till · 2018-08-13, 15:12

Quote:

Originally Posted by science_man_88

only 16 values per central value (including diagonals) so showing up in 18 times, in 2 digit numbers means each digit shows up twice under 100.

Hi science_man,
I think I understand the first part: Like in

Code:

2 3 4
9 1 5
8 7 6

, the "1" turns up in 16 2-digit combinations.

What do you mean with "showing up in 18 times"?

The last part refers to score 100?
If that's true I have it incorporated in my program, and more than that, two equal digits have to be "neighbors".

science_man_88 · 2018-08-13, 16:49

Quote:

Originally Posted by Till

Hi science_man,
I think I understand the first part: Like in

Code:

2 3 4
9 1 5
8 7 6

, the "1" turns up in 16 2-digit combinations.

What do you mean with "showing up in 18 times"?

The last part refers to score 100?
If that's true I have it incorporated in my program, and more than that, two equal digits have to be "neighbors".

10
11
12
13
14
15
16
17
18
19
21
31
41
51
61
71
81
91

18 terms in 2 digits only ,16 can be done by just 1 of a digit. It was only a basic observation. I bet a better obserbation would force most if not all placements.

Till · 2018-08-13, 17:05

Ok, its the possible number of combinations. Thanks.

Till · 2018-08-13, 17:15

Quote:

Originally Posted by Till

Concerning base 2, I just noticed that there are some OEIS sequences matching the central terms 1, 3, 7, 15, 26. The most interesting ones seem to be A073817, A001648, A051054, A131076, A001649 and A074081.

The record score for 6x6 squares in base 2 seems to be 42.
Example:

Code:

[0, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0]
[1, 1, 1, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 1, 0, 1]
[1, 0, 0, 0, 1, 1]

And the best 7x7 score might be 64, example:

Code:

[1, 0, 1, 0, 0, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 0, 1, 0]
[1, 1, 0, 1, 1, 1, 0]
[0, 1, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 1, 0]
[1, 1, 0, 0, 0, 1, 1]

The first 6x6 square with score 42 turned up after testing 300k squares, nothing new within 10 mio square tests. So I am quite confident that it has the maximum score.

The first 7x7 square with score 64 turned up after testing 15mio squares, nothing new within 63.7 mio square tests. Less confidence here, but still some (75% maybe).

So the central term sequence might be 1, 3, 7, 15, 26, 42, 64, ...
The only possible match in OEIS is A131076 then.

science_man_88 · 2018-08-13, 17:28

Quote:

Originally Posted by Till

Ok, its the possible number of combinations. Thanks.

yeah for 3 digits it climbs to 244 but you can also make 24, 3 digit numbers around 1 use. 4 digits goes to 2952 and 48 etc.

2018-08-11, 18:44	#12
Till "Tilman Neumann" Jan 2016 Germany 448₁₀ Posts	A 7x7 with score 108 (random search result): Code: 2 4 4 9 8 2 2 4 0 6 7 8 4 4 1 0 3 6 7 5 0 1 8 5 1 2 9 0 1 0 0 5 3 3 4 7 0 1 1 4 3 3 9 9 2 5 4 1 6

2018-08-12, 19:07	#16
Till "Tilman Neumann" Jan 2016 Germany 2⁶×7 Posts	Base 2 Base 2 is quite easy, I believe all maximum scores here are settled. Code: x \| 1 2 3 4 5 6 7 8 9 10 11 ---+---------------------------------------- 1 \| 1 2 3 4 4 6 7 8 8 8 14(!) 2 \| 2 3 5 6 8 10 15 16 16 3 \| 3 5 7 10 13 16 16 20 4 \| 4 6 10 15 18 20 22 5 \| 4 8 13 18 26 32 6 \| 6 10 16 20 32 7 \| 7 15 16 22 8 \| 8 16 20 9 \| 8 16 10 \| 8 11 \| 14(!) Nothin' found in OEIS, not even the 1xn maximum score sequence 1 2 3 4 4 6 7 8 8 8 14... Last fiddled with by Till on 2018-08-12 at 19:10 Reason: score sequence, not count sequence

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Find the Squares	a1call	Puzzles	18	2018-03-02 16:47
Regarding Squares	a1call	Miscellaneous Math	42	2017-02-03 01:29
Counting Latin rectangles	Dougy	Math	3	2010-02-16 10:20
squares or not squares	m_f_h	Puzzles	45	2007-06-15 17:46
Prime squares/rectangles	roger	Puzzles	10	2007-05-04 16:07

2018-08-12, 14:49	#13
Dr Sardonicus Feb 2017 Nowhere 4,643 Posts	Alas, I am no good at all at this sort of puzzle. About all that comes to mind is some generalities. The thought did occur to me that, in order to maximize the chances of getting all possible k-digit strings, you want as many cells as possible surrounded by as many different digits as possible. There may be some "known" way of doing this. Since each cell not on the perimeter has 8 adjacent cells, it might be that you can do significantly better with octal numbers, or even a smaller base. Perhaps more is known about the binary case.

2018-08-12, 15:45	#14
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶×131 Posts	only 16 values per central value (including diagonals) so showing up in 18 times, in 2 digit numbers means each digit shows up twice under 100.

2018-08-12, 20:22	#17
Till "Tilman Neumann" Jan 2016 Germany 2⁶×7 Posts	Concerning base 2, I just noticed that there are some OEIS sequences matching the central terms 1, 3, 7, 15, 26. The most interesting ones seem to be A073817, A001648, A051054, A131076, A001649 and A074081. I'll try to find more reliable data tomorrow.

2018-08-13, 17:05	#20
Till "Tilman Neumann" Jan 2016 Germany 2⁶×7 Posts	Ok, its the possible number of combinations. Thanks.