mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Abstract Algebra & Algebraic Number Theory

Reply
 
Thread Tools
Old 2020-09-20, 20:09   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·11·172 Posts
Default largest n such that n^2+1 has prime factors within a set

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

Code:
? 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)
fivemack is offline   Reply With Quote
Old 2020-09-20, 20:17   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

139710 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 is offline   Reply With Quote
Old 2020-09-20, 20:33   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

57516 Posts
Default

See also for lots of big arctan formulas: http://www.machination.eclipse.co.uk/FSChecking.html
(last update was at 2013)
R. Gerbicz is offline   Reply With Quote
Old 2020-09-21, 03:23   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·33·132 Posts
w00t

Quote:
Originally Posted by fivemack View Post
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 8th 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 10th 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.
Batalov is offline   Reply With Quote
Old 2020-09-21, 09:52   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·11·172 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
fivemack is offline   Reply With Quote
Old 2020-09-21, 17:39   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25×3×7×13 Posts
Default

Quote:
Originally Posted by Batalov View Post
I was only in 8th 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!

Last fiddled with by LaurV on 2020-09-21 at 17:48
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Not the largest prime Tomws Lounge 5 2020-05-03 01:46
Largest PM1 factors? hansl Data 4 2019-08-25 22:50
List of largest factors DrTarr Math 4 2016-02-11 07:00
NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 561 2013-03-29 16:55
need Pentium 4s for 5th largest prime search (largest proth) wfgarnett3 Lounge 7 2002-11-25 06:34

All times are UTC. The time now is 18:20.

Tue Sep 22 18:20:15 UTC 2020 up 12 days, 15:31, 1 user, load averages: 2.47, 2.20, 2.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.