Problem 245

[jper2]

Problem 245 (View Problem)
I have a question about precision. I have discovered what I believe to be almost all of the answers (my formulas are confirmed with brute force testing up to 5*10^8). However, the answer still isn't correct.

No problem, these things happen, and clearly I've missed something. My question, however, is on what precision is required, as this is what I'm most likely to have missed. For instance:

36844927487 has a totient value of 33774516864
The fraction as given in the problem comes VERY close to giving a unit fraction (the denominator is 12.000000003).

Should numbers like this be considered a hit? Currently I am not counting them, but if this is the issue, it could explain my missing findings.

I can also give a list of how many numbers I've found which are products of N primes. That is to say, xxxx numbers consistenting of 2 primes, xxx of 3 primes, etc., but I don't want to put any spoilers out there.

[Georg]

36844927487 has a totient value of 33774516864
The fraction as given in the problem comes VERY close to giving a unit fraction (the denominator is 12.000000003).

Should numbers like this be considered a hit? Currently I am not counting them, but if this is the issue, it could explain my missing findings.

No, very close to is not equal.

[jper2]

Well...it was worth a shot. Back to finding the problem in my algorithm then. Thanks.

[quilan]

You should be able to use modulus to test legitimacy of your answers & not need to use doubles.

if ((n - 1) % (n - tot) == 0):
success

[jper2]

Yeah, I figured it out....I was exiting one particular loop a little early, and was missing 2 solutions. All taken care of now! Thanks again.

[zwuupeape]

Damn I can't solve this...

Can anyone verify my solutions?

I made a sorted list of all numbers that fullfil the condition.

The first number is 15
The 100th number is 9203377
The 500th number is 8474486399
The 1000th number is 4694855413
The 1500th number is 12284315833

Can anyone confirm this? If my results are not true - what is the index in your sorted list for these numbers - how far off am I?

[hk]

what is the index in your sorted list for these numbers

I don't generate such a list.

[Georg]

I made a sorted list of all numbers that fullfil the condition.

Your list is no subset of my list.

[zwuupeape]

I still have to work on it... but I feel like I'm getting close .

Why was the upper bound changed??

[zwuupeape]

I got back to this problem after a while. I think I have a solution, but it seems like it's a bit... bruteforcish. But there are some problems for which I had the 'correct' algorithm and it took me ages while for others because of programming optimizations and the fact they use damned C++ it was reasonable.

Can someone who solved the problem please PM me? thanks

[daniel.is.fischer]

I'll bite.

[quilan]

I got back to this problem after a while. I think I have a solution, but it seems like it's a bit... bruteforcish. But there are some problems for which I had the 'correct' algorithm and it took me ages while for others because of programming optimizations and the fact they use damned C++ it was reasonable.

Can someone who solved the problem please PM me? thanks

There's a solution in thread that's ~49 seconds in Python. It's doable!

[maomaoloverose]

i only get three solutions

15 = 3 * 5

27874645 = 5 * 17 * 353 * 929

1431655765 = 5 * 17 * 257 * 65537

Can anyone give me another solution? thanks a lot!

[kevinsogo]

@maomaoloverose

See the post above:

The first number is 15
The 100th number is 9203377
The 500th number is 8474486399
The 1000th number is 4694855413
The 1500th number is 12284315833

These are all valid solutions.

[stpasha]

The 500th number is 8474486399

It should be 847486399. Also, the indices provided (100th, 500th, etc) are all wrong.

[Oliver1978]

I'm advancing on this one *heavy breathing*

If I set the maximum composite to 100,000 instead of 2*10^11 I get a total sum of 595,394 out of 22 numbers. Could this be?