Totient permutation
2015-08-18
Problem 070: Totient permutation
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<
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 |