mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-06-25, 18:44   #166
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

217210 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I don't know what m is or why it is needed. But couldn't you just scale the grid by a factor of m and use smaller squares?
It's a matter of formulating the problem that needs to be solved. One way is to set the rectangle with integer side m and unknown side x equal to the 4 square sums. Like I said it's not sufficient constraints for factoring. But that's the first equation. You need more to ensure integer domain solutions for x.
It is not theoretically impossible but very impractical.

Last fiddled with by a1call on 2017-06-25 at 19:03
a1call is offline   Reply With Quote
Old 2017-06-25, 19:43   #167
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22×3×181 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I don't know what m is or why it is needed. But couldn't you just scale the grid by a factor of m and use smaller squares?
Now that I think about it, that is very clever. That indeed is a valid factorization method (much simpler applied algebraically than geometrically).

21/9 -> 63/9 -> 21/3.

Of course unless the scale has a common factor grater than 1 with m, then it's not of much use.

As a measure of potential complexity and extra numbers of steps involved in geometrical solutions versus algebraical solutions, consider the solution I came up with for 5 inscribed circles in a circle here:

http://www.mersenneforum.org/showthread.php?t=21141

vs. its algebraic solution:

Code:
The trigonometric formula for the radius r1 of n equal, tangent and inscribed circles inside a larger circle of radius r2 is:
r1 = (r2 sin (180/n))/(1+sin (180/n))
Its worth pointing out that I settled to providing a link to drawing pentagons rather than including it in the instructions.

Last fiddled with by a1call on 2017-06-25 at 19:59
a1call is offline   Reply With Quote
Old 2017-06-25, 20:36   #168
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22×3×181 Posts
Default

This might be one theoretical use of the concept:


Code:
theExp = 5;\\larger integers will enlarge random n
#
\\\
primorial(n)=
  {
    my(thePrimorial=1);
    forprime(p=2,n,thePrimorial=thePrimorial*p);
    return (thePrimorial);
  }
\\\
n=nextprime(random(19^theExp ))*nextprime(random(19^theExp ))
factor(n)
##
pr= primorial(sqrtint(n));
##
{
s= n/ pr;
print("** ",numerator(s))
}
##
Code:
(16:31) gp > n=nextprime(random(19^theExp ))*nextprime(random(19^theExp ))
%10 = 5452058249203
(16:31) gp > factor(n)
%11 =
[2236807 1]

[2437429 1]

(16:31) gp > ##
  ***   last result computed in 0 ms.
(16:31) gp >
(16:31) gp > pr= primorial(sqrtint(n));
time = 7,376 ms.
(16:31) gp > ##
  ***   last result computed in 7,376 ms.
(16:31) gp > {
s= n/ pr;

print("** ",numerator(s))
}
** 2437429
(16:31) gp > ##
  ***   last result computed in 0 ms.
(16:31) gp >
a1call is offline   Reply With Quote
Old 2017-06-25, 22:06   #169
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

As a sidenote, might I suggest
Code:
n=randomprime([2,19^5])*randomprime([2,19^5]);
rather than
Code:
theExp = 5;\\larger integers will enlarge random n
n=nextprime(random(19^theExp ))*nextprime(random(19^theExp ))
?

That was you get a uniform selection* and it's a little easier to see what's going on. Also, you should probably increase the lower bound -- maybe randomprime([1e5, 3e5]) would be better.

* Consider that, with theExp = 5, 2010881 is chosen 148 times more often than 3 and 74 times more often than 2010973.
CRGreathouse is offline   Reply With Quote
Old 2017-06-25, 22:29   #170
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22×3×181 Posts
Default

Cool.
I did not know that,
Thank you.
a1call is offline   Reply With Quote
Old 2017-06-25, 23:07   #171
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

I posted a very fiddly program
Code:
rsp(len)=my(mn=10^(len-1),mx=10^len-1,p=randomprime([sqrtup(mn/2),sqrtint(mx)]),q=randomprime([ceil(mn/p),mx\p])); p*q;
earlier which, given a number of digits, finds a semiprime pq with that number of digits such that p <= q < 2p. It's not uniform but good enough for these purposes.

Last fiddled with by CRGreathouse on 2017-06-25 at 23:07
CRGreathouse is offline   Reply With Quote
Old 2017-06-25, 23:20   #172
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22×3×181 Posts
Default

My version doesn't seem to recognize sqrtup()
works fine with ceil(sqrt(mn/2)), though.
Cool code, thank you.
Adding it to my library under semiprimes.
a1call is offline   Reply With Quote
Old 2017-06-26, 00:04   #173
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by a1call View Post
My version doesn't seem to recognize sqrtup()
works fine with ceil(sqrt(mn/2)), though.
sqrtup is a function I defined to avoid the floating-point roundoff of that approach. I give the code a few times in this thread but forgot to include it with that snippet, here it is:
Code:
sqrtup(n)=n=ceil(n); if(issquare(n,&n),n,sqrtint(n)+1);
Quote:
Originally Posted by a1call View Post
Cool code, thank you.
Adding it to my library under semiprimes.
Glad I could help.

Last fiddled with by CRGreathouse on 2017-06-26 at 00:05
CRGreathouse is offline   Reply With Quote
Old 2017-06-26, 00:17   #174
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22·3·181 Posts
Default

Got it.
Thank you very much.
a1call is offline   Reply With Quote
Old 2017-06-27, 18:50   #175
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

748 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
In fairness I mentioned this on page 3 and showed how much faster it was.

So, the takeaways:
  • These numbers are really small. I wasn't able to go much higher because the methods were too slow.
  • Overhead matters a lot. My stupid method is twice as fast as Dr Sardonicus's stupid method just because mine does less work and so it spends more time searching.
  • Contrary to my expectations, the extensions helped a lot. I think that's because the algorithm I'm using for four-square representations is slow and the more checks you do inside of each one you find, the better (because each one is expensive to find).
  • It should surprise no one that all methods were much slower than trial division, which is much slower than a real method.
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

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^1 = 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
....
mahbel is offline   Reply With Quote
Old 2017-06-27, 21:40   #176
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by mahbel View Post
[/LIST]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

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^1 = 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
....
you can break down almost any partition that way though: partitions of 9:
9
8,1
7,2
7,1,1
6,3
6,2,1
6,1,1,1
5,4
5,3,1
5,2,2
5,2,1,1
5,1,1,1,1
4,5
4,4,1
4,3,2
4,3,1,1
4,2,1,1,1
4,1,1,1,1
3,6
3,5,1
3,4,2
3,4,1,1
3,3,1,1,1
3,2,1,1,1,1
3,1,1,1,1,1,1
3,3,3
3,3,2,1
3,3,1,1,1
3,2,1,1,1,1
3,1,1,1,1,1,1
...


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.
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 18:22.


Mon Nov 29 18:22:56 UTC 2021 up 129 days, 12:51, 0 users, load averages: 1.46, 1.31, 1.29

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.