Problem 108 / 110

[DDgeva]

I'm having some issues with this one (P. 108).
I've devised an algorithm that should solve it, and my function returns the correct values for n=4 and n=1260.
Nevertheless, I don't get a number of solutions greater than 1,000 for any n below 100,000, which seems too heavy for an "intro" problem.

1. Am I correct about the answer being below 100,000?

2. Can anyone confirm any of the following results:
for n = 1000, # of solutions is 25.
n=24, # = 11
n=78, # = 14
n=360, # = 53
n=15620, # = 68
n=6400, # = 43
n=1100, # = 38
n=150000, # = 149

If it's allowed, I will describe some principles of my method for anyone to judge.

Any help will be appreciated

[zwuupeape]

Those values are correct. It's just dangerous to make assumptions

[Phibonacci]

for n = 24 my algorithm gives me 8 solutions instead of 11. can someone give me just one distinct solution outside of this set of 8:

(25, 600)
(26, 312)
(27, 216)
(28, 168)
(30, 120)
(32, 96)
(36, 72)
(48, 48)

I can P.M. someone my algorithm, its only a few lines in length and I thought it was quite elegant but it is obviously not counting all the solutions.

[TripleM]

It should only take a few minutes to write a brute force program to output the answers for 24. That would be more helpful to you.

[Phibonacci]

Well after finding the problem with my solution counter I developed a new algorithm which is even less code and more efficient than the first. I thought I had this problem in the bag until I started iterating over n to find out when the solution counter returns a number greater than 1000. Its been running for probably 10 min and hasn't found the answer yet. Back to the drawing board. lol.

[wfwood]

I also have a question/concern about these problems. 1 is not the correct answer. however...1/1 = n *1/n... or 1/1=1/2+1/2=1/2+1/4+1/4=1/2+1/4+1/8+1/8... and so on based on the fact that it equals 1= summation for i from 1 to infinity of 1/2^i and the fact that 1 is its own inverse. 1 would technically be correct right? there are infinite ways of expressing 1=1^-1 as a summation of inverses of natural numbers, so why isn't 1 the right answer.

[harryh]

In both Problem 108 (View Problem) and Problem 110 (View Problem) 1/n must be expressed as a sum of exactly two fractions 1/x and 1/y (not an arbitrary number of such fractions).

[Kurushimi]

I can't understand why I'm not getting the correct answer. I'm pretty sure about everything I concluded but it just won't work. If you haven't figured it out yet and want to work on it with no help, don't keep reading.

[spoiler]snip.[/spoiler]

[TripleM]

As mentioned in the big red box at the top of the page, please do not post anything at all that may give away how to solve the problem - regardless of whether you put it in spoiler tags or not. Edit your post as soon as you can to remove it. I'll PM you with your wrong assumption.

[olleicua]

I'm somewhat concerned because I've written a brute force attempt in C that and on my 2.4 GHz MacBook Pro it has been running for almost fifteen minutes now. There are three things I could a conclude here.

1) There is something wrong with my algorithm such that it has already checked the correct answer but failed to find 1000 solutions.
2) My algorithm is inefficient.
3) Brute force on a 2.4 GHz MacBook Pro is too ambitious.

#1 seems unlikely. My answers match those above (now that I've switched to long integers). #2 seems possible but I have no idea how. #3 is the real question.

Peace

EDIT:

my program finally finished but now I have the wrong answer and I have no idea why. This leads me to lean towards #1 above. Can someone verify the following for me?

(sample results but not the answer)
Edit by hk: spoiler file removed.
Peace

[hk]

The problem states: exceeds 1000 solutions, so you have to find the smallest number for which there are 1000 OR MORE solutions.
I don't think there is much wrong with the numbers you computed, but could you please remove them as you're not supposed to post this kind of results.
(A single answer for a rather small number would have been enough for a helpful guy to see if you made any conceptual mistakes, wouldn't it?)

[olleicua]

I figured it was ok since someone had done the same thing higher on the thread. I figured my algorithm might be bugging out for higher numbers somehow.

I know that the problem asks for numbers with over 1000 solutions which is why I didn't post any numbers that give that many solutions. I'd love any sort of pointer/suggestion.

Also, you should check that wording. You claim here that I'm looking for numbers with 1000 or more solutions, the problem asks for a number that exceeds 1000.

[thundre]

3) Brute force on a 2.4 GHz MacBook Pro is too ambitious.

The phrase "brute force" is much overused on PE forums. But if you mean checking all (x,y) combinations for each n, you won't live to see the result.

If you mean that you're doing something slightly smarter that takes a day or so, you may have a precision problem.

I would encourage you to look for patterns in the solutions. Once you can recognize which solutions work and which don't, you can calculate how many without trying them all.

[olleicua]

hmmm... not sure what you mean by all combinations here.. I'll keep staring at it, thanks.

Peace

[hk]

I figured it was ok since someone had done the same thing higher on the thread. I figured my algorithm might be bugging out for higher numbers somehow.

I know that the problem asks for numbers with over 1000 solutions which is why I didn't post any numbers that give that many solutions. I'd love any sort of pointer/suggestion.

Also, you should check that wording. You claim here that I'm looking for numbers with 1000 or more solutions, the problem asks for a number that exceeds 1000.

Putting your spoilers in a text file doesn't make a lot of difference so I deleted that link.
As there are enough additional check values higher up in this thread I don't see any addional value in adding more.
You're right about that omission of mine. However, the idea has been conveyed.
I hope you will be grateful I took the trouble looking into your post.
Peace
Good luck.

[olleicua]

I appreciate your preserving the sanctity of the thread as you see necessary. You didn't provide any useful insight though. I'm not sure why someone like me would post here except to gain insight of some kind into one of these problems. Obviously it's more valuable for me to figure things out myself which is why I asked a question in terms of the big picture reasons I might be failing. I didn't expect to much help because the "figure it out yourself" mentality is quite strong here but I don't think calling me out on technicalities is grounds for appreciation. If you want budding eulerians to respect you than you should help them.

[TripleM]

I appreciate your preserving the sanctity of the thread as you see necessary. You didn't provide any useful insight though. I'm not sure why someone like me would post here except to gain insight of some kind into one of these problems. Obviously it's more valuable for me to figure things out myself which is why I asked a question in terms of the big picture reasons I might be failing.

While many people misuse it, the description of this forum is pretty clear - "A place to air possible concerns or difficulties in understanding ProjectEuler problems". It seems you understand the problem correctly.