Totient maximum


Fork me on GitHub
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