Let $S_n$ be the sum of reciprocal values of non-zero digits of all positive integers up to (and including) $n$. For instance, $S_{13} = \frac{1}{1}+ \frac{1}{2}+ \frac{1}{3}+ \frac{1}{4}+ \frac{1}{5}+ \frac{1}{6}+ \frac{1}{7}+ \frac{1}{8}+ \frac{1}{9}+ \frac{1}{1}+ \frac{1}{1}+ \frac{1}{1}+ \frac{1}{1}+ \frac{1}{2}+ \frac{1}{1}+ \frac{1}{3}$ . Find the least positive integer $k$ making the number $k!\cdot S_{2016}$ an integer.
Problem
Source: JBMO Shortlist 2016 C1
Tags: Sum, combinatorics, positive integers
05.11.2017 18:44
The solution of the problem is pretty much just finding the number of the fractions. This number can be found by doing a couple of tricks: 1. We are going to find this number for numbers up to 2000. Now, the number of all the fractions except the 1/1 is equal in both first and second thousand, but these fractions are not important at all (they are integers). 2. Lets find number of fractions in the first hundred. Pretty much, there are 20 of each (easily found). Now, for each hundred we have 20 original plus 100 (the digit that declares hundred is counted here so as there are 100 numbers in a hundred we are adding 100) so 120 of these fractions in a thousand, so 240 in two thousand(the digit that declares thousands is always 1, so we won't count it). Now, for 2016 we will have 242 of each except of 7, 8 and 9 ones (we will have 241 of them), and 258 of twos. Obviously, we have S = m*1 + 258/2+ 242/3+ ... + 241/9= m+129+81-1/3+60+1/2 +50 + 2/5 + 40 + 1/3 +34 + 3/7 + 30 + 1/8 + 27 - 2/9= n+1/2+2/5+3/7+1/8-2/9= n+3103/2520, so k=7 is the least integer (if I didn't do any errors in calculation, but there is a huge risk I have ). I am not sure if there is a quicker way to solve this problem, but this is one easy problem and this is one even easier and more simple solution that every beginner can understand. PS: First!
01.05.2018 14:42
Nice same answer
24.01.2021 19:26
@Ika789_Master You have the correct k but in the fist thousant, let's say for example twos, are much more than 258!
24.01.2021 19:30
parmenides51 wrote: Let $S_n$ be the sum of reciprocal values of non-zero digits of all positive integers up to (and including) $n$. For instance, $S_{13} = \frac{1}{1}+ \frac{1}{2}+ \frac{1}{3}+ \frac{1}{4}+ \frac{1}{5}+ \frac{1}{6}+ \frac{1}{7}+ \frac{1}{8}+ \frac{1}{9}+ \frac{1}{1}+ \frac{1}{1}+ \frac{1}{1}+ \frac{1}{1}+ \frac{1}{2}+ \frac{1}{1}+ \frac{1}{3}$ . Find the least positive integer $k$ making the number $k!\cdot S_{2016}$ an integer. Wait, can't we simplify this by just checking number of $7$s, obviously if number of $7$s aren't a multiple of $7$ then immediately answer is $7$ since if the value of $S_{2016}$ looks like $a + \dfrac{b}{2} + \dfrac{c}{3} + \dfrac{d}{5} + \dfrac{e}{7}$, where $(a, b, c, d, e) \in \mathbb{Z}_{\geq 0}$ and $7 \nmid e$, then clearly $S_{2016} = \dfrac{7k + e}{2 \cdot 3 \cdot 5 \cdot 7}$ and for us to clear the denominator, we need to multiply by $7!$
29.05.2021 20:48
Exactly!
05.11.2024 16:05
We can try to find the fractional part of $S_{2016}$ and find $k$ as $7$