Totient permutation


Fork me on GitHub
2015-08-18

Problem 070: Totient permutation

Description:

Euler's Totient function, phi(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, phi(9)=6.

The number 1 is considered to be relatively prime to every positive number, so phi(1)=1.

Interestingly, phi(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

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


Solution:
v00000 000 // Project Euler - Problem 70
 ccc
 ?? ?? ??
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################
######################################################################################################################################################

>55*6*:10p57*:20p*40p230p"2("*11p"}("*21p022p112p"}22 "***31p1v>030p     v>g   0\v   v\-1 < >g   0\v   v\-1 <
vp08*8**::**::8p31p30:" "                                     _^#`g03g04< 2 v+55:<>\1>9*\:| 2 v+55:<>\1>9*\:|
>"X"30g:10g%\10g/3+p30g>30g+:40g\`       #v_$>30g1+:30p:10g%\10g/3+g" "-| 7 >%\:#^|#/+55\$< 8 >%\:#^|#/+55\$<
                       ^p+3/g01\%g01:\" ":<  ^                          <  >$ #\>#<>\# :#+_+^>$ #\>#<>\# :#+_vv
vg11                                                                     <^                            < v -+<-
>:42p::10g%\10g/3+g"X"-#v_:1+>:52p::10g%\10g/3+g"X"-#v_42g52g*:72p31g`#v_72g22g*42g1-52g1-*:82p12g*`#v_^v_v
  >$12g.@                   v $<                                       <                     v       <  <
^_^#-g12:+1             <   <^_^#-g12:+1             <                                       <p22g28p21g27<
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

The solution is practically identical to the one from Mathblog. But Kristian explains it much better than I :).

We use our trustworthy Sieve of Eratosthenes snippet and the GetCombinatoricHash-function from problem-62

The rest was straight-forward and not really that interesting.


Interpreter steps: 29 380 799
Execution time (BefunExec): 3.71s (7.91 MHz)
Program size: 150 x 47
Solution: 8319823
Solved at: 2015-08-18



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript