Can You Simplify Large Numbers into Integers with Minimal Remainder?

[therogerwilco]

New here, quick thought :)

Well, this is probably an easy question, but I've been out of school for some time though until recently.
I figured I'ld ask it here cause physics junkies > math junkies :)

What would be the easiest route towards aquiring a int^int +/- remainder result from a fairly large number, in the billions +.
So, if given the number

345,231,234,564,234

It would give the solution (pretend the math is right)

4^34 with a remainder of -342
which would equate to, 4 to the 34th, minus 342.
the remainder can be positive or negative, but the goal is to get the nearest int^int combo, with minimal remainder...

lol

thank for any help that might be had :)

 

[maze]

Well, 345,231,234,564,234^1 would work, of course, but I don't think that's what you're looking for. I think you need to constrain the problem a bit more, since it might happen that the number is close to a square or a cube or something like that, and so the result wouldn't reduce the complexity as much as you might want. eg: 974,559,891,205 = 987198^2 + 1

 

[CRGreathouse]

Does it need to be the very best, or just 'good'?

I imagine you're requiring the exponent to be more than 1. Actually, let me try to specify it and have you tell me what's wrong, if anything:

Given a (large) number n, find a > 0, b > 1, and c so that

$$a^b+c=n$$

where a, b, and c are integers, and |c| is [small].

(Replace [small] with [minimal] if desired.)Now, does it bother you that b will be 2 fairly often? For example, I tested 10,000 values around 4e25, and I found that all 10,000 had exponent 2. I found the same thing with 100,000 numbers around your number.

 

[CRGreathouse]

Well, 345,231,234,564,234^1 would work, of course, but I don't think that's what you're looking for. I think you need to constrain the problem a bit more, since it might happen that the number is close to a square or a cube or something like that, and so the result wouldn't reduce the complexity as much as you might want. eg: 974,559,891,205 = 987198^2 + 1

I agree. The best form for the example given (with exponent > 1) is
18580399^2 + 7565033
which isn't less complicated at all.

If you constrain the exponent to be at least 3, the remainder term grows significantly larger:
70151^3 + 6742911283

 

[maze]

You could keep applying CR's idea, might get something interesting. eg
n = (((a^b + c)^d + e)^f + g)

 

[CRGreathouse]

You could keep applying CR's idea, might get something interesting. eg
n = (((a^b + c)^d + e)^f + g)

Just keep busting up those big numbers. :)

I could post my Pari code here, if anyone wants it, but it's not that great -- it could be much faster in a compiled language (> 5x), and could be algorithmically improved for the case of testing many sequential numbers (> 10x improvement at least, but only when testing thousands-millions of numbers).

I'm trying to get a count of the densities of numbers which are better approximated by a nonsquare than by a square. So far I have 2, 7, 100, 941, 5168, 38294, ... such numbers for 1, 2, 3, 4, 5, 6, ... digits. The densities are dropping off, though not as quickly as I'd hoped. For larger numbers of digits, even with the improvements above, I'd have to use random sampling to get a good idea, since it's taking too long as it is.

 

[maze]

You could keep going and going until everything is 1's, (), *, +, ^.

eg:
95
= 3^4+13
= (2+1)^(2^2)+(3^3+4)
= ((1+1)+1)^((1+1)^(1+1))+((2+1)^(2+1)+(2^2))
= ((1+1)+1)^((1+1)^(1+1))+(((1+1)^1+1)^((1+1)+1)+((1+1)^(1+1)))

 

[CRGreathouse]

You could keep going and going until everything is 1's, (), *, +, ^.

eg:
95
= 3^4+13
= (2+1)^(2^2)+(3^3+4)
= ((1+1)+1)^((1+1)^(1+1))+((2+1)^(2+1)+(2^2))
= ((1+1)+1)^((1+1)^(1+1))+(((1+1)^1+1)^((1+1)+1)+((1+1)^(1+1)))

From there you could drop the 1s since they're redundant at that point:
(++)^((+)^(+))+(((+)^+)^((++)+((+)^(+)))

Or even write it in RPN. There's a funny way to compress numbers.

 

[therogerwilco]

Ahh excellent, tyvm for the help fellas :)
The problems look much more do-able now lol

 

[CRGreathouse]

Glad we could help. As a general rule, take the whole number closest to the square root; squared, that should give a small absolute remainder.