largest n such that n^2+1 has prime factors within a set

[fivemack]

To find Machin-like formulae for pi, I want to find sets of N where N^2+1 has only small prime factors. Tangentially, it would be nice to have a proof that, for example, n=485298 is the largest number where n^2+1 has no prime factor greater than 53.

(asking the same question about n^2-1 gives you combinations of hyperbolic-arc-cotangents which sum to the logarithms of small primes, which combined with efficient series-summing tools give quite good expressions for said logarithms - I've used y-cruncher to get ten billion digits of log(17) without difficulty)

And I've not the faintest clue where to start for this sort of question.

(annoyingly, y-cruncher has quite a large per-term overhead, so getting faster convergence for the individual arctangents doesn't win if you have to sum more terms; so

? lindep([Pi/4,atan(1/485298),atan(1/85353),atan(1/44179),atan(1/34208),atan(1/6118),atan(1/2943),atan(1/1772),atan(1/931)])
%64 = [1, 183, -215, -71, 295, -68, -163, -525, -398]~

? lindep([Pi/4,atan(1/485298),atan(1/330182),atan(1/114669),atan(1/85353),atan(1/44179),atan(1/34208),atan(1/12943),atan(1/9466),atan(1/5257)])
%80 = [1, -808, -1389, -1484, -2097, -2021, -1850, -1950, 398, -2805]~

isn't actually useful)

[R. Gerbicz]

Originally Posted by fivemack

To find Machin-like formulae for pi, I want to find sets of N where N^2+1 has only small prime factors. Tangentially, it would be nice to have a proof that, for example, n=485298 is the largest number where n^2+1 has no prime factor greater than 53.

See: http://oeis.org/A185389 (somewhere there could be a longer computed list also).
This problem is solvable by https://en.wikipedia.org/wiki/St%C3%B8rmer%27s_theorem using a Pell type equation, where on the right side there is a -1 not 1.

[R. Gerbicz]

See also for lots of big arctan formulas: http://www.machination.eclipse.co.uk/FSChecking.html
(last update was at 2013)

[Batalov]

Originally Posted by fivemack

To find Machin-like formulae for pi, I want to find sets of N where N^2+1 has only small prime factors. Tangentially, ...

Ah, it brings so many childhood memories. The year was 1980 and I thought it was interesting to compute many digits of π. Because I was only in 8^th grade, my first implementation was based on \(6 \ atan {1 \over \sqrt 3}\). believe it or not; and it worked of course with a proper implementation of a long \(\sqrt 3\), but was relatively slow but I probably got 10,000 digits or so. Only then I learned form an encyclopedia about Machin's \(4 ( 4 \ atan {1 \over 5} - atan {1 \over 239})\) (imagine the world without internet, heh?), and I remember how I could not believe my eyes and then checked that it was actually true (use \(tan\) of both sides, and \(tan\) of a sum of angles repeatedly), and spent some time searching for better variants but my foundation was too weak to make any progress except for brute force. I did get 100,000 decimal digits on BESM-6's using Algol code that my father ran at work at the Nuclear Center as his own.

Ah memories, memories...

I remember that I submitted that computation to a school informatics (which was just beginning in the USSR) conference -- and went on to present it in my first talk in my life in 10^th grade - and the other viral problem I learned from a talk next to mine was the 'couch problem' where another kid was just cutting pieces from a digital rectangle, and he didn't get much far but he knew (and put it in his talk) at that time the best known answer of \(S = {\pi \over 2} + {2 \over \pi}\) .and I remember being able to get to that answer analytically because at that time I already knew derivatives and some trigonometry.

[fivemack]

Originally Posted by R. Gerbicz

See: http://oeis.org/A185389 (somewhere there could be a longer computed list also).
This problem is solvable by https://en.wikipedia.org/wiki/St%C3%B8rmer%27s_theorem using a Pell type equation, where on the right side there is a -1 not 1.

I'm not convinced that reducing it to 3^#S continued-fraction calculations is all that much of a reduction, but I suppose it's at least conclusive; Arndt has a reasonable efficient sieving process.

Some of the example Machin formulae on Wikipedia clearly use a one-large-prime method which I can't find a very good description for - I've added some paragraphs to make the examples on https://en.wikipedia.org/wiki/Machin-like_formula a bit less unmotivated.

[LaurV]

Originally Posted by Batalov

I was only in 8^th grade

About that age (a bit younger actually), one colleague of mine and me, after we learned from the teacher that 22/7 is a "good" approximation of \(\pi\) (known to the old Greeks too, of course), we started a "quest" to find better approximations, by increasing the denominator little by little and looking for a "suitable" numerator. No computers, all on paper, and with "pocket" calculators (which also, were kind of huge and expensive toys at the time, we call them pocket today, but in those times they were not called so, and you needed a backpack to carry them, but well... both our fathers had some accounting-related jobs...). We did this "research" for few weeks, actually, and we found few "better" approximations, of which we were very proud, and almost ready to show them to the teacher, when we realized suddenly that you can get more accurate approximations, in fact as accurate as you want, just by writing first n digits of \(\pi\) over the corresponding power of 10, and reducing the fraction.

This is not a joke, haha, we were soooooooo disappointed!

[fivemack]

It's absolutely obvious in retrospect, but, looking at the results of a match-up-large-primes run, if we have t^2+1=pq then (t+kq)^2+1 will also be divisible by q; and we may occasionally be lucky enough for (t+kq)^2+1 to have only small prime factors other than q.

eg t=18514 has t^2+1=29*11819593 and (t+11819593)^2+1/11819593 is divisible only by 2,5,13,17,29,37, so we can use 18514 and 11838107 instead of 29.

Otherwise the large prime approach isn't all that fertile: p=137593 is the largest to appear twice as the largest factor of an otherwise-17-smooth n^2+1 for n<10^7 (n=1173 and 3853777) ; p=68761153 (n=18542 and 343824307) for 37-smooth and n<10^9

[R. Gerbicz]

Don't know why not use this colossal 57 terms(!) arctan formula what I've found, its efficiency isn't competing with Chudnovsky, but using a bunch of computers we could get the result quicker in Wall time, since all terms can be computed paralel, and using num=57 arctan terms we can get the final sum basically using only O(log(num)) big number additions time (and multiplying by a "small" constant integer in c[]).
For the smallest term in the sum(arctan(n)) we have n>10^20, so we get more than 20 digits per term, better than Chudnovsky.

c=[212346171621984379202607910, -141986132978022176645261831, -19188947083479808676847750, 72976183437824305758327029, -90487680380658315708343594, 311666636439147152580655021, 164886394092602675087156920, -277675188573061374603700591, -328918225746279750915200446, -115228975332701852008106265, 91695937787306382534509492, 274816818440262075651640693, -15278882553455239903148046, 12345819849357697383382739, -157487043779043149246827005, 165649173043654388123361981, 268335731435818979971293832, -74376668880349669845919200, 136746152203763097091123740, -106971635007532827887780437, -105558968251925687253287026, -82410840215405324255866021, 296511073341938960924412299, 79414242640647747520579196, 26575505338669030526976157, 42582496871221199838103045, -431056435239179795449215, 322897940072599977312538725, -5058363070279926676095997, 138150568339123858964501887, -100697699225584221681812015, -40360165609976142590233256, -32168480347955895535959243, -265774660195351767787225477, -19927028999571156486476849, -9604760200607125790956233, -388197118646979923787984357, -342841339813260618645453450, 178967052427653826777184469, -243278199242825683334544770, -32735042905672245875593049, 380865428210048809909621749, -215830479721667949495349715, 4859860087340886670720953, -306797318475862261176909614, 253850710497913248888215152, 99683692694159392561113651, 171658379893183050731039940, -89191773347130083621036329, 172802843689931488647278961, -96455659594184508250880480, 107781332940660320060027780, 195623057567176555762442409, -82697175828995156518216025, 8171045079609761562016517, 35001730194790928786362252, -28720454810100608397545222];

t = [100706129803452075294, 114063843547135341423, 117387028264098620557, 118182626635495860199, 120422248000399031137, 120870463680930344868, 120927259045345571307, 121843699825114397177, 125275271043850344818, 144552427347806978193, 151179894086004836582, 155531320434402458222, 171268442677083970343, 186312414964043780693, 200597192291437604193, 229771399727574656128, 242114657461222775367, 242526457156343868609, 252241001866777989537, 276914859479857813947, 279268215504325418912, 293274837014756552545, 306254909186162917405, 311286554505870488322, 321507762595941798843, 395467645802520991318, 397699150117042862902, 400464045964625262913, 408987081828419988057, 424370650490416068993, 431899278472593106531, 440044425799491348789, 503324067165721943132, 571415097863763305482, 647982671411101494018, 754220218301026231032, 860057504564641127682, 895965022987753171419, 904744940324446807318, 1350650129695249176568, 1474841158733738137711, 1702259183351533337068, 1707392125695342504348, 1786595743440215727323, 1866004788235399428730, 2021521390014319431432, 2149280509511211774827, 2224183918046598697675, 2262767288002926709269, 2355639885555472733772, 2627598404185081429432, 3661364551741763772965, 4256797797404613635163, 6694462477782585046432, 9443926883403066025057, 10442269772936340101219, 14218352152467117817607];

\p 10000
775078*Pi-sum(i=1,57,c[i]*atan(1/t[i]))
\p 28                       
sum(i=1,length(t),log(10)/log(t[i]))
vecmin(t)

output:

?    realprecision = 10018 significant digits (10000 digits displayed)
%3 = -6.630182182933390232 E-10012
?    realprecision = 38 significant digits (28 digits displayed)
? %4 = 2.747877508222941264640834032
? %5 = 100706129803452075294

this comes from solving a system of linear equations, so the result is really 0, hence we got 775078*Pi. [we need a division by a small integer at the end to extract Pi].

Used the first 64 primes that is p=2 or p==1 mod 4, the largest such prime is 757. Could be able to eliminate 7 of them from lots of smooth solutions to keep only 57 primes and got the 57 terms formula.

[R. Gerbicz]

Found 47668 positive integers x for that x^2+1 is 757-smooth, downloadable at:
https://drive.google.com/file/d/1etr...ew?usp=sharing
An old link giving all 200-smooth solutions from Filip Najman: https://web.math.pmf.unizg.hr/~fnajman/rezplus1.html .

Estimating that there could be roughly 50 missed solutions, among them maybe 30 could be found by an extended search [and note that most of these missing solutions are large so interesting]. The search is exhaustive up to a trivial bound of x<2^32.

Improving a little my above arctan formula, using "only" 55 terms.

c=[38700408465202267483521896, 8074294657163898941499704, 18084751995220504885485716, 10617955537629685604246870, 19381616293392725222395433, -16189431078249810956810540, 2663025114949728099146368, -50821290463616663282060093, 30425287250801654451464701, 5340157628142302862996217, 22257467534574983490163989, -14144052764618268971400705, -34131146882264238757385174, 11517420707788714186671327, 8809498563247969729331508, 9575603319763050834812608, 15013272622091770042897526, 29140822288315176159081433, -26490842270571571240632907, 5379280183188158967246185, 5063193213575554175323319, -21300699540591335158945812, 8765725584890890359073192, -17326267072532326425177716, -22969712961519988945581982, 31015402417393992158722336, 10715218695035024392773646, -6113768192429322401565231, -4959518686523357079068044, -880411196551256194486712, 27222064789916150912426297, 7028400065270324699241782, 6395517824304850284055402, 18382148784793948016890109, -2855737811750830775510733, 1068772694019506440335964, -41696581550717723841749863, -16855984420970193840253782, -17092009580615526091509951, -23678688598446556163790278, -26729067208666826400667006, 5535790741910445875384556, 23253488897611068459648879, 24301719811330032094835131, 13721545967545530609700672, 13638635186955032439915208, -18955462927775883750148916, 15175566500788591331215485, -5657889873218460002259652, -15307860016596651362908660, -12509769441463825443360783, 11660996728649361829160489, 31487859219307743314750041, 10708478645651051077334419, 22413720577850484247874341];
t=[100706129803452075294, 106655703945746057991, 113990292132078182007, 140759366414993038318, 149715090987851395482, 151179894086004836582, 155531320434402458222, 171268442677083970343, 177235659472193946346, 186312414964043780693, 242114657461222775367, 242526457156343868609, 277741650285265886109, 279268215504325418912, 293274837014756552545, 302685178196926874954, 306254909186162917405, 311286554505870488322, 363062694467323053757, 397699150117042862902, 398125775635597684856, 418334276059947230443, 422700922123169074432, 503324067165721943132, 506455457999459591693, 521654927153748407703, 525407238990959323474, 547748886534189022833, 647982671411101494018, 649758297700675498335, 650661171274734088043, 750314893492593005877, 754220218301026231032, 817599728075480257318, 821365850240730409698, 895965022987753171419, 903117827229218160068, 904744940324446807318, 1110592749392907292182, 1195553184514347168724, 1350650129695249176568, 1702259183351533337068, 3022165924225178134193, 4256797797404613635163, 5100058866488107804193, 5710642112294212610443, 6322604305061057220059, 6694462477782585046432, 7172059472210548010478, 9443926883403066025057, 14055524716836234863307, 16322365254295693911102, 63405805856857901256461, 68376738690185154260432, 372635354609714721488943];

\p 10000
430143*Pi/2-sum(i=1,length(t),c[i]*atan(1/t[i]))
\p 28                       
sum(i=1,length(t),log(10)/log(t[i]))
vecmin(t)

that gives:
?    realprecision = 10018 significant digits (10000 digits displayed)
? %31 = 2.762575909555579263 E-10012
?    realprecision = 38 significant digits (28 digits displayed)
? %32 = 2.627625297114408276801574520
? %33 = 100706129803452075294

[Mysticial]

Originally Posted by R. Gerbicz

Don't know why not use this colossal 57 terms(!) arctan formula what I've found, its efficiency isn't competing with Chudnovsky, but using a bunch of computers we could get the result quicker in Wall time, since all terms can be computed paralel, and using num=57 arctan terms we can get the final sum basically using only O(log(num)) big number additions time (and multiplying by a "small" constant integer in c[]).
For the smallest term in the sum(arctan(n)) we have n>10^20, so we get more than 20 digits per term, better than Chudnovsky.

c=[212346171621984379202607910, -141986132978022176645261831, -19188947083479808676847750, 72976183437824305758327029, -90487680380658315708343594, 311666636439147152580655021, 164886394092602675087156920, -277675188573061374603700591, -328918225746279750915200446, -115228975332701852008106265, 91695937787306382534509492, 274816818440262075651640693, -15278882553455239903148046, 12345819849357697383382739, -157487043779043149246827005, 165649173043654388123361981, 268335731435818979971293832, -74376668880349669845919200, 136746152203763097091123740, -106971635007532827887780437, -105558968251925687253287026, -82410840215405324255866021, 296511073341938960924412299, 79414242640647747520579196, 26575505338669030526976157, 42582496871221199838103045, -431056435239179795449215, 322897940072599977312538725, -5058363070279926676095997, 138150568339123858964501887, -100697699225584221681812015, -40360165609976142590233256, -32168480347955895535959243, -265774660195351767787225477, -19927028999571156486476849, -9604760200607125790956233, -388197118646979923787984357, -342841339813260618645453450, 178967052427653826777184469, -243278199242825683334544770, -32735042905672245875593049, 380865428210048809909621749, -215830479721667949495349715, 4859860087340886670720953, -306797318475862261176909614, 253850710497913248888215152, 99683692694159392561113651, 171658379893183050731039940, -89191773347130083621036329, 172802843689931488647278961, -96455659594184508250880480, 107781332940660320060027780, 195623057567176555762442409, -82697175828995156518216025, 8171045079609761562016517, 35001730194790928786362252, -28720454810100608397545222];

t = [100706129803452075294, 114063843547135341423, 117387028264098620557, 118182626635495860199, 120422248000399031137, 120870463680930344868, 120927259045345571307, 121843699825114397177, 125275271043850344818, 144552427347806978193, 151179894086004836582, 155531320434402458222, 171268442677083970343, 186312414964043780693, 200597192291437604193, 229771399727574656128, 242114657461222775367, 242526457156343868609, 252241001866777989537, 276914859479857813947, 279268215504325418912, 293274837014756552545, 306254909186162917405, 311286554505870488322, 321507762595941798843, 395467645802520991318, 397699150117042862902, 400464045964625262913, 408987081828419988057, 424370650490416068993, 431899278472593106531, 440044425799491348789, 503324067165721943132, 571415097863763305482, 647982671411101494018, 754220218301026231032, 860057504564641127682, 895965022987753171419, 904744940324446807318, 1350650129695249176568, 1474841158733738137711, 1702259183351533337068, 1707392125695342504348, 1786595743440215727323, 1866004788235399428730, 2021521390014319431432, 2149280509511211774827, 2224183918046598697675, 2262767288002926709269, 2355639885555472733772, 2627598404185081429432, 3661364551741763772965, 4256797797404613635163, 6694462477782585046432, 9443926883403066025057, 10442269772936340101219, 14218352152467117817607];

\p 10000
775078*Pi-sum(i=1,57,c[i]*atan(1/t[i]))
\p 28                       
sum(i=1,length(t),log(10)/log(t[i]))
vecmin(t)

output:

?    realprecision = 10018 significant digits (10000 digits displayed)
%3 = -6.630182182933390232 E-10012
?    realprecision = 38 significant digits (28 digits displayed)
? %4 = 2.747877508222941264640834032
? %5 = 100706129803452075294

this comes from solving a system of linear equations, so the result is really 0, hence we got 775078*Pi. [we need a division by a small integer at the end to extract Pi].

Used the first 64 primes that is p=2 or p==1 mod 4, the largest such prime is 757. Could be able to eliminate 7 of them from lots of smooth solutions to keep only 57 primes and got the 57 terms formula.

Coming from the other thread on Pi... Wow at this formula!

There is a way to (fairly) accurately estimate how fast a formula like this is for actual computer implementations.

Say you have a series that you want to sum up to D digits of accuracy. First you calculate how many terms N you need. (this is fairly easy since these are usually linearly convergent)

Suppose you sum up the N terms without rounding or truncation (keeping full integers). You will get a very large fraction where the numerator and the denominator are roughly of equal size (in digits).

The # of digits in either the numerator or denominator is roughly proportional to the amount of computation that is needed to sum it up. Thus if you need to compare the speed of series, (such as Chudnovsky vs. a single ArcTan series), you can use this method to get how fast they are relative to each other.

-------

Now the question is how do you actually calculate the size of the resulting fraction? You first have to derive the binary splitting recursion for it.

http://www.numberworld.org/y-crunche...tml#CommonP2B3

Which will have the polynomials: P(x), Q(x), and R(x).

Q(0, N) will be the denominator of your resulting fraction (before simplification). Thus the speed of the series is O( log(Q(0, N)) ). Where the big-O is dependent only on the hardware and software. It is roughly the same for different formulas.

-------

How do you compute O( log(Q(0, N)) )?

Q(x) will be a polynomial. (usually one that completely factorizes) So factorize it, then do a log-gamma on each term individually. Complex pairs will cancel out.

[Dr Sardonicus]

Originally Posted by fivemack

To find Machin-like formulae for pi, I want to find sets of N where N^2+1 has only small prime factors. Tangentially, it would be nice to have a proof that, for example, n=485298 is the largest number where n^2+1 has no prime factor greater than 53.

If n² + 1 has no prime factor greater than 53, we have n² - dy² = -1 where d divides 2*5*13*17*29*37*41*53. We then have to find all y divisible by no primes other than those specified.

It occurred to me that some of the quadratic fields , d as above, have fundamental units with norm +1; and for these d, n² - dy² = -1 will have no solution. Of the 255 values of d which are (non-empty) products of the eight primes 2, 5, 13, 17, 29, 37, 41, and 53, there are 70 such values of d, given below. Not a huge proportion, but it might help a little:

[34, 205, 221, 377, 410, 689, 1394, 1517, 1537, 1802, 1885, 1961, 3034, 4810, 4930, 5945, 6290, 7685, 10730, 11713, 15170, 19610, 19981, 23426, 25493, 26129, 27898, 30914, 33337, 45305, 56498, 56869, 81770, 99905, 117130, 139490, 141245, 197210, 257890, 282490, 335257, 339677, 433381, 439930, 739297, 747881, 804010, 960466, 1478594, 1638442, 1676285, 2166905, 2401165, 3396770, 4096105, 4833865, 7478810, 9667730, 9722453, 13668170, 17768621, 19444906, 23316290, 30311177, 39637693, 97224530, 125680490, 177686210, 303111770, 396376930]