The Lemon Fool

Find two whole numbers with the smallest possible difference between them which, when multiplied together, will produce 1234567890.

Cinelli

Brute forced it in about 10 seconds, but would be interested in how to do it properly!

34227 36070

NotSure wrote:Brute forced it in about 10 seconds, but would be interested in how to do it properly!

By brute force, do you mean you delegated the entire task to the 'puter?

Does it count as any better if you factorise it? Unfortunately the easy factors stop after dividing by 90 (2x3x3x5). So that takes us straight back to brute force to extract the other two factors, after which your solution is obvious.

UncleEbenezer wrote:

NotSure wrote:Brute forced it in about 10 seconds, but would be interested in how to do it properly!

By brute force, do you mean you delegated the entire task to the 'puter?

Does it count as any better if you factorise it? Unfortunately the easy factors stop after dividing by 90 (2x3x3x5). So that takes us straight back to brute force to extract the other two factors, after which your solution is obvious.

Fraid so. Started at the square root and iterated backwards until integer factor was found

Well done, NotSure. Ten seconds is good going. I will try to make the next one harder.

Cinelli

cinelli wrote:Well done, NotSure. Ten seconds is good going. I will try to make the next one harder.

Cinelli

Some of us are too lazy to brute force a factorisation, and also too dim to find better solutions quickly.

If there's a more elegant method could you give a bit more time before revealing it please?


Cheers.

GS

GoSeigen wrote:Some of us are too lazy to brute force a factorisation,GS

two short lines of python (but pointless).

GoSeigen wrote:
and also too dim to find better solutions quickly.

Guilty as charged, except substitute "ever" for "quickly" in my case

GoSeigen wrote:Some of us are too lazy to brute force a factorisation...

Is there a method of factorising that doesn't use brute force?

Once I got down to 13717421 and didn't find any more factors manually before giving up, I delegated the task to a computer. (3607*2*5)*(3803*3*3) seemed most likely.

I like NotSure's idea of starting at the square root as it guarantees the correct answer.


Julian F. G. W.

Without giving away my source, this puzzle is more than a hundred years old. I would guess that the setter had a list of prime numbers and, as NotSure has suggested, if you start at the square root of 13717421, about 3708, and work upwards, it takes only about 8 long divisions until you come to 3803. Digital root considerations mean you don’t have to do all the divisions.

Cinelli

jfgw wrote:

GoSeigen wrote:Some of us are too lazy to brute force a factorisation...

Is there a method of factorising that doesn't use brute force?

Not in the general case of course, but mightn't there have been something cunning in the construction of this particular question that made it easily soluble? [Hence my "If there's a more elegant method..."]

It's pure luck that the factors are so close to the square root. There are some 500 prime numbers less than the root of 13717421 so potentially it could have taken 250 divisions whichever direction you worked from -- and that is with a list of primes available.


GS

I'd be happy with an aliquant answer but I'm transforming into a hippy, man.