## Updates to my BC number theory programs

• Improved code and output for surd(d,t,u,v,e) in patz.
• Removed a print statement in exceptionals which was causing a problem.
• 18th July 2016. Fixed some errors in patz in function sswgeneral(a,b,c,d,e,f).
• 1st July 2016. (i) I had forgotten to include lineareqn(a,b,c,d,e,f) and lineareqnn(a,b,c,d,r,s,n to file patz. (ii) In lineareqn(a,b,c,d,e,f) I had written delta=ad-bc instead of delta=a*d-b*c.
• 24th May 2016. Added conwaysequence1(a,b,n) to phi.
• 23rd May 2016. Added conwaycycles(a,b) to phi.
• 10th September 2015. Added stolt0(d,n,flag) to stolt.
• 8th September 2015. Programs aa1(a,b,c) and aa2(a,b,c,n) under construction.
• 26th August 2015. Updated patz so as to include aa1(a,b,c) and aa2(a,b,c,n).
• 25th May 2015. Added rep(p).
• 21st May 2015. Added inverse(m,n).
• 13th May 2015. I realized that I had two different functions called hyperbola - one in patz, the other in powerdd. So I've renamed the first one hyperboladd.
• 7th May 2015. Updated patz which now contains sswgeneral, hyperbola(a,b,c,d,e,f,dd,gg), hyperbolagg(a,b,c,d,e,f,dd,gg) and ellipse(a,b,c,k,alpha,beta). It also involved updating gcd, powerdd, genfacs, posformrep, reduceneg and constructing the files powertest3 and congruence.
• 7th April 2015. Replaced c by globalsqc and count by globalsqcount in squareroot and squareroot2.
• 5th April 2015. Added ssw4 to patz.
• 24th March 2015. Added to patz.
• 17th March 2015. In binary0(a,b,c,n,e,f), the case a=n=1 was dealt with at the start without using continued fractions.
• 16th March 2015. Added functions binarygen(a,b,c,n) and binarygenlist(a,b,c,n) to patz.
• 11th March 2015. Added functions posrepgen(a,b,c,n), posrepgenlist(a,b,c,n), ssw1(a,b,c,d,e,f) to posformrep.
• 10th March 2015. Noticed a subtle bug in function quadratic(a,b,c,flag) when there was no soltion.
• 9th March 2015. Added functions patzgen(d,n) and patzgentest(d,n) to patz. Also added ssw0(a,b,c,d,e,f) to nagell_test.
• 7th March 2015. Corrected the signs of the fundamental solutions.
• 5th March 2015. I noticed that nagell_test somehow became corrupted. This has now been fixed.
• 21st February 2015. Added wildberger1.
• 2nd February 2015. Added lprimrootneg(p), lprimrootposmn(m,n), lprimrootnegmn(m,n), to phi. Added lucasnonverbose(n) to lucas.
• 15th January 2015. Corrected error introduced in previous change in fund() in stolt.
• 14th January 2015. Treated the case d=x2 + 1 separately at the start of fund() in stolt.
• 14th January 2015. Fixed an error in fund> which appeared when d=41.
• 13th January 2015. Fixed a double counting error in stolt when v=0.
• 17th December 2014. Improved code in stolt.
• 22nd November 2014. Fixed faulty code in stolt.
• 20th November 2014. Added dujella_minus.
• 22nd October 2014. Added stolt.
• 20th August 2014. Added euclid0.
• 14th July 2014. Added posformrep.
• 14th May 2014. Increased the number of primes used in Miller's test to 17 in factors and phi.
• 28th March 2014. Made some improvements to primepatterns.
• 26th March 2014. Added primepatterns.
• 16th December 2013. Added patzpos.
• 13th November 2013. Added markoff_triples.
• 19th July 2013. Fixed a logical error in stolt(d,n) in the determination of ambiguous solution.
• 18th July 2013. Added stolt(d,n) to nagell_test.
• 14th July 2013. Now print two digits in the Nagell and Frattini bounds.
• 11th July 2013. Fixed an error in frattini(d,n) in nagell_test.
• 15th December 2012. Added nagell_test.
• 18th September 2012. Added squareroot2.
• 8th May 2012. Added pellab.
• 9th January 2012. Added genfacs.
• 27th October 2011. Deleted the OCF program due to a missing case.
• 5th August 2011. Added cloitrem.
• 20th July 2011. Added cloitre.
• 15th July 2011. Added ordercomposite to reduceneg.
• 15th July 2011. In classnoneg, table(m,n) now calculates h(-d) for 3 ≤ m ≤ d ≤ n , d ≡ 0 or 3 (mod 4).
• 14th July 2011. Added compose, compose1, power_compose and power_compose1 to reduceneg.
• 14th July 2011. Added bezout and bezout1 to gcd.
• 13th July 2011. Fixed an error in reduceneg.
• 24th June 2011. Reinstated powerdd and tidied up things.
• 23rd June 2011. Added partition.
• 15th June 2011. Added kronecker and altered jacobi so that now jacobi(m,1)=1.
• 9th June 2011. Added bernoulli.
• 8th June 2011. Added tangent.
• 15th March 2011. Replaced p-adic by padic. Currently it does not contain the 2-adic squareroot algorithm, but this will soon be reinstated.
• 26th November 2010. Forgot to add gcd() and gcd3() to the new version of nscf_pell.
• 25th November 2010. Replaced nscf_pell. The new version uses a test for NSCF reduced which is better than the actual definition, which was used in the original program.
• 25th November 2010. Brian Gladman has pointed out that in nscf_pell, inside the function nscf_pqa(), the line d=d*(t*t) should be outside the braces. This error was also present in nipell.
• 2nd November 2010. In ocf, fixed a bug in ocf_pqd1, where I should have tested if(pk==3 && qk==3 && d==5) instead of if(pk==3 && qk==3). Also updated the ocf file by adding the function ocf_pqd2, which replaces ocf_pqd1.
• 4th September 2010. Improved the logic in carmichael.
• 27th August 2010. Altered the printing in carmichael. It now tests Carmichael's conjecture.
• 26th August 2010. Added carmichael. This necessicated updating nprime (to get a non-verbose version) and lucas (to deal with the possibility that n could be even).
• 4th January 2010. Added fibonacci.
• 20th November 2009. Added ocf.
• 29th March 2009. Added equivalent.
• 3rd October 2008. Added spiral.
• 21st August 2008. Noticed that variable a in nipell should have been declared to be auto.
• 10th January 2008. Added nicf_pqa0(d,t,p,q,e) to nipell. Bugs fixed subsequently.
• 8th January 2008. I now convert the input surd (u +t√d)/v to standard form in files nipell and nscf_pell. ie. (U +√D)/V, where gcd(U, V, (D - U2)/V) = 1.
• 1st December 2007. Removed auto variables t1 and t2 in nscf_pell(d,e). Apparently 26 is the maximum number of auto variables allowed in a BC function! Also tightened the logic in the definition of the partial numerators a[i].
• 15th November 2007. Added gcd3(a,b,c).
• Altered the code for the nearest square algorithm so as to agree with lines 5-6, page 25, of the A.A.K. Ayyangar paper, when |Q'| = |Q"|.
• 2nd November 2007. Added nscf_pqa(d,t,p,q,e) to nscf_pell.
• 1st November 2007.Made some small improvements and corrections (regarding the period length) to nscf_pell and nipell.
• 31st October 2007. Added nscf_pell.
• 22nd October 2007. Added nicf_pqa(d,t,u,v,e) to nipell.
• 18th October 2007. Added nicf(m,n) to lra.
• 12th October 2007. Corrected output about period in nipell.
• 11th October 2007. Added nipell.
• 12th February 2007. Added sqrtd_period.
• 9th February 2007. Added decimal2rational.
• 8th February 2007. Removed the restriction gcd(b,n)=1 from the decimal program.
• 15th November 2006. Small improvement to reducepos.
• 13th June 2006. Fixed a serious error in nprimeap.
• 8th August 2004. Added binary to patz.
• 16th July 2004. Added patz.
• 14th July 2004. squareroot continues to haunt me.
• I fixed a bug in relation to solving x2 0 (mod 2).
• Also had an incorrect construction for extending the solutions to original modulus n, so as to list them in the form ±P (mod n), with 0 ≤ P ≤ n/2.
• Replaced if(qglobal[i]==2 && number==1) by if(number==1). This error was giving the wrong answer in x2 0 (mod 6).
• 14th May 2004. Added forster_log.
• 13th May 2004. Noticed that I'd omitted a restriction that in discrete_log, we must have p < 232-216 in order to satisy BC array upper bound length of 216-1.
• 27th April 2004. Fixed a small global variable problem arising when calculating Ramanujan's tau function tau_composite(n). Having factored n and obtained global variables representing the prime factors q[i] and their exponents k[i], I inadvertently changed these on subsequent factorisations involved in calculating tau(q[i]).
• 21st April 2004. Added sigmak(k,n) and tau to phi.
• 15th April 2004. Added squareroot, which is a cleaner version of sqroot. The new program contains cornacchia(a,b,m).
• 7th April 2004. Improved factor and phi by incorporating pollard.
• 24th March 2004. Changed name of cfrace to davison.
• 23rd March 2004. Added cfrace.
• 22nd March 2004. Added raney.
• 19th March 2004. Inserted a sign term in function padic.
• 27th February 2004. Added factorial.
• 26th February 2004. Added binomial.
• 22nd May 2003. Added unimodular.
• 15th May 2003. Added the solution of equations x2-d*y2=±3 and ±4 to pell.
• 14th May 2003. Added table(m,n) to classnopos.
• 14th May 2003. Added table(m,n) to classnoneg.
• 12th May 2003. Fixed a small error in the function period. It was supposed to be returning the cycle-length, not global_count!
• 12th May 2003. Added class_number0(d) to classnopos.
• 7th May 2003. Fixed an error on lines 58-60 of classnoneg.
• 5th May 2003. Added classnopos.
• 1st May 2003. Added reduceneg.
• 29th April 2003. Added classnoneg.
• 28th April 2003. Changed the output of surd to allow choice of printing complete quotients.
• 27th April 2003. Added reducepos.
• 20th April 2003. Fixed a trivial printing error at the end of unit.
• 19th February 2003. Added program john.
• 23rd September 2002. Fixed errors on lines 104 and 112 of lagrange, where I had 2 instead of n.
• 18th September 2002. lagrange now needs sturm. gcdpi and sturm now have an extra parameter e, where e=0 suppresses printing. lagrange has also been tightened up. We now check that the input polynomial satisfies the appropriate restrictions. Also the program now handles the case when the root above 1 is in fact rational.
• 16th September 2002. Improved printp in sturm.
• 15th September 2002. Added sturm.
• 11th September 2002. Interchanged lines 43 and 44 in decimal to fix a printing error.
• 9th September 2002. Added nprime and nprimeap.
• 3rd September 2002. primes now generates more primes.
• 3rd September 2002. Made a small improvement to primes when m=2.
• 2nd September 2002. Added missing else b=0 at line 214 of proth.
• 27th August 2002. Rewrote leastqnr so that it ony needs mpower as in gcd.
• 25th August 2002. Improved the output of surd.
• 22nd August 2002. Improved the output of pell.
• 9th August 2002. Added base and perfect_power.
• 31st July 2002. Replaced "<=" by "<" on line 11 of mthrootr() in gcd.
• 25th June 2002. Replaced all log programs by log.
• 14th June 2002. Added another log program - log2.
• 8th March 2002. I removed the line j=2 from gcd1 in gcd and sqroot. (Kindly pointed out by Kjell Wooding.)
• 10th August 2001. I reinstated log1.
• 24th July 2001. I replaced the above log program by the one that is currently in my manuscript log.pdf.
• 14th June 2001. Today I noticed problems with degenerate cases arising from small r in my log algorithm.
• 23rd February 2001. Added tomas2.
• 13th February 2001. Added tomas1.
• 20th October 2000. Altered unit so that when d=5 it returned the correct answer.
• 7th August 2000. Altered log(a,b,r,e) to log(a,b,d,r,e)
• 29th July 2000. Improved the printing in log.
• 6th May 2000. Fixed a bug in surd.
• 1st May 2000. Corrected printing of output in thue: changed s to t at appropriate places.
• 26th April 2000. surd now prints Pn and Qn, where the nth complete quotient is (Pn+sqrt(d))/Qn.
• 11th April 2000. Realised sqroot still had some bugs. Hopefully these are now fixed.
• 7th April 2000. Replaced sqroot by an improved version which solves the general congruence x2d (mod n). Any bug reports are gratefully received.
• 6th April 2000. Realised sqroot has some bugs.
• 5th April 2000. Changed thue(d,p) to thue(d,u,p).
• 4th April 2000. Added sqroot. This finds all solutions of x2d (mod n) where gcd(d,n)=1.
• 3rd April 2000. Changed name of chineseab() to chineseb(). Rewrote chinesea() and chineseb().
• 2nd April 2000. Added printing of partial quotients and truncated decimal expansion to log. Removed printing of A[i]. Also added thue. Here d>1, is not a square, p an odd prime not dividing d-1. Then thue(d,p) finds x,y such that x2-dy2=kp, with small k.
• 1st April 2000. jacobi now does not need gcd and is a stand-alone program.
• 28th March 2000. Discovered that the old version of log did not always give the correct partial quotients. The current version seems to be more reliable. Type log(3,2,2,10,0) to output roughly 20 partial quotients of log2(3), whereas typing log(3,2,2,10,1) prints the A[i] of algorithm 1 of manuscript log.pdf. The number of partial quotients is returned in both cases.
• 13th March 2000. Made some improvements to the output of log.
• 4th March 2000. Added rootd_modn. This is a crude program for solving x2d (mod n) with 0 ≤ x ≤ n/2 for small n.
• Added log. This is a discrete variant of Shank's algorithm for computing the simple continued fraction for logbn, (Math. Tables and Aids to Computation. 8, 1954, 60-64), originally written by Alan Offer and recently improved by vacation scholar Sean Seefried and myself. It should currently be treated with caution. For while we believe that log(n,b,z,e) computes approximately 2z partial quotients of logbn, we cannot guarantee the correctness of output!.
• lagrange was improved by Sean Seefried, using the binary search method in page 261 of Number Theory with Computer Applications, by R. Kumanduri and C. Romero, 17th December 1999.
• Improved the euclid program. It now prints the s[k] and t[k] associated with Euclid's algorithm.
• Forgot to test possibility np=2 in leastqnr(p). Fixed 28th September 1999.
• Cosmetic alterations to the tonelli program, 24th August 1999.
• Added leastqnr, 13th August 1999. Also removed dependence of proth on phi and gcd.
• Removed dependence of lucas on phi.
• Tightened up the discrete_log program, 11th August 1999.
• Added the discrete_log program, 12th July 1999.
• Added the tonelli program, 29th June 1999.
• Fixed bug in gcd in lcma(m[ ],n) (should have returned b[n-1], not b[n]) 11th November 1998.
• Added some functions to phi that are normally in gcd, 9th October 1998.
• Added recursion, 3rd May 1998.
• Added the lupei program. 24th March 1998.
• Added to lra. 21st December 1997.
• Added the lagrange program. 17th December 1997.
• Added the convergents program. 15th December 1997.
• Added the lra program. 24th January 1997.
• Added the venturini1 program. 1st April 1996.
• Added a missing case at line 27 in unit(n). 5th November 1995.
• Added the mordell program. 26th September 1995.
• Added the challenge program. 27th August 1995.
• Added the 3branch program. 26th August 1995. Fixed a bug there on 27th August 1995
• 15th June 95. Deleted the for loop in function b(n) on line 253 of factors.