## Problem:

Euler's Totient function, φ(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, φ(9)=6.

n Relatively Prime φ(n) n/φ(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/φ(n) for n [≤] 10.

Find the value of n [≤] 1,000,000 for which n/φ(n) is a maximum.

171

## Code:The solution may include methods that will be found here: Library.java .

public interface EulerSolution{public String run();}
/*  * Solution to Project Euler problem 19 * By Nayuki Minase *  * http://nayuki.eigenstate.org/page/project-euler-solutions * https://github.com/nayuki/Project-Euler-solutions */public final class p019 implements EulerSolution {		public static void main(String[] args) {		System.out.println(new p019().run());	}			public String run() {		int count = 0;		for (int y = 1901; y <= 2000; y++) {			for (int m = 1; m <= 12; m++) {				if (dayOfWeek(y, m, 1) == 0)  // Sunday					count++;			}		}		return Integer.toString(count);	}			private static int dayOfWeek(int year, int month, int day) {		long m = mod((long)month - 3, 4800);		long y = mod(year + m / 12, 400);		m %= 12;		return (int)((y + y/4 - y/100 + (13 * m + 2) / 5 + day + 2) % 7);	}			private static long mod(long x, long y) {		x %= y;		if (y > 0 && x < 0 || y < 0 && x > 0)			x += y;		return x;	}	}
The text passage contains a mathematical problem related to Euler's Totient function and a provided answer. It also includes a code snippet that solves a different problem (Project Euler problem 19).
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
## Problem:

Euler's Totient function, φ(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, φ(9)=6.

n Relatively Prime φ(n) n/φ(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/φ(n) for n [≤] 10.

Find the value of n [≤] 1,000,000 for which n/φ(n) is a maximum.

171

## Code:The solution may include methods that will be found here: Library.java .

public interface EulerSolution{public String run();}
/*  * Solution to Project Euler problem 19 * By Nayuki Minase *  * http://nayuki.eigenstate.org/page/project-euler-solutions * https://github.com/nayuki/Project-Euler-solutions */public final class p019 implements EulerSolution {		public static void main(String[] args) {		System.out.println(new p019().run());	}			public String run() {		int count = 0;		for (int y = 1901; y <= 2000; y++) {			for (int m = 1; m <= 12; m++) {				if (dayOfWeek(y, m, 1) == 0)  // Sunday					count++;			}		}		return Integer.toString(count);	}			private static int dayOfWeek(int year, int month, int day) {		long m = mod((long)month - 3, 4800);		long y = mod(year + m / 12, 400);		m %= 12;		return (int)((y + y/4 - y/100 + (13 * m + 2) / 5 + day + 2) % 7);	}			private static long mod(long x, long y) {		x %= y;		if (y > 0 && x < 0 || y < 0 && x > 0)			x += y;		return x;	}	}
user
The text passage contains a mathematical problem related to Euler's Totient function and a provided answer. It also includes a code snippet that solves a different problem (Project Euler problem 19).

TYPE: SINGLE_QUESTION_WITH_ANSWER