# Where is/are the problem(s)?

$\large\sum_{d\mid 29233}\frac{\phi(\phi(d))}{\phi(d)}$

Given that the sum above is equal to $\dfrac{p}{q}$, where $p$ and $q$ are coprime positive integers, find $p+q+2720$

Clarification

• The sum is taken over all positive integer divisors $d$ of $29233 = 23 \times31\times41$.

• $\phi(\cdot)$ denotes the Euler's totient function.

• $a\mid b$ denotes "$a$ divides $b$".

## For prime numbers:

If $d-1=p_1 ^a\times p_2^b\times p_3^c\times\cdots$, where $p_n$ are prime numbers.

\large\begin{aligned} \cfrac{\phi(\phi(d))}{\phi(d)} &=\phi\left (\cfrac{\phi(d)}{d} \right )\\ &=\phi\left (\cfrac{d\left ( 1-\cfrac{1}{d} \right )}{d} \right )\\ &=\phi\left ( 1-\cfrac{1}{d} \right )\\ &=\phi\left ( \cfrac{d-1}{d} \right )\\ &=\cfrac{\phi\left ( d-1 \right )}{\phi\left ( d \right )}\\ &=\cfrac{(d-1)\left ( \cfrac{p_1-1}{p_1} \right )\left ( \cfrac{p_2-1}{p_2} \right )\left ( \cfrac{p_3-1}{p_3} \right )\cdots}{d\times\cfrac{d-1}{d}}\\ &=\left ( \cfrac{p_1-1}{p_1} \right )\left ( \cfrac{p_2-1}{p_2} \right )\left ( \cfrac{p_3-1}{p_3} \right ) \end{aligned}

## For composite numbers:

Let's $\Gamma(d)$ denote $\cfrac{\phi(\phi(d))}{\phi(d)}$

If $d=p_1 ^a\times p_2^b\times p_3^c\times\cdots$:

$\large\Gamma(d)=\Gamma(p_1)^a\times \Gamma(p_2)^b\times \Gamma(p_3)^c\times\cdots$

## Solution:

The divisors of $29233$ are: $\begin{array}{cccc} 1&23&31&41\\ 23\times31\times41&23\times31&23\times41&31\times41 \end{array}$

#### $1$:

$1$

#### $23$:

$\cfrac{1}{2}\times\cfrac{10}{11}=\cfrac{5}{11}$

#### $31$:

$\cfrac{1}{2}\times\cfrac{2}{3}\times\cfrac{4}{5}=\cfrac{4}{15}$

#### $41$:

$\cfrac{1}{2}\times\cfrac{4}{5}=\cfrac{2}{5}$

#### $23\times31$:

$\Gamma(23)\times\Gamma(31)=\cfrac{4}{33}$

#### $23\times41$:

$\Gamma(23)\times\Gamma(41)=\cfrac{2}{11}$

#### $31\times41$:

$\Gamma(31)\times\Gamma(41)=\cfrac{8}{75}$

#### $23\times31\times41$:

$\Gamma(23)\times\Gamma(31)\times\Gamma(41)=\cfrac{8}{165}$

\large \begin{aligned} \displaystyle\sum_{d\mid 29233}\cfrac{\phi(\phi(d))}{\phi(d)} &=1+\cfrac{5}{11}+\cfrac{4}{15}+\cfrac{2}{5}+\cfrac{4}{33}+\cfrac{2}{11}+\cfrac{8}{75}+\cfrac{8}{165}\\ &=\cfrac{5\times(11\times3\times5+5\times3\times5+4\times11+2\times3\times11+4\times5+2\times3\times5+8)+8\times11}{11\times3\times5\times5}\\ &=\cfrac{5\times(165+75+44+66+20+30+8)+88}{825}\\ &=\cfrac{2128}{825} \end{aligned}

So the solution should be: $2128+825+2720=5673$

# Where is the problem?

"And, if you observe closely, the right answer is 2953 = 2128 + 825. So maybe you need not add 2720"

This means the problem was wrong.

Note by Páll Márton (no activity)
3 weeks, 5 days ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

I think your answer is correct, I just want to ask whether this function is multiplicative or not?

And, if you observe closely, the right answer is 2953 = 2128 + 825. So maybe you need not add 2720

- 3 weeks, 5 days ago

Also, it should be 'composite' instead of 'complex', unless there are different ways of saying 'not-a-prime'

- 3 weeks, 5 days ago

• Yeah. This function is multiplicative.

• 2953 is working(lol). I don't understand it.

• I will use composite.

• Thank you!

- 3 weeks, 5 days ago

- 3 weeks, 5 days ago

Hi Páll, the summation is not equal to $\frac{2128}{825}$.

In your solution, the "Gamma function" is wrong.

Staff - 2 weeks, 6 days ago

@Páll Márton (no activity) - What's with the (no activity)??? Does it mean you're offline?

- 4 days, 18 hours ago