Project Euler Forum

I submitted an answer for Problem 70 which I really can't figure out how could be wrong but isn't accepted. To avoid posting the answer here, the ratio I get for it of n/phi(n) is 1.0022690159663

Is this actually wrong and the answer has a better ratio? Feel free to email me at aarondf@bu.edu if want to answer directly where don't have to avoid posting the answer I got.

Note that I was worried my code had some bug so grabbed another person's code for 69 which is very similar and ran it with the changes for 70 and got the same answer again.

I get your result for 1 < n < 10⁶.

Note that the upper bound is actually 10⁷!

Thanks. Just the kind of dumb mistake I figured I had to have made. Oh well. With this change, solved no problem.

This one is really giving me a head ache

I'm getting the min ratio as 1.00075504904 from n = 7026037 = 2693 * 2609 yet it doesn't accept this answer.
I have tried the problem with a few different methods and I still come out with the same answer.
What am I doing wrong? My optomized method finds all numbers under 10^7 which is a multiple of 2 (or more) primes.

Any help would be greatly aprechiated

~ Alien Wolf

It looks like you're on the right track. Are you sure you're considering all possibilities? Did you check for possible 32-bit overflows?

AlienWolf wrote:What am I doing wrong? My optomized method finds all numbers under 10^7 which is a multiple of 2 (or more) primes.

If this is true, then your function f(n) seems to be wrong.

And you should read the problem very carefully a few more times to understand what exactly you are required to find.

Find the value of n, 1 < n < 10^(7), for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum

what does it mean "n/φ(n) produces a minimum"?

For example, given:
φ(87109) = 79180
φ(20617) = 20176

as 20617/20176 = 1.021857653 and 87109/79180 = 11.00138924, following the problem I should choose 20617?

Except for the fact that 87109/79180=1.10013892397069967, yes.

There is alread a thread for Problem 070.

Georg wrote:There is alread a thread for Problem 070.

I searched but using 070 in the title is a bit strange

At the bottom of this page are sort options
Choose "sort by subject" and set the "ascending/descending" switch.
Ihen you will see that "070" is not that strange.

I have done this problem a thousand different ways and I keep finding that

xxxxxx/yyyyyy = 1.0007136346

is the smallest ratio? Did anybody else get this or is it just me?

confused007 wrote:I have done this problem a thousand different ways and I keep finding that

<values>

is the smallest ratio? Did anybody else get this or is it just me?

That is incorrect. There are smaller ratio(s) (I have no idea how many, I just confirmed it wasn't the smallest). Might want to erase your numbers though, just in case.

Hi all,

I too seem to be stuck on this problem. My program seems to work fine (but obviously isn't), checking for minors and substituting correctly I think (when looking at the output on the screen)

Obviously it is not correct but the ratio I get is 1.000649. Is this far from the real mininum?

It's strange really, thought my program was working correctly and really expected to see the infamous green V pop up but alas no luck . I could use a tip for this one, must be something silly I am forgetting.

For instants my upper limit is 10^7 and I did not consider 35806 (035806) to be a permutation of 860053 (just an example, has no particular meaning in this problem).

The real minimum is 1.00070905..., if it's of any help to you. 10^7 is enough for a upper bound, and your reasoning with the zeros in the permutations is correct (035806 isn't permutation of 860053)...

MaJJ wrote:The real minimum is 1.00070905..., if it's of any help to you. 10^7 is enough for a upper bound, and your reasoning with the zeros in the permutations is correct (035806 isn't permutation of 860053)...

It is rather odd that I find a minimum that is lower than 1.00070905. I found a number lower than 10^7, calculated euler totient function and it was a permutation of that number and n/phi was 1.00064... mmm, wonder where my program went wrong, must be a mistake in one of my functions, though I thought my calculations of phi were correct. Back to the drawing tables I guess .

Thanks for the help.

EDIT: found the problem. Thought I had written a correct function for problem 69 which is a bit similar. Then I remembered I didnt write a program for problem 69 but had a "EUREKA !" moment for that one and solved it by head. (... 69... by head... no pun intended). Anyway it was an error where doubles got rounded down to int so in some instances 9.99999 became 9 instead of 10. Silly me.

I'm not sure what to do about this, but I believe I might have a significant contribution for this problem and problem 72.
For 70, I get these times:
Upper bound 10^7: about .6 seconds
Upper bound 99999900: about 6 seconds
For 72:
Upper bound 10^6: .05 seconds
Upper bound 10^7: .60 seconds
Upper bound 99999900: about 10 seconds
For 70, my timer actually gives .37 and 2.97 respectively, but these are definitely off and I just approximated the actual time.
For 72, my timer actually gives 6.97.
In the forum it looks like many struggled to abide by the one minute rule, and I think I saw one that ran in under a second.

Sorry if this post belongs somewhere else.

browni3141 wrote:I'm not sure what to do about this, but I believe I might have a significant contribution for this problem and problem 72.
For 70, I get these times:
Upper bound 10^7: about .6 seconds
Upper bound 99999900: about 6 seconds
For 72:
Upper bound 10^6: .05 seconds
Upper bound 10^7: .60 seconds
Upper bound 99999900: about 10 seconds
For 70, my timer actually gives .37 and 2.97 respectively, but these are definitely off and I just approximated the actual time.
For 72, my timer actually gives 6.97.
In the forum it looks like many struggled to abide by the one minute rule, and I think I saw one that ran in under a second.

Sorry if this post belongs somewhere else.

That's nice

I have not checked for Problem 70 (View Problem), it seems like a good improvement.

For Problem 72 (View Problem), for reference my timings are:
10^6: .008 seconds
10^7: .03 seconds
10^10: 3.7 seconds

The problem 72 overview mentions in the last paragraph a faster way to compute the answer.

browni3141> Yes too bad we can't post anymore and the problem forum.

However if you read carefully enough, there are some people far below 1sec.

Personnally I'm quite proud of my algorithm as i get a .6 sec as well with 10^7 but I don't use some of the optimisations that are made by others but which are on a "should" basis. (that is to say, are likely to be true and in fact are but there was no way of knowing that for sure before having an answer).
And it's recursive, and i love recursive answers