mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-06-24, 19:30   #144
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

6010 Posts
Default tiling an 11x11 square with squares from the 4-sq rep (10,4,2,1)

I made the tiling of an 11x11 square. I started with the 4-sq rep (10,4,2,1). Now using combinations of non-squares, we can find a factor by adding 2 terms 10+1=11. In this picture, it will be shown that one can tile the whole 11x11 square with squares derived from the 4-sq rep (10,4,2,1).

One has to remember that 11=5+5+1, 3+3+1+1+1+1+1=11, 5+4+2=11 and 5+4+2=11 and 2+2+2+2+3=11.

So 10+1=11 becomes in the final picture 5+5+1=11.
Attached Thumbnails
Click image for larger version

Name:	tiling_11_by_11.JPG
Views:	86
Size:	719.5 KB
ID:	16320  
mahbel is offline   Reply With Quote
Old 2017-06-24, 19:52   #145
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by mahbel View Post
I don't know if the algorithm is faster than factorization. I only know that such an algorithm exists. It is based on solving quadratic equations and finding values of a parameter k that makes the discriminant a perfect square. I suppose for some numbers, solutions can be found quickly and for some other numbers not so quickly.

The algorithm is described here.

https://math.stackexchange.com/quest...that-add-up-to
Ah. This requires solving a diophantine quadratic, in particular the hyperbolic case. I think of solving diophantine equations as hard; I guess you could look into this particular case and see if it's easier than the general one. There are known algorithms, and I know PARI/GP implements fast versions of those algorithms (but they're not very user-friendly).

Quote:
Originally Posted by mahbel View Post
To answer your second question, there is no quick way to tell if a number does not admit a representation as a sum of two squares. To find out, one has to check every value of the parameter k in the discriminant until we run out of values to check before we can say the number does not admit a representation as a sum of two squares. And this may take a long time, maybe even longer than factorization.
Right, if you do it this way it would take a long time, definitely longer than factorization. When I suggested factorization it was because it was a good/fast approach.
CRGreathouse is offline   Reply With Quote
Old 2017-06-24, 19:54   #146
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by mahbel View Post
The answer Will Jagy gave in the thread on the statckexchange site proved that writing 2N as a sum of two squares is equivalent to writing N as a sum of two squares. And he is one of the most knowledgeable mathematician I know. He called it a bijection between the two methods.
Yes, and you can understand that claim in light of the factorization characterization I gave.
CRGreathouse is offline   Reply With Quote
Old 2017-06-24, 19:55   #147
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by mahbel View Post
I made the tiling of an 11x11 square. I started with the 4-sq rep (10,4,2,1). Now using combinations of non-squares, we can find a factor by adding 2 terms 10+1=11. In this picture, it will be shown that one can tile the whole 11x11 square with squares derived from the 4-sq rep (10,4,2,1).

One has to remember that 11=5+5+1, 3+3+1+1+1+1+1=11, 5+4+2=11 and 5+4+2=11 and 2+2+2+2+3=11.

So 10+1=11 becomes in the final picture 5+5+1=11.
That's very pretty. I'm not at all sure how I would use this for factorization, though.
CRGreathouse is offline   Reply With Quote
Old 2017-06-24, 20:07   #148
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

Quote:
Originally Posted by mahbel View Post
I made the tiling of an 11x11 square. I started with the 4-sq rep (10,4,2,1). Now using combinations of non-squares, we can find a factor by adding 2 terms 10+1=11. In this picture, it will be shown that one can tile the whole 11x11 square with squares derived from the 4-sq rep (10,4,2,1).

One has to remember that 11=5+5+1, 3+3+1+1+1+1+1=11, 5+4+2=11 and 5+4+2=11 and 2+2+2+2+3=11.

So 10+1=11 becomes in the final picture 5+5+1=11.
Brilliant!

And here is my picture for 13^2=10^2+7^2+4^2+2^2.
In fact it works for any set of squares. We will just cut them all into 1x1 pieces.
One simply has to remember that 7=1+1+1+1+1+1+1, 4=1+1+1+1, and 2=1+1.
Elementary, Watson!
Attached Thumbnails
Click image for larger version

Name:	13^2=10^2+7^2+4^2+2^2.png
Views:	76
Size:	4.0 KB
ID:	16321  
Batalov is offline   Reply With Quote
Old 2017-06-24, 20:12   #149
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
That's very pretty. I'm not at all sure how I would use this for factorization, though.
I somewhat understand, after all I linked to the numberphile video. But, I also get the point, that factoring a number with known factors, allows you to plan ahead. This allows you to make sure you use squares that fit such that their side lengths add to a known factor. The problem is, in a general factorization, baring any knowledge of the type of side length we will be dealing with ( aka factor types like 2kp+1 for mersennes), we can't say which sums will give us a factor so we must try basically all of them. edit: Also the problem of n^2 = n^2*1^2 shows up like Batalov talked about.

Last fiddled with by science_man_88 on 2017-06-24 at 20:30
science_man_88 is offline   Reply With Quote
Old 2017-06-24, 20:34   #150
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22·3·5 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
That's very pretty. I'm not at all sure how I would use this for factorization, though.
It is simply a confirmation that using combinations of non-squares (a,b,c,d) to get a factor is justified.

In the original 4-sq rep used, (10,4,2,1), by just adding 10+1=11, we get a factor. But of course we cannot tile with this rep as is. But if we expand 10^2=(5,5,5,5) and 4^2+2^2=3^3+3^2+1+1, then we would be able to tile the whole square. Each side will give the same factor.
mahbel is offline   Reply With Quote
Old 2017-06-24, 20:46   #151
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

748 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Yes, and you can understand that claim in light of the factorization characterization I gave.
Yes.
mahbel is offline   Reply With Quote
Old 2017-06-24, 21:16   #152
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

215210 Posts
Default

Quote:
Originally Posted by mahbel View Post
I made the tiling of an 11x11 square. I started with the 4-sq rep (10,4,2,1). Now using combinations of non-squares, we can find a factor by adding 2 terms 10+1=11. In this picture, it will be shown that one can tile the whole 11x11 square with squares derived from the 4-sq rep (10,4,2,1).

One has to remember that 11=5+5+1, 3+3+1+1+1+1+1=11, 5+4+2=11 and 5+4+2=11 and 2+2+2+2+3=11.

So 10+1=11 becomes in the final picture 5+5+1=11.
I actually do see a geometric algorithm in there.
Here is my 2 cents, FWIW.
It has absolutely nothing to do with 4 squares and there is no justification to start from 5.
I just applied the geometric tiling algorithm and started with 2x6^2
I ended up tiling a 14x13 rectangle.
I think if one starts from N/2 rounded down and works its way down to N/sqrt(N), then he will find a deterministic factor if any. I also think it will be very very slow.
But if I am missing something, it won't be the first time.

Last fiddled with by a1call on 2017-06-24 at 21:20
a1call is offline   Reply With Quote
Old 2017-06-24, 21:43   #153
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by a1call View Post
I actually do see a geometric algorithm in there.
Here is my 2 cents, FWIW.
It has absolutely nothing to do with 4 squares and there is no justification to start from 5.
I just applied the geometric tiling algorithm and started with 2x6^2
I ended up tiling a 14x13 rectangle.
I think if one starts from N/2 rounded down and works its way down to N/sqrt(N), then he will find a deterministic factor if any. I also think it will be very very slow.
But if I am missing something, it won't be the first time.
If you allow using as many 1x1 squares as you need, this is just a variant of trial division. If not, it's not clear to me that you will find a factorization even if there is one -- maybe there is a factorization but no associated tiling. But I wasn't thinking of something this brute force when I suggested looking at it geometrically. I know that there are parameterized tilings and conceivably these could give factorizations for an appropriate class of integers. Maybe they would be very very thin, and so not useful, or maybe only somewhat thin and so useful at least as a curiosity. If they were fully general, of course, you'd get a normal factorization method.
CRGreathouse is offline   Reply With Quote
Old 2017-06-24, 21:49   #154
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

116178 Posts
Default

Quote:
Originally Posted by axn View Post
Before we proceed further, what is the theoretical justification that it has to be squares?
Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that

a^2 + b^2 + c^2 + d^2 = N exactly.

As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead and form the sums of some or all of a, b, c, d, a^2, b^2, c^2, and d^2, and take the gcd with N. (There are 127 nonempty sums.)

I hypothesize that, there being so many possibilities, the chances are good that any factor of N under 100 will show up fairly quickly. I tried this idea with N = 1457 = 31*47, and the results were better than I expected. Even though a^2 + b^2 + c^2 + d^2 never hit N right on the nose, I still got at least one of the 15 sums of a, b, c, and d alone having a common factor with N in 6 of 8 tries.

If anyone would care to have a go at my examples N = 77, 1457, 3901, 4661, 6557, 7597, 8549, and 9869 using this approach, have at them!

I cheerfully proclaim that this approach really is nothing more than blazing away with a scattergun, in hopes that some of the buckshot will hit. The advantage over the OP's idea is, reloading is a whole lot quicker
;-)
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Sierpinski/Riesel-like problem sweety439 sweety439 1250 2021-10-01 12:53
Another factoring method rides the bus 3.14159 Factoring 233 2011-05-15 18:50
Square numbers and binary representation ET_ Miscellaneous Math 40 2010-06-06 12:55
Is this a feasible factoring method? 1260 Miscellaneous Math 46 2010-05-31 17:37
Representation of integer as sum of squares kpatsak Math 4 2007-10-29 17:53

All times are UTC. The time now is 20:56.


Tue Oct 26 20:56:52 UTC 2021 up 95 days, 15:25, 0 users, load averages: 1.31, 1.18, 1.24

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.