Loading ...
Sorry, an error occurred while loading the content.

RE(2) question regarding base expansion

Expand Messages
  • Jose Ramón Brox
    ... From: gordon_as_number To: Jose Ramón Brox What I intend is an algorithm for finding a solution to x
    Message 1 of 1 , Oct 11, 2005
    • 0 Attachment
      ----- Original Message -----
      From: "gordon_as_number" <gordon_as_number@...>
      To: "Jose Ramón Brox" <ambroxius@...>


      What I intend is an algorithm for finding a solution to
      x or a,b in N=ax^2+bx+c, with c known. There appear to
      be only \ln N choices of the number N to finding one of
      these variables.

      I do have to comment though that a number with only two
      factors may require a cubic or quartic polynomial.

      Basically, any information towards finding a,b, or x is
      important and might solve the factorization problem.

      Gordon

      -------------------------------------------------

      If c is known, then simply take into account the number N' = N-c that will have
      (a',b',c'). We need know to study how to get c' = 0.

      N' = a'x^2 + b'x = x(a'x + b)

      In words, we need N' to be a multiple of the base. If you wanted to apply this problem to
      factoring, at first sight it seems that it doesn't worth it because it doesn't reduce the
      complexity (we need to factor N' in two factors).

      We know that the biggest base x in which N has 3 digits is Floor(Sqrt(N)), but which one
      is the smallest?
      We can assure that it is x = Floor(N^(1/3))+1:
      (x-1)^3 = (Floor(N^(1/3))^3 <= (N^(1/3))^3 = N --> N)x-1 has more than 3 digits
      x^3 = (Floor(N^(1/3))+1)^3 (>)= Ceil(N^(1/3))^3 >(=) (N^(1/3))^3 = N --> N)x has less
      than 3 digits (when N is not a perfect cube, the second inequality is strict and the first
      is an equality, while when N is a perfect cube, the second is a equality but the first is
      a strict inequality).

      So our problem is reduced to find a factor of N' that lay between L = Floor(N'^(1/3)+1)
      and U = Floor(Sqrt(N')). A first corollary is that not every number has a 3-digit
      expansion with a given c; in particular, those N' prime won't have a solution.

      We should take in mind that c must be less than x (c<x) so we have to add this restriction
      to the problem.

      For example:

      Find a base x for the 3-digits expansion of N = 403, with c = 2.
      N' = N-c = 403-2 = 401

      We want a base x so that N')x = ab0.
      L = 8, U = 20
      But 401 is prime! We don't have a solution with c = 2. If we try with c=1 then:
      N' = 402, L = 8, U = 20
      As 402 = 2*3*67, we can't find a factor between L and U.

      If c = 3 then N' = 400, L = 8, U = 20, 400 = 2^4 * 5^2 and we can use x={8,10,16,20) (c<x
      for every x)
      With x1 = 8, N')x1 = 620; x2 = 10--> N')x2 = 400; x3 = 16 --> N')x3 = 190; x4 = 20 -->
      N')x4 = 100

      And so, the solutions to our original problem are:
      N)x1 = 623, N)x2 = 403, N)x3 = 193, N)x4 = 103

      I hope this is useful, but I fear it is not; not because my solution may be fruitless, but
      because I think it says that we can't not save much time with this via.

      Regards. Jose Brox
      PS Forgive me Euclid for living! I messed all the quotients and remainders (R and S) in my
      last message. You know what I meant.
    Your message has been successfully submitted and would be delivered to recipients shortly.