Problem 245

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
jper2
Posts: 3
Joined: Thu Jul 02, 2009 6:04 am

Problem 245

Post by jper2 » Thu Jul 02, 2009 6:11 am

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.

User avatar
Georg
Posts: 157
Joined: Mon Jan 21, 2008 7:00 am
Location: Mannheim, Germany
Contact:

Re: Problem 245

Post by Georg » Thu Jul 02, 2009 6:50 am

jper2 wrote: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
Posts: 3
Joined: Thu Jul 02, 2009 6:04 am

Re: Problem 245

Post by jper2 » Thu Jul 02, 2009 6:52 am

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

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 245

Post by quilan » Thu Jul 02, 2009 1:14 pm

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
ex ~100%'er... until the gf came along.
Image

jper2
Posts: 3
Joined: Thu Jul 02, 2009 6:04 am

Re: Problem 245

Post by jper2 » Thu Jul 02, 2009 7:33 pm

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
Posts: 189
Joined: Tue Jun 09, 2009 5:11 pm

Re: Problem 245

Post by zwuupeape » Fri Jul 10, 2009 5:08 pm

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?

User avatar
hk
Administrator
Posts: 10422
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 245

Post by hk » Fri Jul 10, 2009 6:47 pm

zwuupeape wrote: what is the index in your sorted list for these numbers
I don't generate such a list.
Image

User avatar
Georg
Posts: 157
Joined: Mon Jan 21, 2008 7:00 am
Location: Mannheim, Germany
Contact:

Re: Problem 245

Post by Georg » Fri Jul 10, 2009 9:59 pm

zwuupeape wrote:I made a sorted list of all numbers that fullfil the condition.
Your list is no subset of my list.

zwuupeape
Posts: 189
Joined: Tue Jun 09, 2009 5:11 pm

Re: Problem 245

Post by zwuupeape » Mon Jul 13, 2009 6:24 pm

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

Why was the upper bound changed??

zwuupeape
Posts: 189
Joined: Tue Jun 09, 2009 5:11 pm

Re: Problem 245

Post by zwuupeape » Wed Sep 23, 2009 5:32 pm

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 :)

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 245

Post by daniel.is.fischer » Wed Sep 23, 2009 5:45 pm

I'll bite.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 245

Post by quilan » Wed Sep 23, 2009 7:19 pm

zwuupeape wrote: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! :D
ex ~100%'er... until the gf came along.
Image

maomaoloverose
Posts: 4
Joined: Thu Feb 24, 2011 9:23 am

Re: Problem 245

Post by maomaoloverose » Thu Feb 24, 2011 9:30 am

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!
Image

User avatar
kevinsogo
Administrator
Posts: 1204
Joined: Thu Sep 16, 2010 3:39 am
Location: Manila, Philippines

Re: Problem 245

Post by kevinsogo » Thu Feb 24, 2011 9:59 am

@maomaoloverose

See the post above:
zwuupeape wrote: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
Posts: 1
Joined: Sat Apr 21, 2012 6:36 am

Re: Problem 245

Post by stpasha » Sat Apr 21, 2012 6:38 am

zwuupeape wrote: The 500th number is 8474486399
It should be 847486399. Also, the indices provided (100th, 500th, etc) are all wrong.

User avatar
Oliver1978
Posts: 165
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 245

Post by Oliver1978 » Fri May 22, 2015 1:08 pm

I'm advancing on this one *heavy breathing* 8-)

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? :?
49.157.5694.1125

vamsikal3
Posts: 104
Joined: Sat Oct 01, 2016 8:25 am

Re: Problem 245

Post by vamsikal3 » Sun Nov 25, 2018 1:06 pm

I get the same number both with my naive brute-force and a segmented-sieve brute-force.
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Image

Post Reply