2015-07-20

# Problem 069: Totient maximum

Description:

Euler's Totient function, `phi(n)` (sometimes called the phi function), is used to determine the number of numbers less than 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`.

n Relatively Prime phi(n) n/phi(n)
2 1 1 2
3 1,2 2 1.5
4 1,3 2 2
5 1,2,3,4 4 1.25
6 1,5 2 3
7 1,2,3,4,5,6 6 1.1666...
8 1,3,5,7 4 2
9 1,2,4,5,7,8 6 1.5
10 1,3,7,9 4 2.5

It can be seen that n=6 produces a maximum `n/phi(n)` for `n <= 10`.

Find the value of `n <= 1,000,000` for which `n/phi(n)` is a maximum.

Solution:
v000000    // Project Euler - Problem 69
################################################################################
################################################################################
################################################################################
v                     >p50g1+50pv                                         @.g07<
v                     ^1g0<     >30g1+:30p40g-       #v_"}}@"**60p   0>:1g70g*v\$
>170p"P":10p3:20p*40p230pv^5g03_^#-" "g+1/g01\%g01:g03<p050p030<      ^+1<v06:<\$
vp08*8**::**::8p11p10:" "<                                    _^#`g03g04< >g`  |
>"X"30g:10g%\10g/1+p30g>30g+:40g\`       #v_\$>30g1+:30p:10g%\10g/1+g" "-|^  p07<
^p+1/g01\%g01:\" ":<  ^                          <
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

I had a really complicated solution where I tried to generate an Phi Sieve and had to work around a lot of corner cases. Then I looked at this solution and - well - it's faster and simpler than mine. So I translated it to befunge.

 Interpreter steps: 35 542 Execution time (BefunExec): 16ms (2.22 MHz) Program size: 80 x 10 (fully conform befunge-93) Solution: 510510 Solved at: 2015-07-20

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