# Project Euler #70: Totient permutation

# Project Euler #70: Totient permutation

layer8 + 2 comments It seems to me that by the problem definition you can get multiple answers for the same N. For the 100 example, phi(21) is 12 and the n/phi(n) ratio is 7/4, while phi(63) is 36 and the n/phi(n) also yields 7/4. The problem statement includes no criteria for deciding ties.

cantonios + 0 comments I agree. The answer is sometimes ambiguous.

ErikTillema + 0 comments Apparently the tie is decided by taking the first one (so 21 and not 63).

kitchent + 0 comments I am one of those who approach the problem using the property that is minimum when it is prime. And because is never the permutation of prime , so we set our sight on being the product of two primes and . (Hint on counting: )

For my implementation, I used a prime sieve to generate a list of primes, and feed them to a 2-level for loop afterwards. The point here is the find a balance between reducing the size of prime sieve (otherwise it would be TLE if we make a sieve of size ) and whether we have enough primes to get to the answer. For example, one of the answers is (product of and ), so we need to ensure is included in the prime sieve when is .

Apart from that, we have one honourable candidate who is an answer, but is not the product of two prime numbers, but three! This is the frustrating Test Case #10. I don't have a strategy yet to handle this other than treating it as a special case.

ErikTillema + 1 comment Solved this problem in F#. My O(n log n) solution was apparently not fast enough for all test cases, so I had to use a precalculated solution to pass all tests. The only smart trick I used was to exploit phi(m*n) = phi(m)*phi(n) if m and n are relatively prime. This speeds up the phi calculations.

khoangcachxalam1 + 0 comments thank for your good idea , i used phi(m*n) = phi(m)*phi(n) in myself code , i only wrong test case 0 and pass all test case other.

Argooni + 0 comments My code is giving wrong answer for test case 10. Other cases are success. Does anyone have any information about test case 10?

Ok seems this comment "it's a special case. try brute forcing values <5000 and compare." by shashank21j gave me the right answer. Thank you.

franko4don + 1 comment can "java.lang.OutOfMemoryError: Java heap space" make me get wrong answer for a test case?

saikiran9194HackerRank Admin + 0 comments @franko4don it means that your heap space has been exhausted.

SalvadorDali + 1 comment Any idea what is so special about TC_10? Yes, I read the discussion and followed a relevant thread, and in my case there were 6 numbers below 5000.

Opinion of @shashank21j or @advancedxy would be appreciated.

shashank21jHackerRank AdminChallenge Author + 1 comment It's a special testcase, which defies common logic. I'd say you'll have to try all cases

navneetkrverma + 0 comments Its taking way to long to show output...only two test cases passed..rest 8 are timed out...

Rounak10 + 1 comment iam getting an output 40 for 100 and i feel thats right , Has anybody got 21? if yes, then how?

ashishgimekarAsked to answer + 1 comment I think you are calculating phi(100) but that's not the question...

read the question carefully.. we need to find the number whose totient function value is its permutation...

phi(21) = 12

and the required ratio is also minimum...

so answer is 21 for 100tavinder + 0 comments then how we will come to know that 12 is permutation of 21

infernalkaka + 2 comments Is the output for input 100 is 21 ?? I think it must be 40

vipulkumar071941 + 0 comments Yeah this problem is also coming with me ...I have checked on internet the answer for 100 is 40?????

shashank21jHackerRank AdminChallenge Author + 2 comments What is phi(40)?

tavinder + 1 comment phi(40) is 16

shashank21jHackerRank AdminChallenge Author + 1 comment and how is 16 a permutaion of 40?

tavinder + 2 comments i dont know and why 100 is having such a unexpected answer

tavinder + 0 comments cn u please help me

shashank21jHackerRank AdminChallenge Author + 1 comment 16 is not a permutation of 40.

Read about Permutation

tavinder + 0 comments then what is the permutation of 40

iitrvpsingh + 1 comment what is minimum ratio????

shashank21jHackerRank AdminChallenge Author + 0 comments n/phi(n)

advancedxy + 1 comment what's the input for test case #10. I am keeping getting wrong answer even if I generated all the totient numbers under n..

shashank21jHackerRank AdminChallenge Author + 1 comment it's a special case. try brute forcing values <5000 and compare.

advancedxy + 1 comment There are only 4 numbers under 5000 whose totient number is a permutation of n. is that right?

If that's true, the brute forcing and the semi prime methods of my code gives same result.shashank21jHackerRank AdminChallenge Author + 1 comment Looks like you solved it, how do you feel?

advancedxy + 0 comments The brute forcing method I used to use has a bug. There are more than 4 numbers under 5000 whose totient number is a permutation of n.

Sort 12 Discussions, By:

Please Login in order to post a comment