Re: JSH: Remarkably odd

On Feb 21, 5:43 pm, JSH <jst...@xxxxxxxxx> wrote:
On Feb 21, 11:17 am, marcus_bruck...@xxxxxxxxx wrote:



On Feb 21, 12:23 pm, JSH <jst...@xxxxxxxxx> wrote:

On Feb 21, 8:50 am, Joshua Cranmer <Pidgeo...@xxxxxxxxxxxxxxx> wrote:

JSH wrote:
I HAVE given a mathematical proof that I've solved the factoring
problem. Posters have done what they must to deny proof: talked
around it, ignored key points, and thrown up sand to distract others
from what they are doing.

To attempt to quote Scott Meyers (I don't have the book on me, so I'm
relying on admittedly poor memory): "In programming, what may be true in
other fields, even mathematics, might not be true." [given in reference
to the infamous Rectangle/Square or Bird/Penguin inheritance problems].

Algorithms can work; the question is, are they tractable for the problem
size. An O(10^100*n^10) algorithm will be intractable for any n we care
about, even though it theoretically beats out an O(10^-100*10^n)
algorithm, which is tractable for several n.

What's I've done is shift the factoring problem into a minima problem.

That, if true, shows it is as efficient as IS possible, as it makes
the problem as efficient as finding maxima or minima which is a solved
problem.

Given that reality, the only rational response is to focus on that key
assertion.

Instead you babble on about nothing in reply--which is the bizarre
thing I'm focusing on in this thread.

Let's look at the rest of what you said below. I said:

It's scary. Indication is that even with something as incredibly
important as a simple solution to the factoring problem, people can be
convinced that just pretending it's not there is a possible strategy.

And you replied:

Here's a simple solution to factoring, in, say, Java:
public int[] factor(int num) {
if (num < 1)
throw new IllegalArgumentException("Needs to be positive!");
List<Integer> factors = new ArrayList<Integer>();
int max = (int)Math.sqrt(num) + 1; // Safety-proofing
while (num % 2 == 0) {
num /= 2;
factors.add(2);
}
for (int factor = 3; factor < max; factor += 2) {
while (num % factor == 0) {
num /= factor;
factors.add(factor);
}
}
int[] out = new int[factors.size()];
int i = 0;
for (Integer factor : factors)
out[i++] = factor;
return out;

}

The actual core of the factoring is just 8 lines of functional code, and
is easy to write and understand for anyone who's just had high-school
level algebra.

Your algorithm isn't simpler than that, I can guarantee it :-) .

You shifted to a non-answer focusing only on "simple", but my solution
is simply a solution because it shows factoring can be just about
finding a minima, not because it is narrowly simple for some other
nonsensical reason.

The singular of minima is minimum. You don't say "a minima".

Sorry, a set of minima. You are correct. I have been imprecise in
that usage.

As I understand it, you define x and y in terms of a variable v,

x = r(v)/t(v) and y = s(v)/t(v),

where r(v), t(v), and s(v) are all integer-valued functions
if v is an integer. Then you have

x^2 - 1 = D*y^2, which can be written as

(r(v) - t(v))*(r(v) + t(v)) = D * s(v)^2.

Then you argue that if you choose v such that
abs(r(v) - t(v)) and abs(r(v) + t(v)) are both < D,
then you have a nontrivial factorization of D. So you

Nope. I argue that rational v EXISTS such that that condition is set.

Pay attention. I'm deleting the rest of your reply after the error.

Get it right next time.

___JSH

If it EXISTS, but you have no way to CHOOSE it, it is somewhat
academic, no? The deleted part is appended:

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

Then you argue that if you choose v such that
abs(r(v) - t(v)) and abs(r(v) + t(v)) are both < D,
then you have a nontrivial factorization of D. So you
choose v such that something - not sure what - is a
minimum. So there are some questions:

1. What function or functions do you minimize to ensure
that BOTH abs(r(v) - t(v)) and abs(r(v) + t(v)) are
less than D?

2. What if the minimum occurs when v is irrational,
and r(v) and t(v) are also both irrational? This will
not lead to an integer factorization.

3. How do you know you can choose v so that both
abs(r(v) - t(v)) and abs(r(v) + t(v)) are < D,
and r(v) and t(v) are both integers?

4. You may argue that you don't need v to be exactly where
a minimum occurs, but just close to a minimum, such that
r(v) and t(v) are both rational. But that would imply
that you might need to test a large number of rational
values near the (irrational) v_0 which is where the true
minimum occurs. How many such rational values might you
need to test? There are infinitely many rational v in
any neighborhood of v_0. Most of those are not going to lead
to a nontrivial solution. Searching an infinite set is
exactly the opposite of what you want to do here.

Could you address these problems?

Of course you could convince a lot of people by just showing how
all this works with, say, an 6-digit number which is the product
of two 3-digit primes - e.g., D = 201793.

Marcus.
.

Relevant Pages