Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

First we define a function $f(x,p)$, with $x$ a natural number and with $p$ a prime number.

$f(x,p)$ stands for the location where the digit "$p-1$" first appears in the base-$p$ expansion of $x$. If the digit "$p-1$" doesn't appear, $f(x,p)$ will be equal to $-\infty$. That is, if $x=\sum_{i\geq 0} a_i p^i$ with $0\leq a_i < p$, then $f(x,p)=\min\{i : a_i=p-1\}$. For example:

  • $f((122)_3,3)=0$;
  • $f((561603)_7,7)=2$;
  • $f((123)_5,5)=-\infty$;
  • $f((651634316331)_7,7)=3$.

Now consider a positive integer $A=(a_m a_{m-1} \cdots a_1a_0)_p$ with $f(A,p)=m$, i.e., $a_m=p-1$, $a_0,a_1,\cdots,a_{m-1}\neq p-1$.

My problem is how to prove that for any $h \in [0,2^{m-1}-1]\cap \mathbb{Z}$, which has at most $p-1$ digit "$1$" in binary representation. there is a $k \in \mathbb{Z}^+$ with $A-(p-1)k \geq 0$, satisfies that,

$$2^{f(A-k,p)} \ \mathbf{xor}\ 2^{f(A-2k,p)} \ \mathbf{xor} \ \cdots \ \mathbf{xor} \ 2^{f(A-(p-1)k,p)} = h$$


Edit: I (the one making the edit, not the OP) am not sure how to parse the problem. Is the following equivalent?

Let $h_0,h_1,\dots, h_{m-2}\in \{0,1\}$ with $\sum h_i < p$. Is there necessarily a positive integer $k$ with $A-(p-1)k\geq0$ and for $0\leq i \leq m-2$ $$\left| \{ j : 1\leq j < p, f(A-jk,p)=i \} \right| \equiv h_i \pmod{2}?$$


To Kevin O'Bryant,

Yes, it's equivalent to my version.

share|improve this question
1  
What is your motivation for proving this? How do you know what the answer should be? And what do you mean by xor-ing numbers? –  David Roberts May 18 '12 at 7:16
    
Do you care about the $(m-1)$st digit? That means, am I right that you don't distinguish the situations $f(A-ik,p)=-\infty$ and $f(A-ik,p)=m-1$? Or you need to have $f(A-ik,p)=m-1$ even number of times? If you don't need that, the number $k$ can be reconstructed from right to left in a straightforward manner... –  Ilya Bogdanov May 18 '12 at 7:27
    
Suppose I don't. Then how to reconstruct $k$ from right to left? I've tried for this but failed. Can you describe your method? Thanks. :) –  Lwins.Gafield May 18 '12 at 12:38
    
To David Roberts, This problem is closely related to how to find the identity of this function, $$F(x)=\mathbf{mex}(\{F(x-k) \ \mathbf{xor}\ F(x-2k)\ \mathbf{xor} \cdots \mathbf{xor} \ F(x-(p-1)k) \ | \ k \in \mathbb{Z}^+ , x-(p-1)k\geq 0\})$$ –  Lwins.Gafield May 18 '12 at 12:47
1  
I'm probably being dumb, but as David said, what does ${\bf xor}$ mean when applied to numbers (not base 2)? Is it done digitwise? –  Karl Schwede May 20 '12 at 23:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.