Totient maximum

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

Download

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