# 2 interesting problems

• Jan 5th 2009, 02:53 PM
PaulRS
2 interesting problems
1. Let $\displaystyle g(n)$ be the greatest odd divisor of $\displaystyle n$, show that $\displaystyle \mathop {\lim }\limits_{n \to + \infty } \tfrac{1} {n} \cdot \sum\limits_{k = 1}^n {\tfrac{{g\left( k \right)}} {k}}$ exists and find it ( Bulgaria 1985)
2. Find all $\displaystyle k \in \mathbb{Z}\text{ with }k \geq 2$ such that $\displaystyle n \not|g(k^n+1)$, $\displaystyle \forall n \in \mathbb{Z}/n > 1$ (Olimpíada Rioplatense 2008) - $\displaystyle g(n)$ is defined as in 1 -

Have fun! (Happy)
• Jan 5th 2009, 04:39 PM
NonCommAlg
Quote:

Originally Posted by PaulRS
1. Let $\displaystyle g(n)$ be the greatest odd divisor of $\displaystyle n$, show that $\displaystyle \mathop {\lim }\limits_{n \to + \infty } \tfrac{1} {n} \cdot \sum\limits_{k = 1}^n {\tfrac{{g\left( k \right)}} {k}}$ exists and find it ( Bulgaria 1985)

a simple observation shows that $\displaystyle \sum_{k=1}^n \frac{g(k)}{k} = \sum_{k=1}^m \frac{1}{2^{k-1}} \left \lfloor \frac{n+2^{k-1}}{2^k} \right \rfloor,$ where $\displaystyle m=\lfloor \log_2 n \rfloor + 1.$ the value of $\displaystyle m$ is not important. what we need is to see that $\displaystyle m \rightarrow \infty$ as $\displaystyle n \rightarrow \infty.$

now since $\displaystyle x-1 < \lfloor x \rfloor \leq x,$ the squeeze theorem gives us: $\displaystyle \lim_{n\to\infty} \frac{1}{n} \sum_{k=1}^n \frac{g(k)}{k}=\frac{2}{3}. \ \ \Box$

the second problem is left for other members to try! (Wink)
• Jan 5th 2009, 06:56 PM
chiph588@
Quote:

Originally Posted by NonCommAlg
a simple observation shows that $\displaystyle \sum_{k=1}^n \frac{g(k)}{k} = \sum_{k=1}^m \frac{1}{2^{k-1}} \left \lfloor \frac{n+2^{k-1}}{2^k} \right \rfloor,$ where $\displaystyle m=\lfloor \log_2 n \rfloor + 1.$ the value of $\displaystyle m$ is not important. what we need is to see that $\displaystyle m \rightarrow \infty$ as $\displaystyle n \rightarrow \infty.$

now since $\displaystyle x-1 < \lfloor x \rfloor \leq x,$ the squeeze theorem gives us: $\displaystyle \lim_{n\to\infty} \frac{1}{n} \sum_{k=1}^n \frac{g(k)}{k}=\frac{2}{3}. \ \ \Box$

the second problem is left for other members to try! (Wink)

How did you obtain $\displaystyle \sum_{k=1}^n \frac{g(k)}{k} = \sum_{k=1}^m \frac{1}{2^{k-1}} \left \lfloor \frac{n+2^{k-1}}{2^k} \right \rfloor,$ where $\displaystyle m=\lfloor \log_2 n \rfloor + 1$?
• Jan 6th 2009, 01:34 AM
PaulRS
Quote:

Originally Posted by chiph588@
How did you obtain $\displaystyle \sum_{k=1}^n \frac{g(k)}{k} = \sum_{k=1}^m \frac{1}{2^{k-1}} \left \lfloor \frac{n+2^{k-1}}{2^k} \right \rfloor,$ where $\displaystyle m=\lfloor \log_2 n \rfloor + 1$?

First note that: $\displaystyle a + 2^{t } \equiv 0\left( {\bmod .2^{t+1} } \right) \Leftrightarrow a \equiv 2^{t} \left( {\bmod .2^{t+1} } \right)$ (sum $\displaystyle 2^{t}$ on both sides)

The idea is that$\displaystyle a = 2^t \cdot s{\text{ with }}s \ne \dot 2$ iff $\displaystyle a\equiv{2^{t}}(\bmod.2^{t+1})$

Indeed, to prove this:
$\displaystyle a = 2^t \cdot \left( {2l + 1} \right) \equiv 2^t \left( {\bmod .2^{t + 1} } \right)$, conversly if $\displaystyle a \equiv 2^t \left( {\bmod .2^{t + 1} } \right)$ then $\displaystyle \left. {2^t } \right|{a }$ and $\displaystyle 2 ^{t+1}\not|a$

Now since $\displaystyle \left\lfloor {\tfrac{n} {a}} \right\rfloor - \left\lfloor {\tfrac{{n - 1}} {a}} \right\rfloor = \left\{ \begin{gathered} 1{\text{ if }}\left. a \right|n \hfill \\ 0{\text{ otherwise}} \hfill \\ \end{gathered} \right.$

It follows easily that: $\displaystyle \sum\limits_{k = 1}^\infty {\tfrac{1} {{2^{k - 1} }} \cdot \left( {\left\lfloor {\tfrac{{n + 1 + 2^{k - 1} }} {{2^k }}} \right\rfloor - \left\lfloor {\tfrac{{n + 2^{k - 1} }} {{2^k }}} \right\rfloor } \right)} = \tfrac{{g\left( {n + 1} \right)}} {{n + 1}}$ (only one of the terms is not 0 )

My proof of (1) is based on the following observation: $\displaystyle \tfrac{{g\left( n \right)}} {n} = 2 - \sum\limits_{\left. {2^s } \right|n{\text{ ; }}s \geqslant 0} {\tfrac{1} {{2^s }}}$ then by a simple counting argument ($\displaystyle 2^j$ appears as many times as multiples of $\displaystyle 2^j$ there are in between 1 and n -both included-, that is $\displaystyle \left\lfloor {\tfrac{n} {{2^k }}} \right\rfloor$ ): $\displaystyle \sum\limits_{k = 1}^n {\tfrac{{g\left( k \right)}} {k}} = 2 \cdot n - \sum\limits_{k = 0}^\infty {\tfrac{1} {{2^k }} \cdot \left\lfloor {\tfrac{n} {{2^k }}} \right\rfloor }$ ...
• Jan 7th 2009, 06:13 PM
chiph588@
Sorry to be a bother, but I'm still a bit confused... (Wondering)
• May 30th 2010, 05:21 PM
chiph588@
Quote:

Originally Posted by PaulRS
1. Let $\displaystyle g(n)$ be the greatest odd divisor of $\displaystyle n$, show that $\displaystyle \mathop {\lim }\limits_{n \to + \infty } \tfrac{1} {n} \cdot \sum\limits_{k = 1}^n {\tfrac{{g\left( k \right)}} {k}}$ exists and find it ( Bulgaria 1985)
2. Find all $\displaystyle k \in \mathbb{Z}\text{ with }k \geq 2$ such that $\displaystyle n \not|g(k^n+1)$, $\displaystyle \forall n \in \mathbb{Z}/n > 1$ (Olimpíada Rioplatense 2008) - $\displaystyle g(n)$ is defined as in 1 -

Have fun! (Happy)

Any hints on 2? :confused:
• Jun 1st 2010, 09:01 AM
gmatt
Quote:

Originally Posted by PaulRS
Find all $\displaystyle k \in \mathbb{Z}\text{ with }k \geq 2$ such that $\displaystyle n \not|g(k^n+1)$, $\displaystyle \forall n \in \mathbb{Z}/n > 1$ (Olimpíada Rioplatense 2008) - $\displaystyle g(n)$ is defined as in 1 -

Correct me if I am wrong but the question is not clear as stated. Does the question mean to ask

$\displaystyle r \not|g(k^r+1)$, $\displaystyle \forall r \in \mathbb{Z}/n > 1$

or perhaps

$\displaystyle r \not|g(k^n+1)$, $\displaystyle \forall r \in \mathbb{Z}/n > 1$

or does it mean to ask

$\displaystyle n\not|g(k^n+1)$, $\displaystyle \forall n$

the way that for all is used currently doesn't make sense to me, since the quantified variable $\displaystyle n$ is used to define the domain set $\displaystyle \mathbb{Z}/n$.
• Nov 13th 2010, 01:33 PM
PaulRS
The bar there ("/") means "such that". So what I mean is that that should hold for all integers n greater than 1.