Help with series convergence in Fermat method of factoring

[CRGreathouse]

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

[LaurV]

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.

[science_man_88]

Originally Posted by EdH

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.

[EdH]

Originally Posted by CRGreathouse

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.

Originally Posted by CRGreathouse

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!

Originally Posted by LaurV

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!

Originally Posted by science_man_88

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...

[CRGreathouse]

Originally Posted by EdH

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?

[EdH]

Originally Posted by CRGreathouse

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 (52²). The difference between the first square above and the composite is 77. The first perfect square below 77 is 64 (8²).

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 (53²) is 105, the difference between 2809 and 2916 (54²) 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!

[mgb]

Originally Posted by EdH

-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 X² is. That is, you are looking for Y².

The equation for Y² where n + Y² = X² is-

x² + bx + c = Y² where

b = 2m and c = m² - 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.

[hal1se]

Originally Posted by CRGreathouse

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?