Let $f:\mathbb N\rightarrow\mathbb N$ be a non-decreasing function and let $n$ be an arbitrary natural number. Suppose that there are prime numbers $p_1,p_2,\dots,p_n$ and natural numbers $s_1,s_2,\dots,s_n$ such that for each $1\leq i\leq n$ the set $\{f(p_ir+s_i)|r=1,2,\dots\}$ is an infinite arithmetic progression. Prove that there is a natural number $a$ such that \[f(a+1), f(a+2), \dots, f(a+n)\] form an arithmetic progression.
Problem
Source:
Tags: function, logarithms, number theory, prime numbers, arithmetic sequence, number theory proposed
09.06.2010 08:09
It is not true. Let $p_1=3=s_1,p_2=s_2=5,n=2$ and $f(15n+r)=45n+g(r), 0\le r<15$. We can define $g(0)=0,g(3)=9,g(5)=15,g(6)=18,g(9)=27,g(10)=30,g(12)=36$ and $0\le g(1)\le g(2)\le 9\le g(4)\le 15,18\le g(7)\le g(8)\le 27, 30\le g(11)\le 36\le g(13)\le g(14)\le 45$.
10.06.2010 00:49
I think your counterexample doesn't work. When $n=2$, for every $a\in\mathbb N$, the sequence $f(a+1),f(a+2)$ is of course an arithmetic progression.
10.06.2010 07:25
I don't read end. I think $f(a+1),...f(a+n),...$ infinite arithmetic progression. Your result followed from chinese theorem. We can chose $a=s_i-i\mod p_i$. If $p_i$ is $i-$ th prime, then we can chose $f(a+1),...f(a+m), m\ge [n\ln n]$_
13.06.2010 15:16
Denote $ \{f(p_{i}r+s_{i})|r=1,2,\dots\} = S_i$, and denote its common difference by $d_i$. Step 1) There exists a constant $k$ such that $d_i = kp_i$ for all $i$. Proof) Let a positive integer $x$ satisfy $x \equiv s_i (mod p_i )$ for all $i$. (Such an integer $x$ always exists due to the Chinese Remainder Theorem) Considering $f(x + p_1 p_2 \cdots p_n ) - f(x)$, we have that it is equal to $\frac{p_1 p_2 \cdots p_n d_i}{p_i}$ for all $i$ (since they form an arithmetic progression). This yields $d_i = kp_i$. Step 2) There exists a natural $a$ such that $f(a+1) , f(a+2) , \cdots , f(a+n)$ form an arithmetic progression. Proof) Let $a$ satisfy $a+i \equiv s_i (mod p_i )$ for all $i$. There exists positive integers $m_i$ and $n_i$ that satisfy for all $i$, $m_i p_i - n_i p_{i+1} = 1$. Observe that for all $i$, $(a + (i+1)) - (a+i) = 1 = m_i p_i - n_i p_{i+1}$ $\Rightarrow (a+i+1) + n_i p_{i+1} = a+i+ m_i p_i$ $\Rightarrow f(a+i+1+n_i p_{i+1}) = f(a+i+ m_i p_i )$ $\Rightarrow f(a+i+1) + n_i d_{i+1} = f(a+i) + m_i d_i $ $\Rightarrow f(a+i+1) - f(a+i) = k$. Therefore, $f(a+1) , f(a+2) , \cdots , f(a+n)$ form an arithmetic progression with common difference $k$.
18.07.2017 13:02
Step 1 isn't true because there may be some r such that f(pi*r+s)=f(pi*(r+1)+s) because the equality at the problem given a set and not multi-set