AMC 10 Daily Practice Round 2

Complete problem set with solutions and individual problem pages

Problem 25 Hard

For every integer n, we can represent it by n=2^ka_n, k is a nonnegative integer and a_n is an odd number. S_n=a_1+a_2+a_3+\cdots+a_n. Find S_{128}.

  • A.

    1366

  • B.

    2390

  • C.

    4098

  • D.

    5462

  • E.

    6878

Answer:D

By the definition, we know a_n=\frac{n}{2^k}=n-\frac{n}{2}-\frac{n}{4}-\cdots-\frac{n}{2^k}.

So for those n=2^k, S_{n}=1+2+3+\cdots+n-\frac{2+4+6+\cdots+n}{2}-\frac{4+8+12+\cdots+n}{4}-\cdots-\frac{n}{2^k}=\frac{(1+n)(\frac{n-1}{1}+1)}{2}-\frac{(2+n)(\frac{n-2}{2}+1)}{2\times 2}-\frac{(4+n)(\frac{n-4}{4}+1)}{2\times 4}\cdots-\frac{(n+n)}{2\times 2^k}=\frac{n(n+1)}{2}-\Sigma_{i=1}^k \frac{(2^i+n)n}{2^{2i+1}}.

Let T_n=\Sigma_{i=1}^k \frac{n}{2^{i+1}}=n\Sigma_{i=1}^k \frac{1}{2^{i+1}}=n(\frac{1}{2}-\frac{1}{2^{k+1}})=n(\frac{1}{2}-\frac{1}{2n})=\frac{n}{2}-\frac{1}{2},

U_n=\Sigma_{i=1}^k \frac{n^2}{2^{2i+1}}=n^2\Sigma_{i=1}^k \frac{1}{2^{2i+1}}=n^2\cdot \frac{1}{6}(1-\frac{1}{4^k})=n^2\cdot \frac{1}{6}(1-\frac{1}{n^2})=\frac{n^2}{6}-\frac{1}{6}.

\therefore S_n=\frac{n(n+1)}{2}-T_n-U_n=\frac{n^2}{3}+\frac{2}{3}, when n=2^k, k is a nonnegative integer.

Subsitute n=128 we have S_{128}=5462.

A less rigorous but time-saving approach to the exam can be to write the first 16 terms of a_n and S_n, then you may find out S_{2^k}=S_{2^{k-1}}+4^{k-1} and S_{2^0}=1, that will also give you the answer is 1+4^0+4^1+4^2+\cdots+4^6=5462.

In computer science, there is a cool method to calculate the value of k for each n, which is k = n \& (-n), commonly referred to as "lowbit". This involves many interesting properties of binary numbers, and children interested in this topic can search and learn more about it.

Related Problems
Problem 21 AMC 10 Daily Practice Round 2
Problem 22 AMC 10 Daily Practice Round 2
Problem 23 AMC 10 Daily Practice Round 2
Problem 24 AMC 10 Daily Practice Round 2
Think Academy Powered by ChatGPT