For a given odd prime number p, define f(n) the remainder of d divided by p, where d is the biggest divisor of n which is not a multiple of p. For example when p=5, f(6)=1,f(35)=2,f(75)=3. Define the sequence a1,a2,…,an,… of integers as the followings: a1=1 an+1=an+(−1)f(n)+1 for all positive integers n. Determine all integers m, such that there exist infinitely many positive integers k such that m=ak.
Problem
Source: KJMO 2022 P3
Tags: number theory, prime numbers
29.10.2022 21:56
First, we can easily find that f(p^e t)=(t\mod p), which t is not divisible by p. Lemma. If n-1=\overline{c_k\cdots c_1c_0}_{(p)}, a_n=1+\sum_{i=0}^{k}{(c_i\mod 2)}. pf) Induct on n. Assume that the statement holds for n. Denote j be the minimal index such that c_j \ne p-1, then n=\overline{c_k\cdots c_{j+1}(c_j+1)0\cdots0}_{(p)}, f(n)=c_j+1. Since ((x+1) \mod 2) = (x\mod 2)+(-1)^{x+2}, a_{n+1}=a_n+(-1)^{f(n)+1}=1+\sum_{i=0}^{k}{(c_i\mod 2)}+(-1)^{c_j+2}=1+(c_j \mod 2)+\sum_{i=j+1}^{k}{(c_i\mod 2)}+(-1)^{c_j+2}=1+((c_j+1) \mod 2)+\sum_{i=j+1}^{k}{(c_i\mod 2)}. Thus, also holds for n+1. By the lemma, now we can easily show that the answer is all positive integers.
16.05.2023 20:31
We prove this using a modulus argument Assume WLOG that p is an odd prime. It can be see that adding (-1)^(f(n)+1) alternates between increase and decrease by 1 for all remainders of f(n) except for n congruent to p-1, where it adds two consecutive 1s after one move. Give that the sequence starts with 1, and that the increasing and decreasing 1s cancel out by n congruent to p-1 mod p (p-1 is even so half of it is decrease and half of it is increase). We have that through this increasing property all positive numbers should be able to be reached. And the answer is All positive integers