Where is/are the problem(s)?

Given this problem(link here):

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

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

Clarification

  • The sum is taken over all positive integer divisors dd of 29233=23×31×4129233 = 23 \times31\times41.

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

  • aba\mid b denotes "aa divides bb".


For prime numbers:

If d1=p1a×p2b×p3c×d-1=p_1 ^a\times p_2^b\times p_3^c\times\cdots, where pnp_n are prime numbers.

ϕ(ϕ(d))ϕ(d)=ϕ(ϕ(d)d)=ϕ(d(11d)d)=ϕ(11d)=ϕ(d1d)=ϕ(d1)ϕ(d)=(d1)(p11p1)(p21p2)(p31p3)d×d1d=(p11p1)(p21p2)(p31p3)\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 Γ(d)\Gamma(d) denote ϕ(ϕ(d))ϕ(d)\cfrac{\phi(\phi(d))}{\phi(d)}

If d=p1a×p2b×p3c×d=p_1 ^a\times p_2^b\times p_3^c\times\cdots:

Γ(d)=Γ(p1)a×Γ(p2)b×Γ(p3)c×\large\Gamma(d)=\Gamma(p_1)^a\times \Gamma(p_2)^b\times \Gamma(p_3)^c\times\cdots

Solution:

The divisors of 2923329233 are: 123314123×31×4123×3123×4131×41\begin{array}{cccc} 1&23&31&41\\ 23\times31\times41&23\times31&23\times41&31\times41 \end{array}

11:

11

2323:

12×1011=511\cfrac{1}{2}\times\cfrac{10}{11}=\cfrac{5}{11}

3131:

12×23×45=415\cfrac{1}{2}\times\cfrac{2}{3}\times\cfrac{4}{5}=\cfrac{4}{15}

4141:

12×45=25\cfrac{1}{2}\times\cfrac{4}{5}=\cfrac{2}{5}

23×3123\times31:

Γ(23)×Γ(31)=433\Gamma(23)\times\Gamma(31)=\cfrac{4}{33}

23×4123\times41:

Γ(23)×Γ(41)=211\Gamma(23)\times\Gamma(41)=\cfrac{2}{11}

31×4131\times41:

Γ(31)×Γ(41)=875\Gamma(31)\times\Gamma(41)=\cfrac{8}{75}

23×31×4123\times31\times41:

Γ(23)×Γ(31)×Γ(41)=8165\Gamma(23)\times\Gamma(31)\times\Gamma(41)=\cfrac{8}{165}


d29233ϕ(ϕ(d))ϕ(d)=1+511+415+25+433+211+875+8165=5×(11×3×5+5×3×5+4×11+2×3×11+4×5+2×3×5+8)+8×1111×3×5×5=5×(165+75+44+66+20+30+8)+88825=2128825\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=56732128+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

No vote yet
1 vote

  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:

  • 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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Mahdi Raza - 3 weeks, 5 days ago

Log in to reply

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

Mahdi Raza - 3 weeks, 5 days ago

Log in to reply

  • Yeah. This function is multiplicative.

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

  • I will use composite.

  • Thank you!

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

Log in to reply

Log in to reply

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

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

Brilliant Mathematics Staff - 2 weeks, 6 days ago

Log in to reply

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

Percy Jackson - 4 days, 18 hours ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...