Problem 003

[thundre]

2) Why are you using double? 6.00851e11 is not equal to 600851475143

It should be equal. That integer requires 40 bits, and most implementations of double have at least 50 of the 64 bits allocated to mantissa.

The use of int may be a problem. Use "long long" in C to get 64 bits.

Parliament718, the rules of this board say "don't post any code fragments or results", which means you should find a volunteer and PM the code to him rather than posting.

[GenePeer]

2) Why are you using double? 6.00851e11 is not equal to 600851475143

It should be equal. That integer requires 40 bits, and most implementations of double have at least 50 of the 64 bits allocated to mantissa.

I thought his double is rounding 600851475143 to 6 significant figures, which would explain why it's counting 2 as a factor. Now I see the problem is in the (int) type-casting.

It's kinda odd that it truncates the output to 6.00851e11 and not 6.00851475143e11. I've never programmed in C++ but I expected to behave like Java.

[haider.jafree]

plz tell me which algorithm to use for that problem

[Lord_Farin]

plz tell me which algorithm to use for that problem

Such a ridiculous request. This would be against the spirit of all that PE aspires to be.

[SamB]

I have developed an algorithm that works on the smaller example number (13195) so I'm assuming that the algorithm is a correct way to solve the problem. However it takes about 5 seconds to solve the 13195 case and will not complete the actual problem case.

I'm programming in PHP and loading the php page in a browser. I'm wondering if I just have a very inefficient algorithm or if you just can't get this to run in PHP and a browser. About how fast should this algorithm be? Thanks for your input.

NOTE: Please don't recommend other programming languages in your responses as I'm comfortable with PHP and would like to stick with it, at least for now.

[sivakd]

I just tried a naive implementation and it gives the result in 70 milliseconds for me in PHP.

You don't need to load the page from the browser to test your code. You should be able to run your script on the command line if you have the command line php is enabled.

[quantity]

I am in a similar situation to SamB (two posts up). Working in PHP, my program displays the highest prime factor given in the example. However, when I try to run the same program to solve the problem, it seems that the program eventually stops running because it's taking too long. While trying to figure out what I might need to do differently, I came up with a few surprising solutions. First, when I tried running the following:

Code: Select all

<?php

echo (600851475143 / 2);

?>

my browser displayed '300425737572', which is obviously not correct. Second, when I run 600851475143 through a function I wrote to check if a number is a prime, it tells me that it is, which is also obviously not correct. I'm wondering if the PHP/browser approach is just choking on the big number. This seems unlikely but I'm a little befuddled at the point that I can't even divide the number by 2 and get a correct result. Can I use PHP and view the results through a browser and get the solution to this problem? And if so: what adjustments do I need to make in order to be able to do simple things like divide properly?

[Lord_Farin]

You are dividing integers, meaning that the resulting expression will be typecast to an integer internally (or, simpler, that it will be rounded to return an integer). The fact that the result displayed is similar to the actual result tells you that the size of the number is not a problem.
I have successfully used PHP in the earlier stages to solve some problems. For checking divisibility, you can use the a%b operator (modulus) which returns 0 iff (that is, if and only if) a is divisible by b. In fact, it returns the remainder of the division.
As for this problem, you may have to reconsider your prime testing algorithm if it returns wrong results.

[EDIT: You are right Euler. I gave it no real thought. I recall this float-casting behaviour from PHP now. Probably, it's been too long since I solved a problem in PHP ]

[euler]

@quantity: That is most curious. Integer sizes in PHP are platform dependent. If you are using a 32-bit platform then the number example you gave: 600851475143, exceeds the 32-bit limit so PHP automatically converts the value to a "float", but it is within the size of 64-bit integer. However, I thought that PHP automatically converted to "float" if the resulting number is not integer. For examlpe, if you cast a variable as an odd integer but then divide by 2 it should convert it to a float type.

Out of interest, try the following:

Code: Select all

$a=(float) 600851475143;
print $a/2;

[edit]Also check your php.ini file. There is a setting: "precision = ?". By default it should be 14. I wonder if your value has been set to 12?[/edit]

[machine_easy2]

I think I have it in G-code. I won't fit neatly onto half a page, (in fact it will take several) and I will have to compile it by hand. but I am rather confident I can work it over a lunch break or two. (wow, I can use line numbers as variables!!!)

[machine_easy2]

I think I have it in G-code. I won't fit neatly onto half a page, (in fact it will take several) and I will have to compile it by hand. but I am rather confident I can work it over a lunch break or two. (wow, I can use line numbers as variables!!!)

I think i have it worked on it in G-CODE, how do i convert the .rtf file i wrote it in to a text only file? (no format, just the letters and numbers) on a mac? so I can send it to the machine that runs it, (via usb)

[chicharito14]

Could someone give me one (hopefully) small hint?? is the answer greater than 775146.09922452678 or smaller than it, ie the square root of 600851475143???

[Lord_Farin]

Could someone give me one (hopefully) small hint?? is the answer greater than 775146.09922452678 or smaller than it, ie the square root of 600851475143???

Yes

[hk]

Could someone give me one (hopefully) small hint?? is the answer greater than 775146.09922452678 or smaller than it, ie the square root of 600851475143???

Yes

Your answer should have been No,Yes.

[Lord_Farin]

Could someone give me one (hopefully) small hint?? is the answer greater than 775146.09922452678 or smaller than it, ie the square root of 600851475143???

Yes

Your answer should have been No,Yes.

To that end, I think it is amusing that you state that I should have asked everybody falling under the denomination of someone if they could give a hint, and they all answered they couldn't... . And don't even get me started on 'greater than' not being well-defined (one could also define it in terms of string length).

Oh well, cut the crap already.

[hk]

In that case: my answer is:
Yes,No,Yes.

[chicharito14]

I just solved the problem but my algorithm takes WAAAYY to much time. It take like 3 or 5 minutes, which is way to much. I did it using the hint from wikipedia of trivial division wich says: It consists in testing whether n is a multiple of any integer between 2 and √n. So that implied that all prime factors of n are between those numbers. But for example let n=35, sqrt(35)=5.9160797830996161. Lets truncate it to 5. But 35 is 5*7, where seven is not in the given range, ie its not between root 35 and 1. I think my algorithm would miss 7 since it starts cheching in numbers bellow the sqrt of "the evil big number." Maybe I am wrong, or I misunderstood something...?

[Lord_Farin]

I just solved the problem but my algorithm takes WAAAYY to much time. It take like 3 or 5 minutes, which is way to much. I did it using the hint from wikipedia of trivial division wich says: It consists in testing whether n is a multiple of any integer between 2 and √n. So that implied that all prime factors of n are between those numbers. But for example let n=35, sqrt(35)=5.9160797830996161. Lets truncate it to 5. But 35 is 5*7, where seven is not in the given range, ie its not between root 35 and 1. I think my algorithm would miss 7 since it starts cheching in numbers bellow the sqrt of "the evil big number." Maybe I am wrong, or I misunderstood something...?

In fact, at most one prime factor can be larger than $\sqrt{n}$ (for example, if $n$ is prime). It remains when the other factors have been divided out (assuming a trivial optimization)

[machine_easy2]

I think I have it in G-code. I won't fit neatly onto half a page, (in fact it will take several) and I will have to compile it by hand. but I am rather confident I can work it over a lunch break or two. (wow, I can use line numbers as variables!!!)

I think i have it worked on it in G-CODE, how do i convert the .rtf file i wrote it in to a text only file? (no format, just the letters and numbers) on a mac? so I can send it to the machine that runs it, (via usb)

The machine's operating system cannot accept 9+ digits numbers... Learning Python now.

[Bajinga]

This problem is so damn difficult.

I've created an algorithm that follows some advise on here (You'll find it on page 4; about the quotients).

Two of the integers are undefined until I define them with my two line code; that's the problem, one of them is defined before the other, and the C++ compiler doesn't read the lines together.


I'd like to post the algorithm, but it might be a spoiler.