mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-06-27, 23:34   #177
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22×3×5 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
you can break down almost any partition that way though: partitions of 9:

all the red are partitions of another partition. some of these are also duplicates of earlier ones 3,4,2 and 4,3,2 and 2,3,4 for example ( there's actually 6 possible ways to rearrange these but that's also why you can cut the work back searching for the square sums because there are 16 with sign changes, each having 24 orderings.
It simply means that we only need to find the first 4-sq rep, then expand its squares into sum of 4 squares and then use these expansions to form combinations of square and non-squares as done before to find the factor.
mahbel is offline   Reply With Quote
Old 2017-06-28, 00:30   #178
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by mahbel View Post
It simply means that we only need to find the first 4-sq rep, then expand its squares into sum of 4 squares and then use these expansions to form combinations of square and non-squares as done before to find the factor.
It also means, that looking for the partitions where all the number's are the same, is enough to get a factor though.
science_man_88 is offline   Reply With Quote
Old 2017-06-28, 12:03   #179
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
It also means, that looking for the partitions where all the number's are the same, is enough to get a factor though.
okay not quite turns out you also need to check it's not 1 or N for a non trivial factor.
science_man_88 is offline   Reply With Quote
Old 2017-06-28, 12:35   #180
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×32×139 Posts
Default

Quote:
Originally Posted by mahbel View Post
It turned out that one 4-sq representation can be transformed into another simply by expanding the squares in the first one and re-arranging them to create new 4-sq representations. It can be shown that for N=7*13=91, the first 4-sq rep (5,5,5,4) can be transformed into any other representation.

And in fact, if one used the expanded squares of a given representation, one can find more factors. Take the example of the first 4-sq rep (5,5,5,4).
5^2=4^2+2^2+2^2+1^2
5^2=4^2+2^2+2^2+1^2
5^2=4^2+2^2+2^2+1^2
4^2=2^2+2^2+2^2+2^2....
So, how does this transform one 4-square representation into another? And where does this process stop, short of all the squares being equal to 0 or 1?

Instead of looking at summands n^2, why not use summands 2^n instead? I absolutely guarantee, if N is odd and composite, and you take

1, 2, 4, ... 2^r, with 2^r < sqrt(N) < 2^(r+1), so r < log(N)/(2*log(2)),

then at least one of the sums of these powers of 2 will be equal to a factor of N! I can even spot you that one of the summands must be equal to 1!

Last fiddled with by Dr Sardonicus on 2017-06-28 at 12:39
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-28, 13:13   #181
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by mahbel View Post
It turned out that one 4-sq representation can be transformed into another simply by expanding the squares in the first one and re-arranging them to create new 4-sq representations. It can be shown that for N=7*13=91, the first 4-sq rep (5,5,5,4) can be transformed into any other representation.
Quote:
Originally Posted by mahbel View Post
It simply means that we only need to find the first 4-sq rep, then expand its squares into sum of 4 squares and then use these expansions to form combinations of square and non-squares as done before to find the factor.
I'm concerned we're getting tricked by using small numbers again. Here's a random semiprime and the first 4-square partition I found: 815181927142781578628738664212206467553690877685194559413249 = 902874258766292206129956425802^2 + 255400237710160^2 + 19610779^2 + 5938098^2. Could you expand its sum of four squares into a few others to show the process?
CRGreathouse is offline   Reply With Quote
Old 2017-06-28, 13:25   #182
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22×3×5 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I'm concerned we're getting tricked by using small numbers again. Here's a random semiprime and the first 4-square partition I found: 815181927142781578628738664212206467553690877685194559413249 = 902874258766292206129956425802^2 + 255400237710160^2 + 19610779^2 + 5938098^2. Could you expand its sum of four squares into a few others to show the process?
I cannot do the calculations by hand.
Because we are dealing with a big number, the squares (a,b,c,d) themselves will have many 4-sq reps. The idea of my comment is to limit the search for factors to 4 sub expansions, that is the 1st 4-sq rep of a,b,c,d.
mahbel is offline   Reply With Quote
Old 2017-06-28, 13:36   #183
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by mahbel View Post
I cannot do the calculations by hand.
Because we are dealing with a big number, the squares (a,b,c,d) themselves will have many 4-sq reps. The idea of my comment is to limit the search for factors to 4 sub expansions, that is the 1st 4-sq rep of a,b,c,d.
can't divide those big number's by 2 ? after all (2a)^2= 4(a^2) edit :to prove what you said, most of what you have to do is prove that, any of the squares, once expanded form a lower pair of a Pythagorean triple.

Last fiddled with by science_man_88 on 2017-06-28 at 13:50
science_man_88 is offline   Reply With Quote
Old 2017-06-28, 19:46   #184
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22·3·5 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
to prove what you said, most of what you have to do is prove that, any of the squares, once expanded form a lower pair of a Pythagorean triple.
not necessarily a lower pair of Pythagorean triple. 8^2=4^2+4^2+4^2+4^2 but 4^2=2^2+2^2+2^2+2^2. We may get some Pythagorean triplets but not as a general rule.
mahbel is offline   Reply With Quote
Old 2017-06-28, 20:41   #185
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by mahbel View Post
not necessarily a lower pair of Pythagorean triple. 8^2=4^2+4^2+4^2+4^2 but 4^2=2^2+2^2+2^2+2^2. We may get some Pythagorean triplets but not as a general rule.
then breaking them down doesn't help in general ...
science_man_88 is offline   Reply With Quote
Old 2017-06-29, 12:21   #186
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22·3·5 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
then breaking them down doesn't help in general ...
It does. Expanding the squares of a given 4-sq rep helps as a general rule. Look at the simple example of N=7*13=91, the first 4-sq rep is (5,5,5,4). There is not a single combination of squares that gives a factor. But there is at least one combination of non-square that gives a factor, 5+5+4=14=2*7. There is also a mixed combination that gives a factor, 5^2 + 5 + 5 +4 = 39 =3*13.

Now look at what happens when we expand the squares (5,5,5,4).

5^2=(4,2,2,1)
4^2=(2,2,2,2)

combining these squares, it is easy to see that:

4^2 + 2^2 + 1^2 = 21 = 3*7
2^2 + 2^2 + 2^2 + 1^2 = 13
2^2 + 1^2 + 1^2 + 1^2 = 7
4^2 + 2^2 + 2^2 + 2^2 = 28 = 4*7
4^2 + 4^2 + 1^2 + 1^2 + 1^2 = 35 = 5*7
....
What we don't know is how many levels of expansions are needed. If we consider the original 4-sq rep at the top of a pyramid, the successive expansions of squares of that original 4-sq rep will take us all the way down to a^2=1^2+1^2+...+1^2 and the same for b,c,d.

My guess is that it is very hard to prove that the number of expansions of individual squares of the original 4-sq rep is much smaller than the one required if one has to go all the way down to a^2=1^2+1^2+...+1^2. The math is not simple and I don't think the answer is the same for all numbers.

Last fiddled with by mahbel on 2017-06-29 at 12:23 Reason: fix a typo
mahbel is offline   Reply With Quote
Old 2017-06-29, 12:36   #187
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by mahbel View Post
It does. Expanding the squares of a given 4-sq rep helps as a general rule. Look at the simple example of N=7*13=91, the first 4-sq rep is (5,5,5,4). There is not a single combination of squares that gives a factor. But there is at least one combination of non-square that gives a factor, 5+5+4=14=2*7. There is also a mixed combination that gives a factor, 5^2 + 5 + 5 +4 = 39 =3*13.

Now look at what happens when we expand the squares (5,5,5,4).

5^2=(4,2,2,1)
4^2=(2,2,2,2)

combining these squares, it is easy to see that:

4^2 + 2^2 + 1^2 = 21 = 3*7
2^2 + 2^2 + 2^2 + 1^2 = 13
2^2 + 1^2 + 1^2 + 1^2 = 7
4^2 + 2^2 + 2^2 + 2^2 = 28 = 4*7
4^2 + 4^2 + 1^2 + 1^2 + 1^2 = 35 = 5*7
....
What we don't know is how many levels of expansions are needed. If we consider the original 4-sq rep at the top of a pyramid, the successive expansions of squares of that original 4-sq rep will take us all the way down to a^2=1^2+1^2+...+1^2 and the same for b,c,d.

My guess is that it is very hard to prove that the number of expansions of individual squares of the original 4-sq rep is much smaller than the one required if one has to go all the way down to a^2=1^2+1^2+...+1^2. The math is not simple and I don't think the answer is the same for all numbers.
you said 4 square representations to another not a mixed representation. to get back squares you need a sum of squares that sum to a square the simplest form is a pythagorean triple.

so 1^2+3^2+4^2+5^2 =1^2+5^2+5^2+0^2 because 3^2+4^2=5^2.
science_man_88 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 05:22.


Mon Oct 25 05:22:40 UTC 2021 up 93 days, 23:51, 0 users, load averages: 1.42, 1.25, 1.13

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.