Finding a value larger than N that is the product of X and Y

[WhitetailAni]

A bit of a strange problem, but I'm attempting to find the largest image that paint.NET can allocate RAM for.

So far I have determined that:

1. paint.NET allocates 4 bytes per pixel

2. paint.NET supports up to 262144 pixels for width and height in its input box
I believe the limit is 30GB RAM flat (so 30,000,000,000 bytes) which I achieved with a 100000x75000 pixel image but I'd like to test for values slightly above that. I can't easily do it with a 100000 width or height as moving to 100001x75000 gives me 30,000,300,000 bytes of allocation.

And so I need to figure out how to find a value that is larger than my assumed maximum - but not too large. Given that 30,000,000,000 is the bytes and we know that paint.NET allocates 4 bytes per pixel we can drop our target N to 7,500,000,000. This gives me a target of finding a value that is larger than 7,500,000,000 and is the product of multiplying two numbers that are less than or equal to 262144 individually. It has to be close to the target value as possible, though - if it's just larger that won't tell me anything I don't already know.

 

I have no clue the best way to go about this. Do any of you have ideas? I program mainly in Swift, but I can do ObjC as well (and Java if I really have to).

[Kilrah]

Not really helpful to the actual question, but it might disappear knowing it will go way bigger, so all you'd find is probably "what's the limit with the free RAM you have at this exact moment" that'd change constantly...

 

 

[QuantumRand]

Maybe I'm misunderstanding the question, but can't you just take the square root of 7,500,000,000? That's 86,602, so an image of 86,602x86,603 would be under that limit, and 86,603x86,603 would be over it.

[Kilrah]

20 minutes ago, QuantumRand said:

and 86,603x86,603 would be over it

Yes, that's over at 7'500'079'609, but is it the closest you could get to 7'500'000'000 with 2 integers? probably not

[Sauron]

You can find all factors of a number and filter out results that would go above the size limits. Increase the total by one at a time and use the first number that gives you a result.

 

[colonel_mortis]

If you don't actually care about a programmatic solution and just want the answer, wolfram alpha can do that for you - you can just ask for the next composite number after 7,500,000,000, then for the factorisation of that.

 

In a spoiler just in case you were looking to find the solution yourself:

Spoiler

The next composite number is 7,500,000,001, which you can make with an image which is (13*223=2899) by 2587099

 

[Kilrah]

43 minutes ago, colonel_mortis said:

  Hide contents

The next composite number is 7,500,000,001, which you can make with an image which is (13*223=2899) by 2587099

The 2nd dimension exceeds the max

[colonel_mortis]

2 hours ago, Kilrah said:

The 2nd dimension exceeds the max

Ah damn I missed that part :/. It looks like that approach can still work though

Spoiler

7,500,000,002 = 62,449 * 120,098

 

[FlyingPotato_is_taken]

262144^2 is 68 719 476 736 so obviously you can't iterate through all the options. Either try solving it analytically or run a search. How?

 

The function you work with is f(x,y)=x*y

Let's visualize this function as 3D-plot:

 

Is this enough help?

 

In this very simple case the following could be good enough:

1. run the diagonal (x=y) Till you hit the a pair that is larger than the target N.

2. This will be your starting point for the search.

3. As the surface is symmetrical you only need to move/search one half. 

4. Now iterate/move around the surface to find the line that is the first pair above the target N.

[FlyingPotato_is_taken]

16 hours ago, Kilrah said:

Yes, that's over at 7'500'079'609, but is it the closest you could get to 7'500'000'000 with 2 integers? probably not

The closest you can get is 7'500'000'002 with 12 solutions (6 of them are mirrored):

114851	65302
120098	62449
124898	60049
184811	40582
223201	33602
229702	32651