Given this problem(link here):

$\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.

Easy Math Editor

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:

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in`\(`

...`\)`

or`\[`

...`\]`

to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI 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

Log in to reply

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

Log in to reply

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

I will use composite.

Thank you!

Log in to reply

@Vinayak Srivastava @Mahdi Raza @Siddharth Chakravarty

Log in to reply

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

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

Log in to reply

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

Log in to reply