4
$\begingroup$

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.

$\endgroup$
7
  • 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, 2012 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$ May 18, 2012 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, 2012 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, 2012 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$ May 20, 2012 at 23:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.