Floor fraction of multiple of 3

Algebra Level 4

$\left \lfloor \frac{2}{1}\times\frac{5}{4}\times\frac{8}{7}\times\frac{11}{10}\times\cdots\times\frac{2015}{2014}\times\frac{2018}{2017} \right \rfloor = \, ?$

Notation: $\lfloor \cdot \rfloor$ denotes the floor function .

The answer is 17.

5 solutions

Pranshu Gaba
Mar 2, 2017

To elaborate Debsurya's solution:

Let $A = \dfrac{2}{1} \times \dfrac{5}{4} \times \dfrac{8}{7} \times \cdots \times \dfrac{2018}{2017}$ . We want to find $\lfloor A \rfloor$ .

Consider the sequence $\frac{1+1}{1}, \, \frac{2 + 1}{2}, \, \frac{3+ 1}{3}, \, \ldots , \frac{n+1}{n}$ . As $n$ becomes large, the value of the fraction becomes smaller and closer to 1. We can say that $\frac{m+1}{m} < \frac{n+1}{n}$ for $m > n$ .

We see that the numerators of consecutive terms being multiplied in A differ by 3.
The following inequality will be very helpful:

$\frac{n+1}{n} \times \frac{n+2}{n+1} \times \frac{n+3}{n+2} < \frac{n + 1}{n} \times \frac{n + 1}{n} \times \frac{n + 1}{n} < \frac{n-1}{n-2} \times \frac{n}{n-1} \times \frac{n+1}{n}$

This inequality is useful because the lower and upper bounds of $\left( \frac{n + 1}{n} \right)^3$ collapse to

$\frac{n+3}{n} < \left( \frac{n + 1}{n} \right)^3 < \frac{n+1}{n-2} ~~~~~~~~~~~~\quad (\star)$

If we write this inequality $(\star)$ for $n = 4, 7, 10, 13, \ldots, 2017$ and multiply them together, then we get

$\frac{7}{4} \times \frac{11}{7} \times \cdots \times \frac{2020}{2017} < \left(\frac{5}{4} \times \frac{8}{7} \times \cdots \times \frac{2018}{2017} \right)^3 < \frac{5}{2} \times \frac{8}{5} \times \cdots \times \frac{2018}{2015}$

The bounds once again collapse to

$\frac{2020}{4} < \left(\frac{5}{4} \times \frac{8}{7} \times \cdots \times \frac{2018}{2017} \right)^3 < \frac{2018}{2}$

We can take the cube root and multiply throughout by $\frac{2}{1}$ to get bounds for $A$ .

$15.926... = \frac{2}{1} \times\sqrt[3]{\frac{2020}{4}}< \frac{2}{1} \times \frac{5}{4} \times \frac{8}{7} \times \cdots \times \frac{2018}{2017} = A < \frac{2}{1} \times\sqrt[3]{\frac{2018}{2}} = 20.0598...$

From this we get that $\lfloor A \rfloor$ can be equal to 15, 16, 17, 18, 19, or 20. We can tighten the bound on $A$ by starting with a greater value of $n$ for the inequality $(\star)$ .

If we start with $n =7$ , then we get

$16.520... = \frac{2}{1} \times \frac{5}{4} \times \sqrt[3]{\frac{2020}{7}}<A < \frac{2}{1} \times \frac{5}{4} \times \sqrt[3]{\frac{2018}{5}} = 18.475...$

For $n = 10$ ,

$16.764... = \frac{2}{1} \times \frac{5}{4} \times \frac{8}{7} \times \sqrt[3]{\frac{2020}{10}} < A < \frac{2}{1} \times \frac{5}{4} \times \frac{8}{7} \times \sqrt[3]{\frac{2018}{8}} = 18.0527...$

For $n = 13$ ,

$16.896... = \frac{2}{1} \times \frac{5}{4} \times \frac{8}{7} \times \frac{11}{10} \times \sqrt[3]{\frac{2020}{13}}<A < \frac{2}{1} \times \frac{5}{4} \times \frac{8}{7} \times \frac{11}{8} \times \sqrt[3]{\frac{2018}{11}}= 17.858...$

For $n = 16$ ,

$16.979... = \frac{2}{1} \times \frac{5}{4} \times \frac{8}{7} \times \frac{11}{10} \times \frac{14}{13} \times \sqrt[3]{\frac{2020}{16}} < A < \frac{2}{1} \times \frac{5}{4} \times \frac{8}{7} \times \frac{11}{8} \times \frac{14}{13} \times \sqrt[3]{\frac{2018}{14}}= 17.746...$

For $n = 19$ ,

$17.036... = \frac{2}{1} \times \frac{5}{4} \times \frac{8}{7} \times \frac{11}{10} \times \frac{14}{13} \times \frac{17}{16} \times \sqrt[3]{\frac{2020}{19}}< A < \frac{2}{1} \times \frac{5}{4} \times \frac{8}{7} \times \frac{11}{8} \times \frac{14}{13} \times \frac{17}{16}\times \sqrt[3]{\frac{2018}{17}}= 17.673...$

Since $17 < \lfloor A \rfloor < 18$ , we get $\lfloor A \rfloor = 17$ . Note that in order to get a better bound on the value of $A$ , we have to spend more effort multiplying numbers.

@Pranshu Gaba , we really liked your comment, and have converted it into a solution. If you subscribe to this solution, you will receive notifications about future comments.

Brilliant Mathematics Staff - 4 years, 3 months ago

@Pranshu Gaba can't we directly put a higher value of n ???why did you start from n = 4 when at first we could have put n = 19 or n = 25 or any larger value ?

space sizzlers - 4 years, 3 months ago

For higher values of $n$ , we have to carry out the multiplication of the first few fractions ourselves. If we were satisfied with the bounds for low value of $n$ , then we would just have to multiply the cube root with $\frac 21$ . The bounds weren't as tight as we wanted, so we had to go for higher $n$ , and had to multiply terms $\frac 21 \times \frac 54 \times \cdots \times \frac{17}{16}$ to the cube root.

If I had started with $n = 1$ , then the bounds that I have found out in terms of $n$ wouldn't work since one of the terms would have denominator zero. I started with the next best option of $n = 4$ .

Pranshu Gaba - 4 years, 3 months ago

Debsurya De
Feb 28, 2017

Consider $S^3 = \left( \dfrac{20}{19} \times \dfrac{23}{22} \times \cdots \times \dfrac{2018}{2017}\right)^3$

Observe that $\frac{20}{19} \times \frac{21}{20} \times \frac{22}{21} \le \left( \frac{20}{19} \right)^3 \le \frac{18}{17} \times \frac{19}{18} \times \frac{20}{19}$ . Using a similar inequality for all terms in $S^3$ , we get

$\frac{20}{19} \times \frac{21}{20} \times \frac{22}{21} \times \cdots \times \frac{2020}{2019} \le S^3 \le \frac{18}{17} \times \frac{19}{18} \times \cdots \times \frac{2018}{2017}$

$\implies \frac{2020}{19} \le S^3 \le \frac{2018}{17}$

$\implies \sqrt[3]{ \frac{2020}{19}} \le S \le \sqrt[3]{ \frac{2018}{17}}$

$\implies \text{(approx.) } 4.73731855723 \ldots \le S \le 4.91462908887\ldots$

$\implies 17.03612635\ldots \le \frac 21 \times \frac 54 \times \cdots \times \frac{17}{16} \times S \le 17.6737623004 \ldots$

$\therefore$ My answer came 17. Though a little approximation taken.

Moderator note:

Since we want to bound these terms, we want to minimize the error terms as much as possible.

There are many ways to deal with this. As an alternative approach, we can convert the product into a summation by taking logarithms:

$\log \prod_{n=0}^{667} \left ( 1 + \frac{1}{3n+1} \right ) = \sum \log \left ( 1 + \frac{1}{3n+1}\right ) \approx \int_0^{668} \log \left ( 1 + \frac{1}{ 3x+1} \right) \, dx$

However, this doesn't work well as yet because of the initial terms. As such, we simply use their value directly and approximate the remaining terms. For example, we can use

$\log \prod_{n=6}^{667} \left ( 1 + \frac{1}{3n+1} \right ) = \sum_{n=6}^{667} \log \left ( 1 + \frac{1}{3n+1} \right ) \approx \int_{5.5}^{667.5} \log \left ( 1 + \frac{1}{3x+1} \right ) \, dx,$

which gives us $S \approx 4.81$ . We can get upper and lower bounds by taking the proper Riemann sums .

Now that you've familiar with this idea, try this similar problem .

Why did we start from the $\frac{20}{19}$ term?

Agnishom Chattopadhyay - 4 years, 3 months ago

To minimise error.. If u do starting with 2 then range will go more like answer betwn 10 & 25.. It wud be difficult to get 17 then

Debsurya De - 4 years, 3 months ago

Very nicely done! Looking at $S^3$ allows us to obtain a telescoping inequality that easily bounds the terms.

However, blindly doing that gives us too large of a bound. We realize that the initial terms introduce too much of an error, and so desire to bound those initial terms more tightly. The best way to do so is just to use them directly, hence the truncated expression.

Calvin Lin Staff - 4 years, 3 months ago

Thnx a lot... It's an honour to get those words from Calvin Lin !!

Debsurya De - 4 years, 3 months ago

Nice Approximation . But you can describe why the second line come?

uzumaki nagato tenshou uzumaki - 4 years, 3 months ago

If we write numerator as (3n-1)! & denominator as (3n-2)! , then will it do??? Plss someone tell me this.

Rohit Vijayvargiya - 3 years, 4 months ago

What do you think? For example, what will you get when $n = 1$ ? And when $n = 2$ ?

Calvin Lin Staff - 3 years, 4 months ago

I don't know what was I up to at that time. Sry!

Rohit Vijayvargiya - 3 years, 4 months ago

Raj Mantri
Feb 28, 2017

To find $\left \lfloor \dfrac{2 \times 5 \times 8 \times 11\times \cdots \times 2018}{1\times 4\times 7\times 10\times \cdots \times 2017} \right \rfloor$

Now we can observe that 2, 5, 8, 11, ... , 2018 are in Arithmetic Progression

Similarly, 1, 4, 7, 10, ... , 2017 are also in Arithmetic Progression .

Further, the product of the members of a finite arithmetic progression with an initial element $a_1$ , common difference d, and n elements in total is determined in a closed expression $= d^n \times \frac{(\Gamma (a_1/d + n)}{\Gamma (a_1/d)}$

Derivation of this expression is

where $x^\overline{n}$ denotes the rising factorial

$\Gamma$ Gamma denotes the Gamma function. (Note however that the formula is not valid when $a_{1}/d$ is a negative integer or zero.)

Now consider Arithmetic Progression 2, 5, 8, 11, ... , 2018

Here $a_1=2$ and $d=3$ and

2018 is 673rd term of sequence 2, 5, 8, ... , 2018

So, $2\times 5 \times 8 \times \cdots \times 2018 = 3^{673} \times \frac{ \Gamma (2/3+673)]}{\Gamma (2/3)}$ -------- (1)

Now consider Arithmetic Progression 1, 4, 7, 10, ... , 2017

Here $a_1=1$ and $d=3$ and

2017 is 673rd term of sequence 1, 4, 7, ... , 2017

$1 \times 4 \times 7 \times \cdots \times 2017=3^{673} \times \frac{\Gamma(1/3+673)}{\Gamma (1/3)}$ --------- (2)

Now divide equation (1) by equation (2)

$\dfrac{ 3^{673} \times \dfrac{\Gamma(2/3+673)}{\Gamma (2/3)}} { 3^{673} \times \dfrac{\Gamma(1/3+673)}{ \Gamma(1/3)} }$

$= \dfrac{ \dfrac{\Gamma(2/3+673)}{\Gamma (2/3)}} { \dfrac{\Gamma(1/3+673)}{ \Gamma(1/3)} }$

$= [Γ(2/3+673)×Γ(1/3)]/[Γ(1/3+673)× Γ(2/3)]$

$= [Γ(673.666..)Γ(0.333..)]/[Γ(673.333...)Γ(0.666..)]$

$\approx (6.98× 10^{1611} ×2.67)/(7.97× 10^{1610} ×1.35)$

Now we will get ≈17.32

So, $⌊(2×5×8×11×...×2018)/(1×4×7×10×....×2017)⌋ ≈ ⌊17.32⌋$

≈17

Moderator note:

An equivalent way of relating the product of finitely many terms in an Arithmetic Progression is to use fractional Binomial coefficients . For example,

$2 \times 5 \times 8 \times \ldots \times 2018 = ( - \frac{2}{3} ) \times ( - \frac{2}{3} - 1 ) \times ( - \frac{2}{3} -3 ) \times \ldots \times ( - \frac{2}{3} - 667 ) = { - \frac{2}{3} \choose 667 }$

As expressed in the comments, this doesn't necessarily give us a non-calculator way to approach the problem.

I find your solution difficult to follow through.

In particular, you said "Derivation of this formula is ..." but that is not a derivation at all. It's merely a circular argument that didn't explain anything. To add to that, what does $\overline n$ represents?

[{(3^(673))(Γ(2/3+673)}/Γ(2/3)]) / [{(3^(673))(Γ(1/3+673)}/Γ(1/3)]

I also can't seem to figure out how you managed to simplify [{(3^(673))(Γ(2/3+673)}/Γ(2/3)]) / [{(3^(673))(Γ(1/3+673)}/Γ(1/3)] to 17.32....

Did you use a scientific calculator? If yes, then your solution appears to be obsolete because what you end up doing is "let me just plug it into my calculator to get the answer," which defeats the purpose of this question.

Can you clarify these 2 steps so that it's easier for people to understand your explanation better?

Pi Han Goh - 4 years, 3 months ago

I agree with you here.

If the point of the question was to get it done using a scientific calculator, I could have done it even faster with a Computer Algebra System.

1 2	`sage: floor(prod([(i2)/(i2 - 1) for i in range(1,1010)])) 56`

Although, changing it to a gamma function might be slightly better if that can be computed faster.

Agnishom Chattopadhyay - 4 years, 3 months ago

I had only solved Gamma function using that calculator One can't calculate "[{(3^(673))(Γ(2/3+673)}/Γ(2/3)]) / [{(3^(673))(Γ(1/3+673)}/Γ(1/3)]" such a big expression. I have represented this solution in the way I thought the answer to this question. I had tried hard for the solution. If this solution appears to be obselete for you, then sorry for such a solution Please send a solution of this question.

Raj Mantri - 4 years, 3 months ago

What is the gamma function? How do we know that the gamma function actually does what you claim? In the end of the solution, you ask to solve some expression. How does one do that?

Agnishom Chattopadhyay - 4 years, 3 months ago

I have solved that expression

Raj Mantri - 4 years, 3 months ago

The gamma function (represented by the capital Greek alphabet letter Γ) is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers.

Raj Mantri - 4 years, 3 months ago

Does one need to know about the analytic continuation of the factorial function to solve this problem? That seems like an interesting connection.

Agnishom Chattopadhyay - 4 years, 3 months ago

@Agnishom Chattopadhyay , I had used gamma function calculator to solve this expression.

Here's a link for it http://keisan.casio.com/exec/system/1180573444

Raj Mantri - 4 years, 3 months ago

the floor function of product (3n-1)/(3n-2), n=1..673

My Internet Is Fast - 3 years, 2 months ago

Harout G. Vartanian
Mar 4, 2017

wolframalpha check up

floor(product((3n-1)/(3n-2)), n=1 to 673)

=17

Yeah, but that defeats the purpose of this question, right?

There's no fun of just asking a computer to do your work all the time....

Pi Han Goh - 4 years, 3 months ago

Kyle T
Mar 1, 2017

<?php 
$arr = array();
for($a=1;$a<=2017;$a+=3){
    $arr[] = ($a+1)/$a;
}
echo floor(array_product($arr))."\r\n";

Your code works by actually multiplying out the elements of the array. Is there a faster way to do it with code?

The nice thing about this problem is that there is! Also, it is fun to know that it can be done without code.

Agnishom Chattopadhyay - 4 years, 3 months ago

from math import floor
ans = 1
max_val = 2018
for i in range (0,max_val,3):
    ans *= float(i+2)/(i+1)

print int(floor(ans))

Michael Fitzgerald - 3 years, 3 months ago

Floor fraction of multiple of 3

The answer is 17.

5 solutions

Moderator note:

Moderator note:

0 pending reports