## RE(2) question regarding base expansion

Expand Messages
• ... 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.