mersenneforum.org The new strong (extended) factoring method using the 4-square representation of an integer.
 Register FAQ Search Today's Posts Mark Forums Read

2017-06-27, 23:34   #177
mahbel

Feb 2017
Kitchener, Ontario

22×3×5 Posts

Quote:
 Originally Posted by science_man_88 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.

2017-06-28, 00:30   #178
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 Originally Posted by mahbel 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.

2017-06-28, 12:03   #179
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by science_man_88 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.

2017-06-28, 12:35   #180
Dr Sardonicus

Feb 2017
Nowhere

10011111111002 Posts

Quote:
 Originally Posted by mahbel 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

2017-06-28, 13:13   #181
CRGreathouse

Aug 2006

135338 Posts

Quote:
 Originally Posted by mahbel 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 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?

2017-06-28, 13:25   #182
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2017-06-28, 13:36   #183
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by mahbel 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

2017-06-28, 19:46   #184
mahbel

Feb 2017
Kitchener, Ontario

22×3×5 Posts

Quote:
 Originally Posted by science_man_88 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.

2017-06-28, 20:41   #185
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by mahbel 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 ...

2017-06-29, 12:21   #186
mahbel

Feb 2017
Kitchener, Ontario

1111002 Posts

Quote:
 Originally Posted by science_man_88 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

2017-06-29, 12:36   #187
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by mahbel 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 1250 2021-10-01 12:53 3.14159 Factoring 233 2011-05-15 18:50 ET_ Miscellaneous Math 40 2010-06-06 12:55 1260 Miscellaneous Math 46 2010-05-31 17:37 kpatsak Math 4 2007-10-29 17:53

All times are UTC. The time now is 17:31.

Mon Nov 29 17:31:07 UTC 2021 up 129 days, 12 hrs, 0 users, load averages: 1.16, 1.35, 1.38