Middle School Math <3

Art of Problem Solving

AoPS Online

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Middle School Math <3

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5419 posts

#1 h Mar 11, 2024, 2:07 AM • 1 Y

Y by Soumya_cena

If $f(0)=1$ and $f(n)=\tfrac{n!}{\text{lcm}(1,2,\dots,n)}$ for each positive integer $n$ , what is the value of $\tfrac{f(1)}{f(0)}+\tfrac{f(2)}{f(1)}+\dots+\tfrac{f(50)}{f(49)}$ ?

If you enjoyed the above problem, check out the 2024 WMC Series!

This post has been edited 1 time. Last edited by peace09, Mar 11, 2024, 2:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1929 posts

#2 h Mar 11, 2024, 2:26 AM • 3 Y

Y by peace09, D_S, ESAOPS

Clearly, $f(n+1)=\dfrac{(n+1)!}{\text{lcm}(1,2,\dots,n,n+1)}=\dfrac{(n+1)!}{\text{lcm}(\text{lcm}(1,2,\dots,n),n+1)}$ . Thus, $\dfrac{f(n+1)}{f(n)}=(n+1)\dfrac{\text{lcm}(1,2,\dots,n)}{\text{lcm}(\text{lcm}(1,2,\dots,n),n+1)}$ . If we let $a=\text{lcm}(1,2,\dots,n)$ , then we want to find $\dfrac a{\text{lcm}(a,n+1)}$ . We know $\text{lcm}(a,n+1)=\dfrac{a(n+1)}{\text{gcd}(a,n+1)}$ , so our expression is equal to $\dfrac{\text{gcd}(a,n+1)}{n+1}$ . We actually wanted to multiply this by $n+1$ , so finally, $\dfrac{f(n+1)}{f(n)}=\text{gcd}(a,n+1)$ .

im too lazy to go further thonk

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5419 posts

#3 h Mar 11, 2024, 5:03 PM

Y by

The problem isn't High School Math in any sense of the word.. is there a single technique in the problem that isn't elementary

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17 posts

#4 h Mar 11, 2024, 5:32 PM

Y by

This is a quite easy problem, f(0)=1, so if we expand the series we get f(1) /f(0) =1, similarly all the terms will be equal to 1, as (n!/1*2*3*4.....n) =1 therefore 1 will come 50 times so ans is 50, am I correct.

This post has been edited 1 time. Last edited by Soumya_cena, Mar 11, 2024, 5:33 PM
Reason: Typing mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3789 posts

vsamc

#5 h Mar 11, 2024, 5:43 PM

Y by

Soumya_cena wrote:

This is a quite easy problem, f(0)=1, so if we expand the series we get f(1) /f(0) =1, similarly all the terms will be equal to 1, as (n!/1*2*3*4.....n) =1 therefore 1 will come 50 times so ans is 50, am I correct.

not true, f(n+1)/f(n) = n+1 if n+1 is not a prime power, and (n+1)/p if n+1 = p^l for some l >= 1

This post has been edited 6 times. Last edited by vsamc, Mar 11, 2024, 5:51 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17 posts

#6 h Mar 11, 2024, 5:48 PM

Y by

vsamc wrote:

Soumya_cena wrote:

This is a quite easy problem, f(0)=1, so if we expand the series we get f(1) /f(0) =1, similarly all the terms will be equal to 1, as (n!/1*2*3*4.....n) =1 therefore 1 will come 50 times so ans is 50, am I correct.

not true, f(n+1)/f(n) = 1 if n+1 is not a prime power, and (n+1)/p if n+1 = p^l for some l >= 1. so the answer is 50 + [sum(p prime power) n/p^l] which comes out to 220 if i did my calculations right

No but [n! / lcm (1,2,3........n)] is same as [n! /1*2*3.......n] the which equal to 1, it doesn't matter whether n is prime or not

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3789 posts

vsamc

#7 h Mar 11, 2024, 5:49 PM

Y by

Soumya_cena wrote:

vsamc wrote:

Soumya_cena wrote:

This is a quite easy problem, f(0)=1, so if we expand the series we get f(1) /f(0) =1, similarly all the terms will be equal to 1, as (n!/1*2*3*4.....n) =1 therefore 1 will come 50 times so ans is 50, am I correct.

not true, f(n+1)/f(n) = 1 if n+1 is not a prime power, and (n+1)/p if n+1 = p^l for some l >= 1. so the answer is 50 + [sum(p prime power) n/p^l] which comes out to 220 if i did my calculations right

No but [n! / lcm (1,2,3........n)] is same as [n! /1*2*3.......n] the which equal to 1, it doesn't matter whether n is prime or not

That's not true, for example if $n = 4$ then $f(4) = \frac{4!}{\text{lcm}(1, 2, 3, 4)} = \frac{4!}{12} = 2.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5419 posts

#8 h Mar 11, 2024, 5:50 PM

Y by

Soumya_cena wrote:

vsamc wrote:

Soumya_cena wrote:

This is a quite easy problem, f(0)=1, so if we expand the series we get f(1) /f(0) =1, similarly all the terms will be equal to 1, as (n!/1*2*3*4.....n) =1 therefore 1 will come 50 times so ans is 50, am I correct.

not true, f(n+1)/f(n) = 1 if n+1 is not a prime power, and (n+1)/p if n+1 = p^l for some l >= 1. so the answer is 50 + [sum(p prime power) n/p^l] which comes out to 220 if i did my calculations right

No but [n! / lcm (1,2,3........n)] is same as [n! /1*2*3.......n] the which equal to 1, it doesn't matter whether n is prime or not

Are you aware of the definition of the least common multiple? The least common multiple of $2$ and $4$ is $4$ rather than $2\times4=8$ .

Anyway, the default value of $\tfrac{f(n)}{f(n-1)}$ should be $n$ rather than $1$ ...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

105 posts

D_S

#9 h Mar 11, 2024, 5:50 PM

Y by

Technodoggo wrote:

Clearly, $f(n+1)=\dfrac{(n+1)!}{\text{lcm}(1,2,\dots,n,n+1)}=\dfrac{(n+1)!}{\text{lcm}(\text{lcm}(1,2,\dots,n),n+1)}$ . Thus, $\dfrac{f(n+1)}{f(n)}=(n+1)\dfrac{\text{lcm}(1,2,\dots,n)}{\text{lcm}(\text{lcm}(1,2,\dots,n),n+1)}$ . If we let $a=\text{lcm}(1,2,\dots,n)$ , then we want to find $\dfrac a{\text{lcm}(a,n+1)}$ . We know $\text{lcm}(a,n+1)=\dfrac{a(n+1)}{\text{gcd}(a,n+1)}$ , so our expression is equal to $\dfrac{\text{gcd}(a,n+1)}{n+1}$ . We actually wanted to multiply this by $n+1$ , so finally, $\dfrac{f(n+1)}{f(n)}=\text{gcd}(a,n+1)$ .

im too lazy to go further thonk

Continuing, $\gcd(a,n+1)$ is $n+1$ if $n+1 = pq$ for coprime $p,q>1$ , for $n+1 = p^a$ for prime p, $\gcd(a,n+1) = p^{a-1}$ . This should be enough to find the sum.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17 posts

#10 h Mar 11, 2024, 5:52 PM

Y by

Oh sorry, got it

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1423 posts

#11 h Mar 11, 2024, 6:38 PM

Y by

sol?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5419 posts

#12 h Mar 11, 2024, 7:34 PM

Y by

@above: You're extremely close to my answer so I suspect it's merely a computational error. Here is my solution from a while back.

@below: Yes, I think we all messed up the arithmetic a bit, to be completely honest with you.

This post has been edited 1 time. Last edited by peace09, Mar 11, 2024, 11:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

180 posts

#13 h Mar 11, 2024, 11:10 PM

Y by

This is a bit off from others' answers so I probably forgot a prime, prime power, or just sillied the arithmetic.
Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

209 posts

#14 h Apr 23, 2025, 11:39 PM

Y by

bruh what the calculator bash

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a