2
$\begingroup$

It is known that Almost all primes have a multiple of small Hamming weight, which makes me wonder what is known about the least multiples of primes that have least Hamming weight.

Questions:

  • what are the values of the sequence $$\mu(n)\quad :=\quad \min\limits_{m\in\mathbb{N}}\left( \min\limits_{k\in\mathbb{N}}:\ \ \frac{\sum\limits_{i=0}^\infty d_i2^i}{p_n}=m\in\mathbb{N},\ \ \sum\limits_{i=0}^\infty d_i=k,\ \ d_i\in\lbrace0,1\rbrace\right)$$,
    where $p_n$ is the $n$-th prime number?
    $\mu(1)=1,\ \mu(2)=1,\ \mu(3)=1,\ \mu(4)=1,\ \mu(5)=3,\ \mu(6)=5,\ \dots$

  • for which $n$ is $H(p_n\mu(n)) \gt 6$ if $H()$ is denotes the Hammig weight of the argument ?

Improve this question
$\endgroup$
12
  • $\begingroup$ Let me see if I understand the question. If you want to calculate $\mu(6)$, say, you first find $p_6=13$, the sixth prime, then you find $13\times5=65=(1000001)_2$ has Hamming weight $2$, and obviously no multiple of $13$ is a power of $2$, so $\mu(6)=5$ (or is it $\mu(6)=2$?). Are the values of $\mu(n)$ tabulated at the Online Encyclopedia of Integer Sequences? $\endgroup$
    – Gerry Myerson
    Commented Mar 30, 2020 at 22:18
  • $\begingroup$ @GerryMyerson $\mu(6)=5$. I chose that on purpose because knowing the smallest factor $m$ that yields the smallest Hamming weight allows for easy calculation of that weight, but knowing the minimal Haming weight gives no way of easily calculating the minimal $m$ that yields that minimal weight, especially if the minimal Haming weight were proven by contradiction, i.e. the assumption that a higher Hamming weight were minimal led to cotradiction. $\endgroup$
    – Manfred Weis
    Commented Mar 31, 2020 at 2:51
  • $\begingroup$ OK, then $\mu(8)=27$, since the eighth prime is $19$, and $19\times27=513=2^9+1$ has Hamming weight $2$, and $19m$ has Hamming weight greater than $2$ for all $m<27$. It seems to me there will be a lot of $n$ for which $\mu(n)$ will be considerably greater than $6$. $\endgroup$
    – Gerry Myerson
    Commented Mar 31, 2020 at 3:03
  • $\begingroup$ @GerryMyerson shame on me! I wanted to know the $p_n$ with a Hamming weight larger than 6; I edited the question accordingly. Thank you. $\endgroup$
    – Manfred Weis
    Commented Mar 31, 2020 at 3:36
  • 1
    $\begingroup$ @GerryMyerson today is not my day... $\endgroup$
    – Manfred Weis
    Commented Mar 31, 2020 at 10:50

1 Answer 1

Reset to default
2
$\begingroup$

Thank you for the interest in my paper.

  1. Here is a criterion for good candidates: if the order of 2 modulo $p$ is less than $p^{1/6}$, then six-fold sums $2^{i_1}+ \cdots + 2^{i_6}$ cannot cover all $p$ residue classes. (Often the 0-class mod $p$ is covered only with high iterations, but it is possible, it is covered earlier. Actually, a slightly weaker condition might suffice, as there are only Binomial(ord_p (2),6) expressions with distinct exponents.) As the order of $2$ is at least $\log_2(p+1)$, which is the case of Mersenne primes, $p$ needs to be at least $3 \times 10^9$.

Non-Mersenne primes with this criterion might be quite a bit larger.

  1. At the time I wrote that paper, I did some experimental tests, which shows that smaller primes work, as the sumsets do not always grow with maximal speed.

Let us look at primes (not being Mersenne primes) with quite small order of 2. Let $A=(\{2^i: 0\leq i \leq \rm{ord}_p(2)-1\} ) \subset \mathbb{Z}/p\mathbb{Z}$.

For $p=178481$; $|A|=23, |2A|=276, |3A|=2047, |4A|=10879, |5A|=42711, |6A|=113275, |7A|=171810, |8A|=178480$,

which means one class is missing. It is exactly the 0-class, which is needed so that the sumset is a multiple of $p$.

Only the 9-fold sumset contains the 0-class.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .