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.

  • 1
    $\begingroup$ 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? $\endgroup$ – David Roberts May 18 '12 at 7:16
  • $\begingroup$ 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... $\endgroup$ – Ilya Bogdanov May 18 '12 at 7:27
  • $\begingroup$ 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. :) $\endgroup$ – Lwins May 18 '12 at 12:38
  • $\begingroup$ 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\})$$ $\endgroup$ – Lwins May 18 '12 at 12:47
  • 1
    $\begingroup$ 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? $\endgroup$ – Karl Schwede May 20 '12 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.