Page 3 of 3 FirstFirst 123
Results 31 to 45 of 45

Math Help - Integer Solutions?

  1. #31
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by Media_Man View Post
    (After three days, my program is still running, though not turning up anything new . I am trying to pare it down as much as possible for another run.)
    Earlier you mentioned the following

    Quote Originally Posted by Media_Man View Post
    Something odd/useful though: Using the same exact algorithm to look for solutions for A up to six factors, these are the only solutions I found, the same eight five-factor ones that you guys found before I made my own algorithm. This means that no combination of six prime factors from the list {1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2 81,401,421,857} make a solution. All the six-factor solutions I thought I'd found earlier were simply four-factor primitives with an extra x^2 factor. I doubt this means no six-factor primitive solutions exist, but I am now intrigued. I'm going to try to run my algorithm with all primes up to 1000, instead of just this small set. Maybe it will terminate in a few *days* and give me what I'm looking for, a six-factor primitive solution.
    So all primitive k = 4 solutions found thus far have only 4 prime factors and they all come from the set {1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2 81,401,421,857}, yes? I wonder if the # of primes in a given a_1 is a power of 2. I'm going to attempt looking for a_1 that have 2^3 from your list. Perhaps you could try the same, or perhaps try 2^4.



    Quote Originally Posted by Media_Man View Post

    So 10^2+11^2=14^2+5^2=221. So given the factors of a large number N, I can extremely quickly find all integer solutions x,y to N=x^2+y^2. For our purposes, we'll need to use a polynomial to approximate sine and cosine for speed, though. This will be much faster than the loop structure and function calls I have in place now.
    I'm not sure I follow? If you know the prime factors of N, how does one do this using polar coordinates?

    In question 5.17 of Pomerance's book, the reader is asked to derive a polynomial-time algorithm for finding integers (x,y) such that x^2 + y^2 = p where p is prime of the form 1 + 4k (unfortunately no algorithm appears to be described in the text and the question refers to a 1985 paper by Schoof).

    Since the primes your using are all under 1000, and that there always exists integers x,y both less than p^0.5, perhaps a brute force is best.
    Follow Math Help Forum on Facebook and Google+

  2. #32
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408
    Quote Originally Posted by jamix View Post
    I'm not sure I follow? If you know the prime factors of N, how does one do this using polar coordinates?
    Consider the identity: (a^2+b^2)(c^2+d^2)=(ac\pm bd)^2+(bc\mp ad)^2, except let r_1^2=a^2+b^2,r_2^2=c^2+d^2,\theta_1=\arctan(\frac  {b}{a}),\theta_2=\arctan(\frac{d}{c})

    Then the identity becomes r_1^2r_2^2=(r_1\cos(\theta_1)r_2\cos(\theta_2)\pm r_1\sin(\theta_1)r_2\sin(\theta_2))^2 +(r_1\cos(\theta_1)r_2\sin(\theta_2)\mp r_1\sin(\theta_1)r_2\cos(\theta_2))^2 =\left(r_1r_2\cos(\theta_1\pm\theta_2)\right)^2+\l  eft(r_1r_2\sin(\theta_1\pm\theta_2)\right)^2. The best way to understand it is to try it!

    Always clarifying with an example: If p=13=2^2+3^2,\theta_p=\arctan(\frac32)=.9827,q=17=  1^2+4^2,\theta_q=\arctan(\frac41)=1.3258, then pq=221=(\sqrt{221}\cos(.9827\pm1.3258))^2 +(\sqrt{221}\sin(.9827\pm1.3258))^2=10^2+11^2=14^2  +5^2

    The algebra gets hairy, but it can be shown that this process is nested. Given a number N with prime factors f_i=x_i^2+y_i^2, define \theta_i=\arctan{\frac{y_i}{x_i}}. Then N=f_1f_2f_3...f_k=(\sqrt{N}\cos(\theta_1\pm\theta_  2\pm\theta_3...\pm\theta_k))^2+(\sqrt{N}\sin(\thet  a_1\pm\theta_2\pm\theta_3...\pm\theta_k))^2

    Quote Originally Posted by jamix View Post
    So all primitive k = 4 solutions found thus far have only 4 prime factors and they all come from the set {1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2 81,401,421,857}, yes? I wonder if the # of primes in a given is a power of 2. I'm going to attempt looking for that have 2^3 from your list. Perhaps you could try the same, or perhaps try 2^4.
    Actually, no. We have found 4 4-factor, 5 5-factor, and 1 6-factor solutions thus far (see above posts). Dilcher's 1999 proof does manage to convince us that there are no 3-factor solutions, and it is trivial that there are no 1- or 2-factor solutions.

    Quote Originally Posted by jamix View Post
    In question 5.17 of Pomerance's book, the reader is asked to derive a polynomial-time algorithm for finding integers (x,y) such that x^2 + y^2 = p where p is prime of the form 1 + 4k (unfortunately no algorithm appears to be described in the text and the question refers to a 1985 paper by Schoof).
    This I didn't find any trick in doing, but it doesn't slow down the algorithm because it can be done separately, before everything else. If there are only 168 primes p of the form 4k+1 up to 1000, then the integer solutions x,y to p=x^2+y^2 can be found by trial in a split second. Then an array of p_i's can be stored, along with an array of \theta_i's. I'm sure Pomerance is interested in doing this for extremely high values of p, but in our application, I am assuming that the two squares that sum to a given prime are easy to find, unique, and constant throughout the program.
    Follow Math Help Forum on Facebook and Google+

  3. #33
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by Media_Man View Post
    At last here is our generating algorithm in simplest form:

    a^2+b^2=c^2+d^2=e^2+f^2=g^2+h^2=A
    2(a^2b^2+c^2d^2)=2(e^2f^2+g^2h^2)=B
    2|a^2b^2-c^2d^2|=C_1
    2|e^2f^2-g^2h^2|=C_2
    (These are the C-values for the two k=3 ladders that multiply to get the desired k=4 ladder)
    \frac12(C_1^2+C_2^2)=C
    \frac12|C_1^2-C_2^2|=D

    The eight roots can be gotten by r=a\pm b, c\pm d, e\pm f, g\pm h or by r^2=A\pm\sqrt{B\pm\sqrt{C\pm D}}
    You know this formula is probably new (It appears only the first condition is described in Dilcher).

    In any case, I decided to use the above to actually write out some of the k = 4 polynomials in terms of (a_1,a_2,a_3,a_4). I also used the chance to check that your formula is correct by checking that various roots r_i are such that P(r_i) = 0 (I'm too lazy to go through the algebraic proof).

    Here are the 4 ones that I did:

    1) A = 67405:

    (67405,3525798096,533470702551552000,4692082091913  21600)

    2) A = 600445:

    (600445,172337340816,16685576724080968704000,10660  920170019569049600)

    3) A = 55445869:

    (55445869,1164899189250000,44622709555000952072468 7360000,359659829363407799927500800000)

    4) A = 5915065:

    (5915065,14071276316736,96909018922818605393510400 ,88118108724250005553152000)

    Two of these are so long I can't even Latex them, which is also why I chose to stop after doing four of the eight A's.

    In any case there is some interesting properties with regards to common factors among the a_i for a particular A.

    Have you been following some of the theory I've written in the past couple of posts over in the other thread? Each of these k = 4 ladders is generated by one k = 3 ladder in the sense there exists an (a_0,c) such that P_3(x) = P_4(y) when x = y^2 - a_0. The polynomial P_3(x) has the form (c^2a_1,c^4a_2,c^4a_3) where (a_1,a_2,a_3) is some primitive k = 3 ladder.

    For example, for the k = 4 given by A = 67405 we have (a_0,c) = (67405,12).

    Thus, when x = y^2 - 67405 this ladder is created by the k = 3 P(x), given by
    (c^224484709,c^425726789282000,c^422627710705600) where c = 12.

    Similarly, for the k = 4 polynomial given by A = 5915065, we have (a_0,c) = (5915065,24).

    When x = y^2 - 5915065, this ladder is created by the k = 3 ladder given by
    (c^224429299161,c^4292091709233997050400,c^4265595  186885880852000) where c = 24.

    For A = 600445 we have c = 12 and for A = 55445869, we have c = 60. I wonder if the value for c is always divisible by 12?

    Unfortunately this idea probably doesn't add anything of value that would make finding a k = 5 or k = 4 go any faster. It can however be used to find partial ladders (ie ladders of degree 2^k where many of the terms are linear, but not necessarily all of them are).
    Last edited by jamix; September 4th 2009 at 04:17 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #34
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Banking on the converse

    Consider the roots of P_3(x)=((x^2-a_1)^2-a_2)^2-a_3^2, r_i=\pm\sqrt{a_1\pm\sqrt{a_2\pm a_3}}

    Now substitute x=y^2-a_0, so the roots of P_4(y) become s_i^2-a_0=\pm\sqrt{c^2a_1\pm\sqrt{c^4a_2\pm c^4a_3}} or s_i=\pm\sqrt{a_0\pm c\sqrt{a_1\pm\sqrt{a_2\pm a_3}}}=\pm\sqrt{a_0\pm c r_i}

    So, the question becomes: Given four integers r_1,r_2,r_3,r_4, for what values a_0,c is a_0\pm cr_i a perfect square for all i?

    To use your example, the roots of P_3(24484709,25726789282000,22627710705600) are

    \sqrt{24484709-\sqrt{25726789282000- 22627710705600}}=4767
    \sqrt{24484709-\sqrt{25726789282000+ 22627710705600}}=4187
    \sqrt{24484709+\sqrt{25726789282000- 22627710705600}}=5123
    \sqrt{24484709+\sqrt{25726789282000+ 22627710705600}}=5607

    Transforming it into P_4(a_0,c^2a_1,c^4a_2,c^4a_3) with a_0=67405,c=12 gives our familiar 67405 k=4 ladder, whose roots are:

    \sqrt{67405-12*4767}=101
    \sqrt{67405-12*4187}=131
    \sqrt{67405-12*5123}=77
    \sqrt{67405-12*5607}=11
    \sqrt{67405+12*4767}=353
    \sqrt{67405+12*4187}=343
    \sqrt{67405+12*5123}=359
    \sqrt{67405+12*5607}=367

    So now given (a_1,a_2,a_3,a_4)=(67405,3525798096,53347070255155  2000,469208209191321600), for what values a_0,c is a_0\pm cr_i a perfect square for all r={101,131,77,11,353,343,359,367}? If you find this, then P_5(a_0,c^2a_1,c^4a_2,c^8a_3,c^8a_4) will be a k=5 ladder!

    The operative word here is "if." Even though every k=4 ladder can be spawned from a k=3 ladder, the converse is not true. Just because you have a k=3 ladder does NOT mean a a_0,c pair can be found producing the above results. Likewise, we have only uncovered 10 k=4 ladders so far. It is highly unlikely that one of these will be the one to spawn the lowest k=5 ladder using the above algorithm. But hey, it's worth a try

    Can you build a program that inputs r_1,r_2,r_3,r_4,r_5,r_6,r_7,r_8, loops through candidate values of a_0= 1\to 1000000 and c=1\to 1000 and checks to see that a_0\pm cr_i is a perfect square for all i?
    Follow Math Help Forum on Facebook and Google+

  5. #35
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by Media_Man View Post
    Can you build a program that inputs r_1,r_2,r_3,r_4,r_5,r_6,r_7,r_8, loops through candidate values of a_0= 1\to 1000000 and c=1\to 1000 and checks to see that a_0\pm cr_i is a perfect square for all i?
    I'll run my current program again, except this time put in your larger parameters. A few days ago I ran it for a_0= 1\to 100000 and c=1\to 500. I didn't find a k = 5 ladder that was a product of only linear terms, however with (a_0,c) = (33317,92) I found that 6 of the sixteen terms a_0\pm cr_i were squares when I was using the k = 4 generated by a_1 = 67405.

    As I said earlier, this method is no better than your method for finding a k = 5 by sieving through various a_1 and checking that they satisfy the necessary conditions (in fact its probably even worse than yours). The only positive, is that you can easily find many partial ladders. The programming may also be slightly easier.

    Anyways, if you are able to download Pari/gp, you can input the following code yourself:

    (note: for the below I decided not to sieve out the a_0 that are divisible by primes 3 + 4k to an odd exponent because I don't think this condition is necessary for partial ladders)
    roots1(a_0,c) = { local(y);
    y = 0;
    if( issquare(a_0 - 367*c) == 1, y++);
    if( issquare(a_0 - 359*c) == 1, y++);
    if( issquare(a_0 - 353*c) == 1, y++);
    if( issquare(a_0 - 343*c) == 1, y++);
    if( issquare(a_0 - 131*c) == 1, y++);
    if( issquare(a_0 - 101*c) == 1, y++);
    if( issquare(a_0 - 77*c) == 1, y++);
    if( issquare(a_0 - 11*c) == 1, y++);
    if( issquare(a_0 + 367*c) == 1, y++);
    if( issquare(a_0 + 359*c) == 1, y++);
    if( issquare(a_0 + 353*c) == 1, y++);
    if( issquare(a_0 + 343*c) == 1, y++);
    if( issquare(a_0 + 131*c) == 1, y++);
    if( issquare(a_0 + 101*c) == 1, y++);
    if( issquare(a_0 + 77*c) == 1, y++);
    if( issquare(a_0 + 11*c) == 1, y++);
    return(y);
    }

    roots2(a_0) = { local(y);
    y = 0;
    for( c = 1,1000,
    s = roots1(a_0,c);
    if( s > y, y = s);
    );
    return(y);
    }

    roots3(a,b) = { local(y);
    y = 0;
    for( a_0 = a,b,
    s = roots2(a_0);
    if( s > 5, print(s));
    );
    }
    In the code for ''roots2'', you can see I have c = 1,1000. To check every single a_0 from 1-1000000, I input ''roots3(1,1000000)''. I have the program set such that when I input the command ''roots3(a,b)'' it will output any a_0 such that there exists a c for which at least 6 of the 16 integers a_0\pm cr_i are squares. When this finishes, one can go back and slightly alter the code for ''roots2'' in order to find out exactly how many are squares, and what the c values are.

    I'll post here again when my program finishes.
    Follow Math Help Forum on Facebook and Google+

  6. #36
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Partial ladders = partially useful?

    Jamix -

    You know the original factoring algorithm better than I do. Are "partial" ladders of any use? By partial, of course, we're talking about polynomials with some non-integer, and possibly non-real roots, correct?
    Follow Math Help Forum on Facebook and Google+

  7. #37
    Member
    Joined
    Jun 2008
    Posts
    148
    Media_Man...

    So long as your polynomial ladder is a product of a very large # of smaller polynomials, then it can be used as an Integer factoring algorithm. To tell how efficient your polynomial is for Integer factoring, you need only calculate the following ratio:

    Let K be the # of squaring/multiplications one needs to do in order to calculate the polynomial ( say P(x)) and let L be the # of distinct irreducible polynomials that divide P(x).

    Call the ratio P = \frac{L }{K}.

    The larger P is, the better the polynomial is for factoring integers.

    In 6.17 of the Pomerance book, there is a rudimentary description on how one can create a factoring algorithm using these polynomials. I'll go into more descriptive detail later. Personally, I feel like this methology is more beneficial for sieving out composite integers when one wishes to find very large primes, as appose to full factorization for its own sake (after all there are far more superior algorithms for that).

    .................................................. ...........................

    With regards to the current situation:

    Now that I think about it, the above program is really slow. In fact if one simply checks the condition of whether or not a_0 is a quadratic residue over the primes 367,359,353,343,131,101,77,11, we can immediately determine if a_0\pm cr_i is not a square for any c for some of these primes.

    To check if an a_0 is a quadratic residue for a particular prime p, we need only apply Euler's criterion ( ie does a_0 satisfy (a_0)^(p - 1)/2 = 1 mod(p)).

    Here is some new code which is similar to the code above, but which goes significantly faster:

    residues(a_0) = { local(y);
    y = 0;
    if( ((a_0)^183) % 367 == 1, y++);
    if( ((a_0)^179) % 359 == 1, y++);
    if( ((a_0)^176) % 353 == 1, y++);
    if( ((a_0)^147) % 343 == 1, y++);
    if( ((a_0)^65) % 131 == 1, y++);
    if( ((a_0)^50) % 101 == 1, y++);
    if( ((a_0)^30) % 77 == 1, y++);
    if( ((a_0)^5) % 11 == 1, y++);
    return(y);
    }

    roots1(a_0,c) = { local(y);
    y = 0;
    if( issquare(a_0 - 367*c) == 1, y++);
    if( issquare(a_0 - 359*c) == 1, y++);
    if( issquare(a_0 - 353*c) == 1, y++);
    if( issquare(a_0 - 343*c) == 1, y++);
    if( issquare(a_0 - 131*c) == 1, y++);
    if( issquare(a_0 - 101*c) == 1, y++);
    if( issquare(a_0 - 77*c) == 1, y++);
    if( issquare(a_0 - 11*c) == 1, y++);
    if( issquare(a_0 + 367*c) == 1, y++);
    if( issquare(a_0 + 359*c) == 1, y++);
    if( issquare(a_0 + 353*c) == 1, y++);
    if( issquare(a_0 + 343*c) == 1, y++);
    if( issquare(a_0 + 131*c) == 1, y++);
    if( issquare(a_0 + 101*c) == 1, y++);
    if( issquare(a_0 + 77*c) == 1, y++);
    if( issquare(a_0 + 11*c) == 1, y++);
    return(y);
    }

    roots2(a_0) = { local(y);
    y = 0;
    for( c = 1,1000,
    s = roots1(a_0,c);
    if( s > y, y = s);
    );
    return(y);
    }

    roots3(a,b) = { local(y);
    y = 0;
    for( a_0 = a,b,
    k = roots(a_0);
    if( 6 > k, next);
    s = roots2(a_0);
    if( s > 5, print(a_0));
    );
    }
    Basically if a_0 isn't a quadratic residue for at 6 of the primes, then I immediately move to the next a_0 integer.
    Last edited by jamix; September 7th 2009 at 07:41 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #38
    Member
    Joined
    Jun 2008
    Posts
    148

    Integer factoring and programming results

    My program has finished running. My code for the residues function was flawed yesterday, so if your going to copy it, make sure to note the corrections made. You can see the results and my comments below, but first you asked earlier how it is polynomials can be used to create an integer factoring algorithm in this context, so I'll go into that now.

    Suppose n = pq is a composite integer we wish to factor. Furthermore, let P_(x) be some polynomial such that there exists an x_0 such that P(x_0) \equiv 0 mod(p). Even if we reduce P(x) over Z_n (that is we calculate P_n(x) = P(x)mod(n)), it will still be the case that gcd(P_n(x_0),n) = p giving us a factorization of n. Occasionally the gcd will equal n but thats not a big issue since this doesn't happen often. The real problem here is that we do not know what x_0 is, hence we must plug in multiple values of the variable x and calculate gcd(P_n(x),n) for each of them untill we get a gcd that factorizes n.

    Now if P(x) = Q_1(x)*Q_2(x)*....Q_k(x), then there likely exists many integers x_0,x_1,x_2,x_s such that P(x_i) \equiv 0 mod(p). This means we have less values of x to check before we obtain a nontrivial gcd. This is why we want to maximize the L value in the equation P = \frac{L}{K}. On the other hand, increasing L by multiplying together a bunch of polynomials may not be such a great strategy since we now have to do more multiplications or squaring operations to calculate P(x). That is, the value for K in P = \frac{L}{K} has also increased. To determine if changing P(x) just to increase to L was worth it, we need only determine if P has increased. If it has, then this new polynomial is more efficient for factoring. If not, then our first choice was more efficient.

    Lets do one example:

    Suppose we wish to factor the integer n = 851 using the polynomial P(x) = ((x^2 - 85)^2 - 4176)^2 - 2880^2. Reducing this polynomial over Z_{851} gives us the polynomial P_n(x) = ((x^2 - 85)^2 - 772)^2 - 554. To make sure that the values x checked are uniformly distributed, let us define x_i = 2^i mod(851) and plug these in until a nontrivial gcd is found.

    We have the following results:

    P_{851}(2^1) = 438 and gcd(438,851) = 1

    P_{851}(2^2) = 420 and gcd(420,851) = 1

    P_{851}(2^3) = 79 and gcd(79,851) = 1

    P_{851}(2^4) = 368 and gcd(368,851) = 23

    The last gcd is nontrivial and factores 851 into 23*37 which are both prime. Hence we have factored 851.

    The efficiency of this polynomial, is given by P = \frac{L}{K} = \frac{8}{3} = 2.67.

    If we had used one of the k = 4 polynomials, we might have been able to factor 851 even faster since then P = \frac{16}{4} = 4. On the other hand, the partial k = 5 ladder which is mentioned in the other thread, might do even better since in that case P = \frac{22}{5} = 4.4.

    Did you understand all this well enough?

    .................................................. ..............................


    I've finished running the code for a_0 in the interval 100000-1000000 and c in the interval 1-3000 (generally for larger a_0 one needs to use larger c to rule out a_0 as a particular candidate) . My program only ouputed 7 integers a_0, all of which created 6 squares among the 16 terms a_0 \pm cr_i, hence they're no better than the (33317,92) term I found awhile ago (ie they all have a P = 4.4).

    I believe it is not inconceivable that an (a_0,c) may exist which will produce seven squares among the a_0 \pm cr_i, although perhaps one may have to use a different k = 4 ladder. On the other hand, if this is as far as we can get using a 2^5 degree polynomial, then perhaps we should go up to 2^6 and see if we can obtain a P value that is higher than 4.4 this way.
    Follow Math Help Forum on Facebook and Google+

  9. #39
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Heuristics :-\

    This is an interesting tangent of the original problem. A k-ladder with all integer roots will have an efficiency of \frac{2^k}{k}, so a k=5 ladder, if we can find one, will have an efficiency of 5.67, but a partial ladder should have a range with this as an upper bound.

    Consider: The probability of a random number n be a square is about 1 in n, right? So take a known k=4 ladder with roots r_i and guess a_0,c -- the chances of s_i=\sqrt{a_0\pm cr_i} being an integer is about 1 in a_0\pm cr_i. Multiplying, the chances of s_{i+} and s_{i-} both being integers are 1 in (a_0+cr_i)(a_0- cr_i)=a_0^2-c^2r_i^2. The chances of all 32 roots being integers is therefore 1 in c^{16}(\frac{a_0^2}{c^2}-r_1^2)...(\frac{a_0^2}{c^2}-r_8^2) or 1 in c^{16}P_4(\frac{a_0}{c}).

    To minimize this, it makes sense that a_0,c are both small. Does it seem strange that the bigger we start guessing for these numbers, the less likely we are to find a solution?

    This may be a bad argument, but it's an interesting result. Take a perfectly good k=4 ladder with 16 integer roots, and the more you keep guessing a_0,c combinations, the less likely you are to find a k=5 ladder. If this result is valid, then it makes sense that there are so few of them. Am I misinterpreting something here?
    Follow Math Help Forum on Facebook and Google+

  10. #40
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by Media_Man View Post
    This is an interesting tangent of the original problem. A k-ladder with all integer roots will have an efficiency of \frac{2^k}{k}, so a k=5 ladder, if we can find one, will have an efficiency of 5.67, but a partial ladder should have a range with this as an upper bound.

    Consider: The probability of a random number n be a square is about 1 in n, right? So take a known k=4 ladder with roots r_i and guess a_0,c -- the chances of s_i=\sqrt{a_0\pm cr_i} being an integer is about 1 in a_0\pm cr_i. Multiplying, the chances of s_{i+} and s_{i-} both being integers are 1 in (a_0+cr_i)(a_0- cr_i)=a_0^2-c^2r_i^2. The chances of all 32 roots being integers is therefore 1 in c^{16}(\frac{a_0^2}{c^2}-r_1^2)...(\frac{a_0^2}{c^2}-r_8^2) or 1 in c^{16}P_4(\frac{a_0}{c}).
    It would be about 1 in (2c)^{8}\sqrt{P_4(\frac{a_0}{c})} since the probability of a given integer n being square is closer to \frac{1}{\sqrt{2n}}. For example, if n = 50 then n is at the midpoint of the interval from 1-100. Since there are \sqrt{100} = 10 squares in this interval, the probability that 50 is a square is arguably \frac{1}{10}.

    Quote Originally Posted by Media_Man View Post
    To minimize this, it makes sense that a_0,c are both small. Does it seem strange that the bigger we start guessing for these numbers, the less likely we are to find a solution
    Its best that (a_0,c) is chosen so that the majority of a_0 \pm r_ic are small. On the other hand, if (a_0,c) is large, than so are all the a_0 + cr_i, so yeah its best if (a_0,c) is small unfortunately.

    I'm going to try and take out a book at my library that discusses an algebraic version of the Pollard rho factorization algorithm since I believe it may shed some light on this issue (note: The Pomerance book discusses the Pollard rho method, however its not the algebraic version).
    Follow Math Help Forum on Facebook and Google+

  11. #41
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Mathematica

    Greetings all viewers/contributers! I require access to a symbolic-manipulation program like Mathematica or Maple to follow a possible lead:

    Expand and simplify in terms of x_i: (e_0-e_2+e_4)^2(e_1-e_3)^2, where
    e_0=1
    e_1=x_1+x_2+x_3+x_4
    e_2=x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4
    e_3=x_2x_3x_4+x_1x_3x_4+x_1x_2x_4+x_1x_2x_3
    e_4=x_1x_2x_3x_4

    You should see a lot of patterns and symmetry here, but this simple algebraic leap is close to intractable by hand.
    Follow Math Help Forum on Facebook and Google+

  12. #42
    Member
    Joined
    Jun 2008
    Posts
    148
    Not sure how to compress this. Is this the discriminant for a polynomial of degree 4 with 4 roots?

    I wrote a little program that will output this discriminant when you input (x_1,x_2,x_3,x_4), but I suppose this isn't necessarily what you want.

    expres(x_1,x_2,x_3,x_4) = { local(e_0,e_1,e_2,e_3,e_4,k);
    e_0 = 1;
    e_1 = x_1 + x_2 + x_3 + x_4;
    e_2 = x_1*x_2 + x_1*x_3 + x_1*x_4 + x_2*x_3 + x_2*x_4 + x_3*x_4;
    e_3 = x_2*x_3*x_4 + x_1*x_3*x_4 + x_1*x_2*x_4 + x_1*x_2*x_3;
    e_4 = x_1*x_2*x_3*x_4;
    k = (e_0-e_2+e_4)^2*(e_1-e_3)^2;
    return(k);
    }
    Follow Math Help Forum on Facebook and Google+

  13. #43
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408
    Not sure how to compress this. Is this the discriminant for a polynomial of degree 4 with 4 roots?
    I have no idea. I do know that this algebraic step could provide a link between our two conditions necessary to find a k=4 ladder, and the solutions p,q to f=p^2+q^2 for prime factors f of a_1.

    Expanding this thing fully results in about 150 terms, but I suspect (or hope dearly) that a lot of stuff cancels out, resulting in a simple, intuitive expression of x's.

    With a little luck, this approach could help us predict which factors most likely appear in a_1. What is the output of this program? Have you tried it?
    Follow Math Help Forum on Facebook and Google+

  14. #44
    Member
    Joined
    Jun 2008
    Posts
    148
    Media_Man...

    Sorry for the delay. I have less time to come here now since classes and teaching are back in full swing. I don't know how to compress the expression (e_0-e_2+e_4)^2(e_1-e_3)^2, however as a general rule of thumb, if you can express something as a square, then you should compress whatever is in the square. That is, you should attempt to compress k = (e_0-e_2+e_4)(e_1-e_3) instead, as this will lead directly to a compression for k^2 which is what you want.
    Follow Math Help Forum on Facebook and Google+

  15. #45
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Odd?

    Okay, I have pared down my algorithm as much as possible using this line of reasoning, and found no other solutions. This seems odd.

    (1) No values for A have been even numbers. My algorithm didn't even look for them, since I let A be every possible combination of prime factors 1,5,13,17,etc. But you guys initially counted A from 1 to 2 billion, right?

    (2) No more 4-factor solutions exist for factors under 5000. No more 5-factor solutions exist for factors under 2000. No more 6-factor solutions exist for factors under 500. (These upper bounds simply represent the computing limits of my pc.) This seems extremely odd. Why should A=67405,600445,55445869,242048509 be the first 4-factor solutions we find, all with prime factors under 1000, and then suddenly, they stop? Or, phrased another way: Of all possible combinations of 4 4k+1 primes less than 5000, not a single solution contained a factor greater than 1000! This means that if more 4-factor solutions exist, they would have to be greater than 5000^4=625 trillion! That's a pretty big leap for a sequence of integers following any kind of law. EDIT: Just upped the bound to 10000 and let it run overnight. No results. I am at a loss.

    I have attached my source code in case anyone thinks I have made some kind of programming error.

    Perhaps there are a finite number of k=4 ladders whose A value has a given number of factors? Perhaps there are a finite number of k=4 ladders, and we have here most or all of them! I believe these two observations are correct, but they do not make sense. I know this only seems like theoretical pouting for churning out 10 solutions and then hitting a wall, but come on...
    Attached Files Attached Files
    Last edited by Media_Man; September 15th 2009 at 05:20 AM. Reason: increased upper bound
    Follow Math Help Forum on Facebook and Google+

Page 3 of 3 FirstFirst 123

Similar Math Help Forum Discussions

  1. No integer Solutions
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 16th 2011, 03:01 AM
  2. integer solutions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 28th 2011, 09:07 AM
  3. Replies: 2
    Last Post: May 8th 2010, 10:59 PM
  4. Integer Solutions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 31st 2009, 09:18 AM
  5. Integer solutions to a^2+b^2=c^3
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 11th 2009, 07:48 AM

Search Tags


/mathhelpforum @mathhelpforum