mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2017-10-03, 05:54   #45
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

174916 Posts
Default

Sidenote: In this case you seem to be looking at the sum of a linear function, which is of course quadratic. If you want to know when two quadratics will be equal you may find this handy:
https://www.alpertron.com.ar/QUAD.HTM
CRGreathouse is offline   Reply With Quote
Old 2017-10-03, 07:46   #46
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100011101100002 Posts
Default

Obviously, you have a sum of two arithmetic progressions, which you equate and then you have to solve a diophantine equation, which is equivalent with factorization.

On your particular case where you sum odd numbers, this is the difference of squares factoring method. When you sum odd numbers to n, you get a square number. Summing them from m to n is just a difference of two squares.
LaurV is offline   Reply With Quote
Old 2017-10-03, 11:11   #47
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by EdH View Post
I'd like to renew this thread just long enough to revisit the following. I've probably missed something in my studies, or maybe this just isn't doable. Anyway:

I'm trying to figure out how to calculate where the coincidence of two series will happen. The series grow by a known progression. I know the starting integer and the progression for each series, but I can't figure out a way to calculate coincidence. Is that because it can't be done, or because I don't know enough?

series1 is 2704+105+107+109+111...
series2 is 2691+17+19+21+23+25...

series1 will equal 2916 at 2705+105+107
series2 will equal 2916 at 2691+17+19+21+23+25+27+29+31+33

Is there a way to calculate the value 2916 directly, if it is unknown?

IOW, can 2705+105+107... = 2691+17+19... be calculated instead of stepping through each to coincidence?

Obviously, I'll want to be able to do this with much larger integers, but these small ones illustrate my query.

Thanks for any replies...
the first sum is odd every even iteration and even every odd iteration from what's shown, the second one is odd every odd iteration and even every even iteration so it's only if an odd iteration of one equals an even iteration of the other that you can show they can equal at any point maybe that would speed things up. you can also make a sequence that sum of the differences from one to the other.

Last fiddled with by science_man_88 on 2017-10-03 at 11:14
science_man_88 is offline   Reply With Quote
Old 2017-10-03, 14:55   #48
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

33×131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
If you can compute them term-by-term, and if each summand is a positive integer, it's not hard.
Unfortunately, I'm trying to stay away from an advance and check solution, since this will take way too much time for anything over a few digits. I've done some other versions of advance and check and the solution won't come back within hours for anything in the 20 digit region.

Quote:
Originally Posted by CRGreathouse View Post
Sidenote: In this case you seem to be looking at the sum of a linear function, which is of course quadratic. If you want to know when two quadratics will be equal you may find this handy:
https://www.alpertron.com.ar/QUAD.HTM
Now, this is probably where I should be looking! I'm envisioning the two series as two intersecting graphs and if I had big enough paper, I could simply draw the two and study the intersection. I will look at this page in depth. Thanks!
Quote:
Originally Posted by LaurV View Post
Obviously, you have a sum of two arithmetic progressions, which you equate and then you have to solve a diophantine equation, which is equivalent with factorization.

On your particular case where you sum odd numbers, this is the difference of squares factoring method. When you sum odd numbers to n, you get a square number. Summing them from m to n is just a difference of two squares.
My problem, as I see it, is trying to create an equation from the two series. I can't figure out what each series would be in function form. I will be looking more closely at the page CRGreathouse suggested, which includes Diophantine as well as quadratic sections. Thanks!
Quote:
Originally Posted by science_man_88 View Post
the first sum is odd every even iteration and even every odd iteration from what's shown, the second one is odd every odd iteration and even every even iteration so it's only if an odd iteration of one equals an even iteration of the other that you can show they can equal at any point maybe that would speed things up. you can also make a sequence that sum of the differences from one to the other.
The odd and even attributes are just coincidence for this example. I still need to stay away from advance and check methods due to the time involved in every iteration.

Thanks to all for your help in this. Off to study...
EdH is offline   Reply With Quote
Old 2017-10-03, 15:36   #49
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135118 Posts
Default

Quote:
Originally Posted by EdH View Post
Unfortunately, I'm trying to stay away from an advance and check solution, since this will take way too much time for anything over a few digits. I've done some other versions of advance and check and the solution won't come back within hours for anything in the 20 digit region.
In that case we'll need to know more about the series themselves. Will the terms, as in your example, be in arithmetic progression, so that the partial sums are quadratic?
CRGreathouse is offline   Reply With Quote
Old 2017-10-03, 18:23   #50
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

33×131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
In that case we'll need to know more about the series themselves. Will the terms, as in your example, be in arithmetic progression, so that the partial sums are quadratic?
The series are the advancements by consecutive perfect squares. In the example given, the composite is 2627 and the first perfect square above it is 2704 (522). The difference between the first square above and the composite is 77. The first perfect square below 77 is 64 (82).

The high sequence is made up of the first square, 2704 and each sequential square upward. These are derived by adding the differences between each, which is a progression that increases by 2 for each step. The difference between 2704 and 2809 (532) is 105, the difference between 2809 and 2916 (542) is 107, etc.

The low sequence is similar in that it uses sequential squares as well, but is offset by the composite. In this case, 2627+64 gives us the starting value of 2691. The series continues by adding the perfect square differences from 64 upward: 17, 19, 21, 23, etc.

The intersection of the two series will be the value of the high square needed to factor 2627. In this case it is reached rather quickly at 2916.

The low series has no more interest after is has intersected with the high series to provide the value 2691. 2691-2627=64. The fact that this was the original low square is coincidental for this sample. However, we now have the two squares needed to factor 2627.

I have programmatically stepped and checked through progressions one element at a time to look for this coincidence and stepped through the high series only, checking for a difference that is a perfect square, (as suggested by fivemack, earlier). Both are exceptionally slow. So now I'm looking again at a way to calculate directly the intersection.

I'm sure someone has studied and tossed this at some time in the past, but I'd like to visit it myself for a bit.

Thanks much!
EdH is offline   Reply With Quote
Old 2019-07-19, 21:33   #51
mgb
 
"Michael"
Aug 2006
Usually at home

24·5 Posts
Default

Quote:
Originally Posted by EdH View Post

-find the closest squares below and above comp (hsq1 and hsq2, respectively)

-find the difference between hsq1 and hsq2 (hsqdiff)

-find the difference between hsq2 and comp (cdiff)

-find the closest two squares below and above cdiff (lsq1 and lsq2, respectively)

-find the difference between lsq1 and lsq2 (lsqdiff)

-add comp to lsq1 (clsq)
This is an old thread but it is like something I was looking at some years back. If I understand you correctly you are looking for an equation that will tell how far above the composite number X2 is. That is, you are looking for Y2.

The equation for Y2 where n + Y2 = X2 is-

x2 + bx + c = Y2 where

b = 2m and c = m2 - n

m = ceil(sqrt(n))

I looked at this equation but it is not very useful as x can be very large. It is only marginally better than Fermat's Method which is very slow for large Y^2.

Last fiddled with by mgb on 2019-07-19 at 21:35
mgb is offline   Reply With Quote
Old 2019-07-21, 14:35   #52
hal1se
 
Jul 2018

3·13 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Sidenote: In this case you seem to be looking at the sum of a linear function, which is of course quadratic. If you want to know when two quadratics will be equal you may find this handy:
https://www.alpertron.com.ar/QUAD.HTM
3*(10**22+117)**2-5*(10**22+117)*(10**22+193)+7*(10**22+193)**2-11*(10**22+117)+13*(10**22+193)-5*10**44-1856*10**22-190127
=0
so: x=(10**22+117) and y=(10**22+193) an integer solve.

https://www.alpertron.com.ar/QUAD.HTM
a=3
b=-5
c=7
d=-11
e=13
f=-5*10**44-1856*10**22-190127
please click for mouse or finger for touch-plate: 'solve' button:
112 different solve only 1 second, thank you dario, good work!

but if digit > 5e2 then need many time, for example:


101*(10**776+1777)**2-103*(10**776+1777)*(10**776+2037)+107*(10**776+2037)**2-109*(10**776+1777)+127*(10**776+2037)-105*10**1552-402048*10**776-390143971
=0
so: x=(10**776+1777) and y=(10**776+2037) an integer solve.

a=101
b=-103
c=107
d=-109
e=127
f=-105*10**1552-402048*10**776-390143971

a few hours, not any result.

question: how can we solve 1e16 times faster?

Last fiddled with by hal1se on 2019-07-21 at 14:39
hal1se is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
radius of convergence of a complex power series wildrabbitt Math 3 2016-08-16 08:38
Modification of Fermat's method rdotson Miscellaneous Math 0 2007-07-27 10:32
Elliptic Curve Method factoring - Fermat numbers philmoore Math 131 2006-12-18 06:27
Fermat's factoring method with Gauss's inprovement Carlos Programming 0 2005-09-11 12:50
Convergence of infinite series LoKI.GuZ Math 10 2004-11-28 03:07

All times are UTC. The time now is 22:32.

Sun Jan 17 22:32:38 UTC 2021 up 45 days, 18:43, 0 users, load averages: 1.53, 1.62, 1.65

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.