Comments on A158415 =================== Reed Kelly (oeis at keldesign.com) and others Tue Mar 24 04:38:20 CET 2009 Hi Vladimir, Please excuse me if this is too basic. There is a chance that you have already thought this through and dismissed it as not useful. If I say something inaccurate, please let me know. I think that one can choose a value for the calculated difference between two candidates. The problem is that the bound may be too small to be practical. To see that a bound is possible, consider the following. All the numbers being considered are algebraic numbers having a corresponding polynomial with integer coefficients for which they are a solution. For example, sqrt(1+1+sqrt(1+sqrt(1+1))) is the solution of ((x^2-2)^2-1)^2-2 == 0 Let d be the difference between two such numbers. Clearly, d is also algebraic, so it is also the solution of a polynomial with integer coefficients. If we knew that the sum of the absolute values of the coefficients was at most A, and that the constant term had an absolute value of 'a', then the difference would either be 0, or it's absolute value would be greater than a/A. As long as a/A > eps, then an approach like the PARI listing should work. In order to provide an upper bound on A (and therefore a lower bound on eps), we need to keep track of the degrees and coefficient sums of each step in the construction of the numbers. Taking a square root doubles the degree, but it does not change the sum of the absolute value of the coefficients. Adding 1 only increases the sum by 1. Adding two algebraic numbers is the tricky part. If the two numbers are 'a' and 'b' with degrees 'm' and 'n' and sums of absolute values of coefficients A and B, then the degree of a+b is at most m*n and a very crude upper bound can theoretically be found for the sum of the abs val of the coeff of a+b minimal integer polynomial coefficients. If you actually had the two polynomials that 'a' and 'b' were roots of, then you could derive m*n potentially independent equations for terms representing a^i*b^j. Each of the intermediate equations would have coefficients having a sum of abs vals <= A^i*B^j. Solving the system of equations for a+b would result in a new equation with coefficients having a sum of abs vals < a-huge-number. Using Gaussian elimination to solve the system of m*n equations should introduce at most an additional factor of (A^m*B^n)^(m*n*(m*n+1)/2). I think this puts the upper bound somewhere around: (A^m*B^n)^(1+m*n*(m*n+1)/2) Unless I am totally off base, someone may be able to improve the estimate. I hope that this helps in determining whether eps can be computed. For smaller terms, the degree and sum of absolute values of the coefficients of the corresponding minimal integer polynomial can be computed directly in Mathematica with help from the function: RootReduce[]. For example, RootReduce[Sqrt[2]+Sqrt[3]] returns: Root[1 - 10 #1^2 + #1^4 &, 4]. This is degree 4 and has a sum of 12. Reed > -----Original Message----- > From: seqfan-bounces at list.seqfan.eu [mailto:seqfan-bounces at list.seqfan.eu] > On Behalf Of Vladimir Reshetnikov > Sent: Sunday, March 22, 2009 9:55 AM > To: Sequence Fanatics Discussion list > Subject: [seqfan] Re: A158415 > > On Sun, Mar 22, 2009 at 1:00 PM, Robert Gerbicz > <robert.gerbicz at gmail.com>wrote: > > > 2009/3/22 Vladimir Reshetnikov <v.reshetnikov at gmail.com> > > > > > Dear all, > > > > > > Can anybody suggest an algorithm for calculating the terms of A158415? > > > > > > Thanks > > > Vladimir > > > > > > _______________________________________________ > > > > > > Seqfan Mailing list - http://list.seqfan.eu/ > > > > > > > Hi! > > > > There are two possibilities for N symbols: u=sqrt(x) where x is using N- > 1 > > symbols, or u=x+y where x is using 1<=j<N and y is using 1<=N-1-j<N > > symbols. > > Extension of the sequence (I've already submitted): > > 1,1,2,3,5,8,13,20,33,54,91,154,264,455,791,1379,2424,4277,7588,13513, > > 24162,43336,77978,140683,254487,461409,838433,1526536 > > > > A quick PARI-Gp code for it: > > allocatemem(2*10^8);\ > > a=L=vector(28);eps=10^(-20);a[1]=[1];L[1]=1;print1(1",");\ > > for(i=2,28,b=vector(L[i-1]+sum(j=1,(i-1)\2,L[j]*L[i-j-1]));\ > > up=0;for(j=1,L[i-1],up++;b[up]=sqrt(a[i-1][j]));\ > > for(j=1,(i-1)\2,for(k=1,L[j],for(l=1,L[i-1-j],\ > > up++;b[up]=a[j][k]+a[i-1-j][l])));\ > > c=vector(up,j,b[j]);c=vecsort(c);s=0;\ > > for(j=1,up,if((j==1)||(c[j]>c[j-1]+eps),s++));\ > > a[i]=vector(s);s=0;\ > > for(j=1,up,if((j==1)||(c[j]>c[j-1]+eps),s++;a[i][s]=c[j]));\ > > L[i]=s;print1(L[i]",")) > > > > _______________________________________________ > > > > Seqfan Mailing list - http://list.seqfan.eu/ > > > > How did you prove that eps=10^(-20) is sufficient? In my view, the main > problem here is how to rigorously determine equality of two expressions. > > Thanks > Vladimir > > _______________________________________________