mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2018-08-09, 17:45   #1
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

236118 Posts
Default Mythic squares/rectangles

While we have heard of magic squares. I started to wonder about a different kind of square (or rectangle). Most of us have worked a word search in our day. I thought about a number search.

The question is what is the minimum size and proper configuration such that you can find within the square/rectangle all numbers from 1->n? This is using the conventional word search rules: straight lines only, continuous, either direction.

The following is the minimum for 1->9. The configuration is irrelevant.
Code:
1 2 3
4 5 6
7 8 9
With a careful rearrangement and going from a 3 x 3 square to a 4 x 3 rectangle we can go much further. The following yields 1-> 21
Code:
5 9 3 0
6 1 2 1
7 8 4 1
So what would it take to get to n = 50 or n = 100 or n =1000?
I have put only a very little effort into this. And I have to be AFT for a few hours. Figured that it would be an interesting challenge, either by hand, programmatically, or in theory.
Uncwilly is offline   Reply With Quote
Old 2018-08-10, 03:35   #2
WraithX
 
WraithX's Avatar
 
Mar 2006

2×35 Posts
Default

I misunderstood your "straight lines only" rule and thought you meant only horizontal and vertical lines. Once i realized you also include diagonal lines, I see how your 4x3 could get from 1->21. I found a small improvement to get from 1->24 with:
Code:
5932
6124
7810
If we treat the grid like a torus then that same group will go from 1->32.

I really like this puzzle. I think the flat x,y grid will be able to get up to around n = 2*x*y and the torus x,y grid might be able to get up to around n = 4*x*y These are just wild guesses. Hopefully someone can come up with better bounds. I'm going to try running a python program to see if I can come up with some other/better solutions.
WraithX is offline   Reply With Quote
Old 2018-08-10, 04:49   #3
axn
 
axn's Avatar
 
Jun 2003

2×23×113 Posts
Default

Quote:
Originally Posted by WraithX View Post
I misunderstood your "straight lines only" rule and thought you meant only horizontal and vertical lines. Once i realized you also include diagonal lines, I see how your 4x3 could get from 1->21. I found a small improvement to get from 1->24 with:
Code:
5932
6124
7810
If we treat the grid like a torus then that same group will go from 1->32.
You can get to 25 by just swapping 5 & 9, and 26 by swapping 6 & 8
Code:
9532
8124
7610
axn is offline   Reply With Quote
Old 2018-08-10, 22:30   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

29×349 Posts
Default

Quote:
Originally Posted by WraithX View Post
I really like this puzzle. I think the flat x,y grid will be able to get up to around n = 2*x*y and the torus x,y grid might be able to get up to around n = 4*x*y These are just wild guesses. Hopefully someone can come up with better bounds. I'm going to try running a python program to see if I can come up with some other/better solutions.
Standard word searches are not based around the torus.
Quote:
Originally Posted by axn View Post
You can get to 25 by just swapping 5 & 9, and 26 by swapping 6 & 8
Code:
9532
8124
7610
Nice innovations.

Someone had posted on FB, "like and share if you can find XXX". My thought, I wonder how big of rectangle one would need to get all of the numbers.

So to get to 30, would a 5 x 3 work? Or would a 4 x 4 be required?
Once we get to 5 x 5 the number of potential connections goes way up. And passing through the 50's will see a gain in XY, YX pairing (ie. 45 and 54 are the same, just in a different direction, same for 91 and 19).
Uncwilly is offline   Reply With Quote
Old 2018-08-11, 01:54   #5
axn
 
axn's Avatar
 
Jun 2003

2·23·113 Posts
Default

Code:
1....
41221
330..
5x3 = 34 (. to be replace by 4-9 in any order)

Code:
3043
.12.
.21.
3..3
4x4 = 43 (. to be replaced by 3,5-9 in any order)

I am assuming both of these can be improved -- these were found quickly by manual search.
axn is offline   Reply With Quote
Old 2018-08-11, 04:27   #6
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

236118 Posts
Default

I like what you did there in that last one. It pulls ahead of WraithX's prediction of n = 2*x*y by having 43 > 2*4*4. So maybe 6 x 6 might be the break through that gets all the way to 100.

Last fiddled with by Uncwilly on 2018-08-11 at 04:28
Uncwilly is offline   Reply With Quote
Old 2018-08-11, 12:03   #7
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

13×37 Posts
Default

Here is a 5x3 rectangle with score 36:
Code:
9 0 3 6 8
1 2 3 1 2
7 4 1 5 2

Genetic algorithms might perform pretty good on this kind of problem.

Last fiddled with by Till on 2018-08-11 at 12:04 Reason: data formatting
Till is offline   Reply With Quote
Old 2018-08-11, 14:28   #8
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

1E116 Posts
Default

A 5x5 square derived from axn's 4x4 with score 76:
Code:
. 0 4 3 6
5 1 2 4 6
6 2 1 9 5
0 7 8 3 5
3 5 4 6 3
The upper-left entry can be filled with any value.

And a 6x6 with score 99:
Code:
9 9 2 8 5 1
6 7 3 4 0 6
2 6 6 3 4 7
2 8 5 9 1 7
1 2 8 0 5 5
1 0 7 5 4 1

Last fiddled with by Till on 2018-08-11 at 15:08 Reason: put placeholder in upper left corner
Till is offline   Reply With Quote
Old 2018-08-11, 15:06   #9
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

13·37 Posts
Default

I found a 6x6 with score 100, derived from the 5x5 stated before:
Code:
. 7 0 6 . .
. 3 0 4 3 6
9 5 1 2 4 6
9 6 2 1 9 5
0 7 7 8 3 5
8 8 5 4 6 3

The dots can be filled with any number, hence there is still a lot of freedom. On the other hand will it be difficult to get much better because then we need many "10x" strings.
Till is offline   Reply With Quote
Old 2018-08-11, 17:00   #10
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

278916 Posts
Default

Great work!
Did you do that all by hand? I noticed that the inner square of 1's and 2's carried over. At some point rather that keeping them together, it might be that we don't care about them being so close as we have 3 or 4 of them.

The initial thread title was a play on magic squares. But, there has to be a better title for these. Sentences that have all the letters are pangrams or holoalphabetic sentences. Holonumeric squares might be a good sterile name. Compact number squares. Convonumbero squares. Getting all Latin Omnibus numeris quadratum.
Uncwilly is offline   Reply With Quote
Old 2018-08-11, 17:27   #11
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

13×37 Posts
Default

Thanks.
I wrote a little program that random-tests rectangles that contain each of "0123456789" at least once. That gave me the 5x3 solution with score 36 and the 6x6 with score 99.


The better 5x5 and 6x6 results were derived by hand. axn's 4x4 is quite ingenious I'ld say. My random test achieved no more than score 36 after >10million 4x4squares.
Till is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 06:46.


Mon Dec 6 06:46:18 UTC 2021 up 136 days, 1:15, 0 users, load averages: 1.61, 1.57, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.